I just wrote something on this subject on facebook... suppose this would be a good place for it.

TL;DR though - we aren't ready to try to answer such questions directly yet.

---------

We are self programmable Turing machines: the core problems (and frustrations!) of both AI and understanding the human brain are encoded in that statement. Frustrations, because it's an infuriatingly simple statement that's obviously true but we're nowhere near actually understanding.

On the one hand, it's almost a tautology if you take the Church-Turing thesis seriously. That is: there are no hypercomputers, there are only computers - Turing machines, and they're all fundamentally equivalent except in the details of capacity or performance. We can compute, thus we are also Turing machines.

But we are self programmable Turing machines: we're able to create new programs for other Turing machines (proof by example: any software engineer), and we're able to modify the existing programming for our own Turing machines (i.e. learn new things: the set of new things we can learn, or ways we can change our own behavior, has no fixed bound).

But Turing machines are deterministic: their output is completely determined by their inputs and the code they run. Completely deterministic: if a Turing machine appears to have random or nondetermistic outputs, either it's running a pseudo random number generator (thus deterministic), or it had random input (e.g. a hardware random number generator), and if you fixed the input the output would also be fixed.

So, we have this rather baffling conundrum - on multiple levels! of how in the hell to reconcile all this. We have a proof by example that it is possible to construct a Turing machine with outputs that are not only effectively non deterministic, but unbounded in complexity and potentially more complex than the Turing machine that created them: that this should be possible at all runs counter to the intuition of every programmer who's ever written a line of code.

For the first baffling thing: regular Turing machines have deterministic outputs, and while we are subject to the same rules and math that applies to any other Turing machine - so this has to be true for us too, in the strictest sense - it is clearly also true that in a very deep way our outputs are not deterministic, and not restricted in complexity.

By not restricted in complexity, I mean that it would be uninteresting if you had a Turing machine that produced nondeterministic output but it was all just white noise, or a string of random numbers. If that was all, there wouldn't be much to fuss over - all you need is a cryptographic PRNG and in practice you can get a seed anywhere. We, on the other hand, can produce things with actual semantics and structure - there's a big difference between spitting out some random numbers that seem to come from nowhere, and pulling a proof for the infinitude of the primes out of thin air.

That is, we're non deterministic in a very deep way: with a regular computer program, you can predict what will happen when you give it inputs and model the results, and if your model is correct you'll never be surprised - imagine sending packets to a network server, you always know more or less what you're going to get back.

(Digression: fundamentally, the model that tells you what response you'll get is a program that is in some way equivalent to the original program - it must be a Turing complete program, else it would not be able to capture all the possible outputs of the original Turing complete program. You can learn a lot about how natural languages work, and also about how intelligence must work, by applying this insight: first, note that natural language is (inherently) ambiguous, and it is also (like programming languages) Turing complete. When we construct a sentence that we're about to say to someone else, fundamentally (there are shortcuts most of the time, but this is really going on) we are resolving this ambiguity by constructing a (turing complete!) model of how the other person thinks, and then finding a sentence that, when run as a program on that model, will produce the desired output - that is, the sentence that will convey to them what we want them to understand. And when we're reading or listening to other people, we are treating those sentences as programs to be executed and run - that we run in our own models that we construct in order to figure out what the other person means.

This is fundamentally different from how the computer programs we construct communicate: they send packets back and forth with fixed, predefined meaning. When human communicate, in programmer speak we are running untrusted code from other people inside our own brains!).

But the fact that we're non deterministic is, I think, the easiest part to swallow: it's pretty clear that we make use of and rely on non determinism, so where we get the initial seed is uninteresting (it's a safe bet that evolution has provided us with the equivalent of hardware random number generators).

Programs constructing other programs though - and not in a deterministic way like a compiler, but genuinely new programs - that is baffling, though.

Modern machine learning - deep learning - does appear to actually be starting to scratch the surface of this: we're starting to figure out how to construct programs that can discover, on their own, the structure - the grammar - of things, to a degree that's actually starting to look promising. This is certainly a prerequisite any "self programmable Turing machine", but there's still a hell of a lot more we don't understand...