# Human computing power: Can humans decide the halting problem on Turing Machines?

We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines or general purpose computers?

Note: Obviously, in the strictest sense, you can always say no, because there are Turing Machines so large they couldn't even be read in the life span of a single human. But this is a nonsensical restriction that doesn't contribute to the actual question. So to make things even, we'd have to assume humans with an arbitrary life span.

So we could ask: Given a Turing Machine T represented in any suitable fashion, an arbitrarily long-lived human H and an arbitrary amount of buffer (i.e. paper + pens), can H decide whether T halts on the empty word?

Corollary: If the answer is yes, wouldn't this also settle if any computer has a chance of passing the turing-test?

• Humans may be able to work out whether a few particular machines halt. But because of the undecidability of the halting problem and the Church-Turing thesis, there is no algorithmic procedure that a human could use to solve the problem. – Carl Mummert Aug 21 '12 at 11:58
• @CarlMummert: Humans have ingenuity; This ingenuity is not necessarily bound to what you can express in terms of a TM. The reason the h.p. is undecidable for TM stems from the contradiction in the diagonal language. – bitmask Aug 21 '12 at 12:05
• If humans had the sort of power to figure out what inputs a given Turing machine halts on, they probably wouldn't have felt the need to articulate the definition of a Turing machine, or the classes P and NP, etc., as they would mostly seem to us as curiousities for describing completely trivial problems. (Of course, if you're in a generous mood, this might be seen as describing our relationship with deterministic finite automata.) – Niel de Beaudrap Aug 21 '12 at 14:00
• @NieldeBeaudrap: I disagree. Although we might be capable of something, it might still be a demanding task (to avoid the word "hard"). Also, if we don't concentrate properly we tend to make careless mistakes, especially with tedious tasks. – bitmask Aug 21 '12 at 14:52
• I think the best and only answer to your question is that nobody knows. Nobody knows whether the Church-Turing thesis is true, or what limitations exist on what humans can compute. We can say that if human beings can solve the halting problem, they're doing something that Turing machines can't. – Patrick87 Aug 23 '12 at 22:16

It is very hard to define a human mind with a such mathematical rigor as it is possible to define a Turing machine. We still do not have a working model of a mouse brain however we have the hardware capable of simulating it. A mouse has around 4 million neurons in the cerebral cortex. A human being has 80-120 billion neurons (19-23 billion neocortical). Thus, you can imagine how much more research will need to be conducted in order to get a working model of a human mind.

You could argue that we only need to do top-down approach and do not need to understand individual workings of every neuron. In that case you might study some non-monotonic logic, abductive reasoning, decision theory, etc. When the new theories come, more exceptions and paradoxes occur. And it seems we are nowhere close to a working model of a human mind.

After taking propositional and then predicate calculus I asked my logic professor:
"Is there any logic that can define the whole set of human language?"
He said:
"How would you define the following?
To see a World in a grain of sand
And a Heaven in a wild flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
If you can do it, you will become famous."

There have been debates that a human mind might be equivalent to a Turing machine. However, a more interesting result would be for a human mind not to be Turing-equivalent, that it would give a rise to a definition of an algorithm that is not possibly computable by a Turing machine. Then the Church's thesis would not hold and there could possibly be a general algorithm that could solve a halting problem.

Until we understand more, you might find some insights in a branch of philosophy. However, no answer to your question is generally accepted.

