When studying computer science a student invariably learns about the infamous halting problem.

The problem states there is no general algorithm that can determine for every deterministic computer program whether that program will halt or not. This struck me as absurd when I first learned of the problem. Surely a whizkid like myself could design a simple algorithm to track the program’s memory and catch when it started repeating itself and determined it would not halt.

Once convinced the problem was indeed provably unsolvable, I then thought the problem must show that humans are not computers. This is because it seems intuitive that for every program, if I watch it enough and think about it carefully enough, I should be able to figure out whether it will halt.

Turns out this is not true either. There are many problems I cannot solve, and may not have a solution, so if I ran a search for a solution to these problems, I would never be able to say whether the search would stop.

All that being said, it does seem intuitive that I am, or perhaps humans in general are, better than algorithms at determining whether arbitrary programs will halt. This is mainly because it is very difficult to formally prove even very simple programs will halt. Yet programmers routinely write very complex programs where reliably reasoning about whether they halt or not is crucial to success. Thus, human programmers seem to have some inexplicable ability to solve particular instances of the halting problem that our brightest minds have not yet been able to pin down into what would undeniably be the greatest invention in all of history, bringing with it untold wealth and immortal fame.

After going back and forth a bit like this about the halting problem with a friendly skeptic, it could strike one as plausible that humans have something special going on in their minds which makes them more than machines.

Yet there is one more card up the skeptics sleeve. “Aha!” says the skeptic, “Do you not know that the halting problem applies to you?”

“Me?”

“Yes! Because we can construct an algorithm that will halt if you figure out that a particular program halts, and not halt if you figure out it does halt. And then we can give you this algorithm as a program and ask you to figure out if it will halt or not. If you figure out the algorithm will not halt, then it will, and if you think it will halt, it will not. So either way you go, you will be unable to solve the puzzle.”

“I am so confused.”

“Exactly.”

“Because you are so confused.”

“What?” exclaims the skeptic.

“Do you not know of the great oracle hierarchy?”

“Yes, but explain for the benefit of the reader.”

“Every algorithm has a halting status.”

“Go on.”

“We can think of this pairing of halting status to algorithm as an infinitely long table, since there is an infinite number of algorithms.”

“Sure.”

“Let’s imagine there is an algorithm that has access to this table (which is not physically impossible, but we’re making things up here).”

“Indeed, infinite doesn’t exist in the real world anyways, but mathematicians still use the idea all the time.”

“Now we are tracking! So, if we had this infinite table algorithm, we could run it for any algorithm and determine within a finite amount of time whether that algorithm will halt.”

“Yes, a bit of a mind bender, but there’s a way we can sort all algorithms so what you say is possible.”

“Thanks. Now notice we can take your original skeptical argument and apply it to this infinite table algorithm, showing we can feed the infinite table algorithm a special new algorithm, which contains the infinite table algorithm (bear with me here), and your argument will show the infinite table algorithm can also be given algorithms which it cannot determine whether they halt or not.”

“Now I’m confused.”

“Exactly.”

“Ok, ok, what you are saying is that even though my argument shows there can be certain algorithms a human (such as yourself) cannot determine the halting status, that doesn’t mean you don’t have some sort of access to this infinite halting status table. This is because we made up such an algorithm, and showed both things are true at the same time: it can determine the halting status for the infinite set of all normal programs, but there can be specially constructed algorithms which it still cannot determine the halting status.”

“Fantastic! You get it!”

“It is a nice thought experiment, but you missed one point,” grins the skeptic.

“What is that?”

“Even if we agree, my argument doesn’t disqualify the infinite table algorithm from determining all halting statuses, it’s an infinite table! And we also agreed that an infinite table cannot exist within reality! So your argument only works if we are figments of your imagination, and I most definitely am not.”

“I meet your modus ponens thrust with a modus tollens parry. If it is indeed demonstrated that humans can solve the halting problem better than all algorithms, what then?”

“A bit of a questionable premise, but let’s grant for sake of argument. If we could somehow demonstrate such a thing, and as we proved it requires access to an infinite table, and there is no way an infinite table can exist within reality, then there is only one logical conclusion.”

“Which is?”

“I hesitate to say, it seems so absurd.”

“Go on.”

“If we physically demonstrate access to a source of information that cannot physically exist, then the only logical conclusion is we are interacting with an infinite, non-physical realm. But that is
impossible!”

“Well, you know the saying, if once you eliminate the impossible, the only thing left is the possible. It’s all in Plato. My goodness, what do they teach people in schools these days?”

“Hmm, not sure what ancient dead Greeks have to do with any of this, but what you said has made me think. And for that I’m grateful. Now I need to go collect my thoughts. Have a good one!”

“Thanks, you too!”

And with that exchange, we have a possible, yet extraordinary, explanation for human ingenuity.

You may also enjoy these articles by Eric Holloway: What’s hard for computers is easy for humans Some of the surprising things computers have a hard time doing and why.

And, especially, as a vivid discussion of the halting problem:

Why your computer will never talk to you As a jokester recently demonstrated, even “shirts without stripes” is a fundamental, unsolvable problem for computers.