Non-computability.

According to Roger Penrose, humans can perform non-computable feats, such as dealing with Gödel questions. He uses this as a foundation to claim that the human mind cannot be expressed in terms of classical processes, and as such must be party to the only other (known) game in town: Quantum Mechanics.

Now, I haven't had the patience to sit through all of his arguments yet, though I slowly make progress. My understanding is that a large part of his stance is that an algorithm cannot usefully deal with a Gödel question, or equivalently, with the halting problem, while a human can.

My objection to this is that such problems always demand a certain quality of response when asked of UTMs: failing to respond forever is not acceptable as correct, nor is providing any response other than one that yields a truth when taken in combination with the question. This much is fine, however, when it is time for the human to answer, he is permitted the liberty of rejecting the question on the grounds that it is inherently unanswerable.

Obviously I am interested in artificial intelligence, and also find his assertion to be simply a self-serving one with a contrived philosophical backdrop for foundation. If anyone knows of, or can think of, a more sophisticated argument than the one above (or expose my flaws in my assessment of it) I would like to hear it.

Apologies for bringing up a largely philosophical question, my only excuse is that I cannot trust any other board with the question.

>>12
I tried to explain it in natural language but apparently not.
Let S be the enumeration all possible states of a chosen "TM", and A the enumeration of all state transitions of such a "TM", A = {(S₁,S₂), (S₂, S₃), ...}
Given that each state requires a non-zero amount of memory S must be finite for all "TM's" with finite memory. With this in mind it's trivial to construct an algorithm which tests whether a given program halts or not.

Set visited(S_n) = false for all states. Set s ∈ S = entry state, {g1, g2, g3, ... gn} ∈ S = exit state. While the current state is not visited and not an exit state, mark it as visited and traverse to the next state (run the next discrete step in the program). If the current state is an exit state, the program does not loop, we are done. If the current state is already visited, the program must loop, we are similarly done.

This will always give us a result in finite time (an inductive proof of this is left as an exercise for the reader, chiefly that the number of unvisited states must be strictly lower at every step of the program and thus must eventually be exhausted.)