• Assuming that the brain can be modeled as a collection of molecules interacting with each other, wouldn't it be sufficient to prove that molecules are "computable"? There seems to be some evidence for this assumption (see OpenWorm). – Olivier Lalonde Mar 23 '14 at 20:13
• @OlivierLalonde Your assumption would imply that humans can be simulated by a Turing machine and therefore cannot solve the halting problem. However, your assumption is too strong. By Uncertainty principle en.wikipedia.org/wiki/Uncertainty_principle in quantum mechanics, the state of the physical system cannot be simulated on a computer since any random sequence of states is incomputable. You may then argue that the model of the physical system is deterministic - not easy. The question reduces to whether a simulation of a brain can be computable. – Dávid Natingga Oct 28 '14 at 22:01
• @DavidToth A random infinite sequence of states is not computable. Any system containing a finite number of events is computable, assuming that all the quantities in that system are computable with respect to each other. And even if that's not the case, we would simply end up with a rounding error smaller than thermal noise, which should have no significant effect on human cognition. (The error would necessarily be immeasurably small, in fact.) – Keen Nov 12 '14 at 17:06
• @Cory Yes, any finite subset of any set even an incomputable one is computable, but the point is to "simulate the future" not to replay the past. In this sense there may not be a Turing machine that would predict a human action in an arbitrarily distant time in the future. It would need to predict one of the combinations of an infinite sequence of future events. The fact that the number of possible events at one time may be finite does not alter the incomputability of the infinite sequence. – Dávid Natingga Nov 13 '14 at 20:27
• @DavidToth I'm not asserting that all of reality is necessarily Turing computable. However, the argument from quantum randomness does not hold up. Quantum mechanics is a system used by physicists to compute properties of future states of reality. Physicists' (computable) models can handle this randomness because the number of (distinguishable) outcomes is always countable (and thus computable), even in cases where it's infinite. Note that there's also no reason to believe that quantum randomness would give humans, and not other machines, the capacity to evaluate uncomputable functions. – Keen Dec 15 '14 at 20:42

I think there is no way how give a definitive answer to this question, as nobody really knows the capabilities of human mind (and I doubt anyone ever will).

But there is a view that gives one possible solution or explanation to this question:

When we're searching an oracle to solve the halting problem (or decide provability of first-order logical formulas etc.), we naturally want the oracle to be correct, it must not make any mistakes. But human mind isn't consistent, it makes mistakes. Nobody can honestly say that all statements (s)he believes are true are really true. This inconsistency can be viewed as the source of the power human mind has. Due to its inconsistency, it isn't subject of limitations that follow from the halting problem, Gödel's incompleteness theorem etc. We make mistakes, we mistakenly believe in false statements, and as our knowledge grows, we correct them (and of course find new false statements we believe in). On the other hand, we want all formalizations of the notion of algorithm or all logical calculi to be consistent, so that we can prove once and for all that they're free of such mistakes. And this makes them limited.

• We do not make more mistake than our proof systems. It is quite common to works on hypotheses, even in Mathematics. Sometimes they lead to results that are provably wrong (or observationally wrong in natural sciences), and we revise our beliefs and some of our working hypotheses. In mathematics this is the basis for proof by reductio ad absurdum (which are non constructive). Non-deterministic automata also rely on the idea that one can get results even when exploring wrong paths, as long as one can also explore other path. Nothing there that differentiates the human mind. – babou Nov 10 '14 at 9:46
• Interesting point about the possibility of inconsistency being one source of (computational) power of the mind. Has it occurred to you that there may even be types of thought beyond mathematics wherein two evidently contradictory data could both be true? The quality of "truth" as a relative concept which cannot be assigned a number is a distinction of human thought which is difficult (dare I say impossible?) to fully replicate in a machine. The point being, defining mental inconsistency as "mistaken belief in falsehood" (as you seem to do here) is itself a rather limited outlook. – Wildcard Jun 7 '16 at 9:25
• It can be shown that one cannot prove that oneself will never mistake but that doesn't mean they can disprove they will never make a mistake either. For example, suppose our universe is a Conway's game of life simulation that does not follow many worlds theory. Furthermore, suppose you state that you never have and never will make a mistake. Then a certain algorithm will not halt until after you state that that algorithm won't halt. If you're using a strong enough system, you can deduce that you will never say it won't halt and therefore that it will never halt and state it causing it to halt. – Timothy Aug 30 '18 at 2:17

