Comments Elsewhere

I think it’s possible that algorithms and computability are simply the wrong framework for understanding human intelligence or creating artificial intelligence.

They probably are the wrong framework. But I don’t see how that helps you with the halting problem. The issue with the halting problem isn’t that a solution is really hard, or that it’s ill-suited to the methods of computer programming. It’s that the notion of a correct general solution to the problem is, provably, internally contradictory. There’s nothing that could count as a correct general solution to the problem.

Here’s why. The halting problem is provably unsolvable because if it were solvable by any means, its output could be used to construct at least one algorithm which would be logically incompatible with the correctness of the solution to the halting problem. For a brief discussion why, see here. Basically, any proposed solution to the halting problem could be used to construct a “fink” function, which will do the reverse of what the halting problem says a given function will do when given itself as an input (so that, when you call FINK(FUNC), execution will halt if FUNC(FUNC) would loop forever, and will loop forever if FUNC(FUNC) would halt.) But then, when FINK(FUNC) gets itself as an input — FINK(FINK) — there is literally no possible answer to the question of what it will do. If it halts, then it doesn’t halt; if it doesn’t halt, then it halts. Hence, whatever your solution to the halting problem said it will do, it won’t do that. Hence, whatever your solution to the halting problem is, it’s wrong in at least one edge case.

Note that it does not matter whether the solution to the halting problem is accomplished within a Turing machine, or whether it is accomplished by some other means. Suppose the method for solving it is to print out a copy on a human being’s printer, and then wait for the human being to input TRUE or FALSE, and send the human being’s response back to the function to use as the return value for the halting function. Even so, you can still construct the fink function using that external input, which means that there just is no right answer that the human being could possibly return: whatever answer she returns, the program will do the reverse of what she said it would do.

The problem is not that finding a method to solve the halting problem is really hard, or limited by available resources or conventional computer architectures; it’s that the mere existence of a solution would necessarily entail an edge case where the solution cannot possibly be correct. A human being can’t do it any better than a computer can.