humans assisted by non-recursively self-improving technology (e.g. theorem provers, probabalistic code checkers, sandbox environments etc.) checks during execution or afterwards that the code behaves in respect of whatever properties the human cares about.

I reiterate my point: regardless of tools used, you still have a human brain at the end of the line and that brain's complexity limit is not high.

complete computational traces be provided

Going back to my example, what does a "complete computational trace" mean in the context of a few million threads running different code asynchronously on distributed hardware, all interacting?

Bayesian probability graphs as its fundamental unit of computation, like a list in Lisp

A list in Lisp is just a data structure. What is a Bayesian probability graph as a unit of computation? I don't even understand what it means.

assume that you have access to a lie detector

Sure. Give that lie detector to someone with the IQ of 60 and see how well they together will figure out something that a guy with the IQ of 150 wants to keep hidden from them, say, his true intentions and capabilities.