Just to make things clear: The Church-Turing hypothesis has nothing to do with some dogma of a hypothetical Church of Turing. There is nothing religious about it. On the contrary, it is just a hypothesis summarizing the best of our knowledge. There is no metaphysical Implication. The question whether humans could do better, that they could achieve more than machines, is a metaphysical question as we have strictly no handle on it, no hint whatsoever of what could differentiate a human from a machine. So this question should be migrated to metaphysics.stackexchange.com.

But let us assume that the human brain can solve the halting problem for Turing Machine. Then the computational model of Turing Machines becomes much less important, and the Church-Turing Hypothesis becomes much less relevant, as we have a more powerful model called the Human Model (to avoid the word machine). Of course this (arbitrarily long-lived) human model comes with its own hypothesis on computability.

But then, while the halting problem for Turing Machines is no longer critical, we now have to deal with the Human Model Halting problem. And diagonalization will show that the Human Model Halting problem is not decidable by a Human. Then what?

Now, you might object that diagonalization would not be applicable. That would mean, I guess, that associating some form of Gödel numbering with computing devices, proofs, or whatever we describe with notation would no longer be possible, though it is currently the basis of all science. In other words, we would have to deal with entities, concepts that have no written representation, that cannot have a written representation, or to say it more generally concepts without a syntactic representation, whether written, oral or otherwise.

Of course, this would be in opposition with the teaching of John whose very first sentence is: "In the beginning was the Word, and the Word was with God, and the Word was God." Negating the fundamental importance of syntax, of the word, is thus a very anti-christian statement. I am of course not taking a stand on this, but since my first take on this question is that it is a metaphysical one, and since the question is not on hold, it seems natural to consider all consequences, including the metaphysical consequences.

• Non-christian is not synonymous with atheist. – ubadub Dec 10 '18 at 3:33
• @ubadub You are totally correct. My mistake entirely, or more precisely my lack of attention to a major point. I made the correction. Would you know what other religions have to say on the matter? – babou Dec 10 '18 at 10:48
• several schools of Buddhism would classify "absolute" reality as ineffable, i.e. beyond linguistic description altogether, and yet m knowable (by the enlightened). This produces an interesting set of philosophical issues that have been the subject of Buddhist discussion for millennia. See this article: bit.ly/2G71tmk for one take, although it is not the only one. Garfield has a dialetheist reading of Madhyamaka Buddhism which not all scholars agree with (e.g. see "Is Gorampa's "Freedom from Conceptual Proliferations" dialetheist?" by C. Kassor). – ubadub Dec 10 '18 at 14:41

Consider this from a different perspective.

