Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
8  
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
2  
@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
1  
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
2  
@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
2  
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

9 Answers 9

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.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments

share|improve this answer
    
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 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. –  David Toth Oct 28 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.) –  Cory Nov 12 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. –  David Toth Nov 13 at 20:27
    
@Cory I think even small changes in initial/intermediate states may result in big final changes, consider Game of Life and other examples from en.wikipedia.org/wiki/Chaos_theory. –  David Toth Nov 13 at 20:28

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.

share|improve this answer
    
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 at 9:46

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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 methaphysical question as we have strictly no handle on it, no hint whatsoever of what could differentiate a human from a machine. So this question shoud 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 atheist 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.

share|improve this answer

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

share|improve this answer

The other answers are talking about the complexities of the human mind, which seems to me to be irrelevant.

Is it OK to rephrase the question as the following?

I interpret the undecidability of the Halting Problem to imply that there exists a set of program-input pairs for which the program DOES halt and this property can only be discovered by unabbreviated execution. It also implies another set of program-input pairs for which the program DOES NOT halt and that this property cannot be computed.

Based on that interpretation, I wonder whether there are any pairs from either set which a human could statically analyze and know with 100% accuracy - or possibly even prove, if this "big picture" intuitive perspective is such an advantage - whether those programs halt or not.

Perhaps the interpretation is incorrect - it is how I imagine @bitmask is thinking.

Regarding assisted theorem provers, from what I've read of such provers, it's not that the algorithm needs human intuition exactly, it's just that the search space is so vast as to be impractical. The human just helps narrow the search space for choices for which we don't yet have good heuristics. But I have no experience in many of these matters. Perhaps someone can comment on this as well?

share|improve this answer
    
Maybe I'm misinterpreting your doubts, but I think there are plenty of cases in which it's possible to prove a given TM halts or doesn't halt on certain inputs. It's a problem in the general case, but in lots of specific cases, it's quite possible. –  Patrick87 Aug 22 '12 at 15:51
    
Yes, agreed. I just did not mention the third set of program-input pairs for which the halt-property can be known. –  uosɐſ Aug 22 '12 at 16:50
1  
"Based on that interpretation, I wonder whether there are any pairs from either set which a human could statically analyze and know with 100% accuracy - or possibly even prove, if this "big picture" intuitive perspective is such an advantage - whether those programs halt or not." I believe this wouldn't prove that human brains are more powerful then Turing machines. You would have to prove that human brains can decide whether a program will halt or not for any given program (not just a subset of all possible programs). –  Olivier Lalonde Mar 23 at 20:17

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

http://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.

share|improve this answer
1  
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 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 at 11:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.