• First-order logic is undecidable, that is, there is no decision procedure that determines whether arbitrary formulas are logically valid. (But the set of true first-order formulas is semi-decidable, that is if a formula is true, it's possible to find a proof by an algorithm.)
• Proof assistants help prove theorems in first-order (or even higher-order) logic. The proof assistant ensures that the proof is done correctly and can even help resolve some cases. However, human interaction is require to guide the proof assistant to the correct answer.

Proof assistants could be used to prove properties of individual Turing machines.

Carl Mummert's comment nailed it.

1. My understanding (correct me if I am wrong) of the Church-Turing thesis is the idea that anything that can be computed can be computed by a Turing Machine.

2. And also, if a Turing Machine could compute if another Turing Machine would halt or not on an input (halting problem), then you could also compute if another Turing Machine would not halt on a given input (just swap yes for no, and no for yes!) - significant because then you could feed this Turing Machine to itself - would it not halt on itself on the input? If yes (not halting), then no (is halting??). If no, then yes. If yes, then no. If no, then ye... hmmm.

So, 2. shows it is impossible for a Turing Machine to solve the halting problem. But I don't think there is any clear evidence to contradict 1. at this time. Every model of computation known still can solve (decide) as much as a Turing Machine can.

The burden of proof seems to be on the person coming up with a new model of computation, which has more power (that is, can decide more problems) than the classical Turing Machine.

By the way, some great lectures on this can be found here.

There isn't any evidence that the human brain is in fact anything more than a Turing machine. In fact, it seems like the entire universe can be simulated on a (sufficiently large) Turing machine.

Humans are "smart" because of smart algorithms that are cleverly written in neurons so computer scientists can't steal or efficiently implement them. However clever these algorithms are, they most likely cannot reliably solve the halting problem.

• "it seems like the entire universe can be simulated" -- no, it can't, because the uncertainty principle means we can't find out the initial state with enough accuracy to do so. We can simulate a universe by making arbitrary decisions about the initial state, but that is not necessarily a simulation of the universe. – Periata Breatta Sep 13 '16 at 5:36
• There also isn't any evidence that all thought is based upon evidence. It is a distinct possibility that Knowing is superior to proof, and that knowing based on evidence is a much lower-grade mental ability than knowing directly in a fashion not susceptible to proof. Must all knowledge be based upon evidence? What about creating new knowledge directly? – Wildcard Sep 13 '16 at 22:02
• A quote from the Madeleine L'Engle book "Many Waters" makes the point much more succinctly, even if considered merely as a possibility rather than a factual statement: "Some things have to be believed to be seen." If you enter the field of epistemology with the assumption that nothing exists unless proven to exist, you are placing arbitrary limits on the potential scope of knowledge. – Wildcard Sep 13 '16 at 22:05
• For the universe part, you need quantum in there, i.e. en.wikipedia.org/wiki/… – Fizz Nov 4 '17 at 8:23

In short: NO

there are Turing machines for wich we don (yet) know if those machines Halt (Collatz Conjecture in example).

Until we find a way to enumerate all Turing Machines for wich we don't have a Halting-proof, and until we don't find a way to proove Halt-ness of those machines we are not any better than a Turing machine (If I am correct someone already prooven that we cannot prove everything, a points toward the fact we are as limited as Turing Machines). Oh wait, we cannot enumerate all those machines because infact we have a limited memory and a limited lifespan.

You are asking if human are able to "decide", but the decision itself is defined as an algorithm, so or we run an algorithm on our minds and comes to a correct conclusion (or to no conclusion at all: open problems), or we just make a guess.

• Assume there exist a black box algorithm (Oracle) than can answer yes or no to certain questions
• You can then use it to answer unanswerable questions by building another algorithm that use it
• By doing that you ends with a contradiction

That means that as long you have any system that want a No or Yes answer, the Oracle is not compatible with that system, so Oracles may actually exists, but we have no way to communicate their results, because if we are able to communicate their results then we ends up with a contradiction somewhere.

Assume Quantum mechanics is made of many small oracles, then you cannot communicate their results because when you read the status of a particle, you also change the status of that particle.

Infact we can proove anything if we start from fake hypotesis. So we can proove that an algorithm halt, but we can also proove that an algorithm does not halt, that can be interesting, but it is useless since a contradictory (you want a Yes or No answer) result is not what you want.

• why downvotes? The fact that communicating the result of an oracle is not possible is a very deep and interesting point, that also answer the question. – GameDeveloper Jun 7 '16 at 15:42
• But don't you think Humans will eventually prove or disprove problems like Collatz Conjecture – Akshay L Aradhya Dec 30 '18 at 12:23

as with DCs answer (and to expand on it somewhat) there is a strong sense in which this question (combination of human and computer in finding special-case solutions to the halting problem) is related to the field of ATP, automated theorem proving and the closely related computer assisted proofs. also it has long been known there is a strong correspondence between programs and proofs in the Curry-Howard correspondence. also related/similar to this is proving program termination (eg via loop invariants or loop variants). in fact there is a deep sense in which all of mathematics is about this problem, because virtually all mathematical statements can be converted to questions about specific programs on TMs halting or not halting. see eg [2] for some further info & lots of further refs on ATP etc.

[1] is a semifamous book on the subject that examines the question in detail, relating it to the possibility artificial intelligence. briefly Penrose's idea is that true AI must be impossible because humans can come up with proofs of undecidability such as Turings halting problem or Godels incompleteness proof, whereas computers could not due to the same phenomena.

[1] Emperors new mind by Penrose

[2] adventures & commotions in ATM, vzn

• I don not undestand how can someone downvote this answer it links a lot of interesting material. +1 and +100 if only I could. – GameDeveloper Jun 7 '16 at 10:54

Modern supercomputer systems can certainly simulate the behavior of at least one atom. If individual atoms can be simulated then one can simulate the human mind as well by building a big enough computer system for the simulation of the individual atoms. However I think that this alone wouldn't be enough. You would also need an entropy source in order to obtain true random numbers for the simulation of the human mind. The best entropy source would probably be radioactive decay or something like that. What does this mean?

I think that the human mind is more powerful than a Turing Machine, because a TM is deterministic. You cannot simulate true randomness on a Turing Machine. (At least this is the impression, I got from the following discussion

https://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable

) However I think that a Turing Machine, attached to a true entropy source would be capable of simulating a human mind.

If one also takes the randomness of the environment into account, which interacts with a human mind (e.g. the food, we eat, how the sleep, walk, basically live our lives), then I certainly think that a TM with entropy is needed for the simulation of the human mind. Don't forget that the human mind is also constantly exposed to background radiation, which may also unpredictably interact with the molecules in our brain. But I think that even if we consider a completely "isolated" environment (Is that even possible? Because the following seems to indicate that it may not be possible: http://hps.org/publicinformation/ate/faqs/faqradbods.html ) - basically a "brain in the jar" - scenario, you would probably still get truely random processes, which would occur somethere in the human brain. I'm sure that a biologist could settle this part of the question? Also don't forget that a human is in a sense also part of his or her environment:

http://en.wikipedia.org/wiki/Human_Microbiome_Project

Perhaps some of these bacteria also influence the inner workings of the human brain in some way and the composition of this bacteria can change in a human's lifetime (also within certain boundaries I suppose?). The question is whether the behavior of these bacteria is random within certain boundaries. If at least one process within at least one of these organisms is truely random and also somehow indirectly affects the human brain then one would need a TM with an entropy source to simulate a human mind.

So to answer the original question:

Can a "human" (as defined in the question) solve the halting problem? Yes, if it is the halting problem for all deterministic TMs and no if it is for all TMs, attached to an entropy source.

• This seems very speculative. Essentially, you're saying that the human mind incorporates randomness, which means it's not a Turing machine, which means it might be able to decide the halting problem? – David Richerby Nov 10 '14 at 9:35
• It is probably correct that a computer can simulate what we know of atoms. But how would you know that what we know is all there is to be known? Then randomness is nice: if you wait long enough, if will come up with the right answer ... among many others. Just use enough monkeys for long enough, or look up the right book in the library of Babel. But getting the right answer is not all: how do you know it is the right anwer? – babou Nov 10 '14 at 11:32
• Non determinstic turing machines are not more powerfull than turing machines. Randomness is not enough to become superior to Turing Machines. See my answer – GameDeveloper Jun 7 '16 at 15:47

All human thought conflates single problems into personal experience. We might satisfy ourselves that we have adequately solved a problem sufficiently to halt, but we never know for sure in the algorithmic sense a computer would acquire a solution. Be still and watch your own mind. 99.9% of the messaging going on in our neural circuitry has nothing to do with a logical representation of the world. Instead, we are dealing with "gut" feelings, sensory data and a flood of memories, associations and attitudes which vary constantly. That's why we have scientific method.

• I think you misunderstood the question. The question is whether humans can decide whether a given Turing machine halts, which doesn't really have anything to do with "solving a problem sufficiently to halt". Do you mean that we can be "sufficiently convinced" the machine is going to halt? – Tom van der Zanden Jul 24 '15 at 10:16