65
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 19
    $\begingroup$ 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. $\endgroup$
    – Carl Mummert
    Aug 21, 2012 at 11:58
  • 6
    $\begingroup$ @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. $\endgroup$
    – bitmask
    Aug 21, 2012 at 12:05
  • 6
    $\begingroup$ @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. $\endgroup$
    – bitmask
    Aug 21, 2012 at 14:52
  • 8
    $\begingroup$ 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. $\endgroup$
    – Patrick87
    Aug 23, 2012 at 22:16
  • 6
    $\begingroup$ Humans like to think of themselves as more than just ugly bags of mostly water. In their arrogance they dare compare themselves with Turing machines. This is a bit like an antilope thinking it could overtake a Ferrari. $\endgroup$
    – Andrej Bauer
    Feb 8, 2013 at 14:21

11 Answers 11

Reset to default
32
$\begingroup$

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

Improve this answer
$\endgroup$
11
  • 2
    $\begingroup$ 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). $\endgroup$
    – Olivier Lalonde
    Mar 23, 2014 at 20:13
  • $\begingroup$ @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. $\endgroup$
    – Dávid Natingga
    Oct 28, 2014 at 22:01
  • $\begingroup$ @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.) $\endgroup$
    – Keen
    Nov 12, 2014 at 17:06
  • $\begingroup$ @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. $\endgroup$
    – Dávid Natingga
    Nov 13, 2014 at 20:27
  • 2
    $\begingroup$ @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. $\endgroup$
    – Keen
    Dec 15, 2014 at 20:42
17
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – babou
    Nov 10, 2014 at 9:46
  • $\begingroup$ 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. $\endgroup$
    – Wildcard
    Jun 7, 2016 at 9:25
  • $\begingroup$ 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. $\endgroup$
    – Timothy
    Aug 30, 2018 at 2:17
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Non-christian is not synonymous with atheist. $\endgroup$
    – ubadub
    Dec 10, 2018 at 3:33
  • $\begingroup$ @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? $\endgroup$
    – babou
    Dec 10, 2018 at 10:48
  • $\begingroup$ 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). $\endgroup$
    – ubadub
    Dec 10, 2018 at 14:41
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "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. $\endgroup$
    – Periata Breatta
    Sep 13, 2016 at 5:36
  • 1
    $\begingroup$ 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? $\endgroup$
    – Wildcard
    Sep 13, 2016 at 22:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Wildcard
    Sep 13, 2016 at 22:05
  • $\begingroup$ For the universe part, you need quantum in there, i.e. en.wikipedia.org/wiki/… $\endgroup$
    – the gods from engineering
    Nov 4, 2017 at 8:23
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I don not undestand how can someone downvote this answer it links a lot of interesting material. +1 and +100 if only I could. $\endgroup$
    – CoffeDeveloper
    Jun 7, 2016 at 10:54
2
$\begingroup$

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.

However you question, is self-answering:

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.

Computation theory is about:

  • 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.

I had the answer, but I've read it..

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – CoffeDeveloper
    Jun 7, 2016 at 15:42
  • $\begingroup$ But don't you think Humans will eventually prove or disprove problems like Collatz Conjecture $\endgroup$
    – DollarAkshay
    Dec 30, 2018 at 12:23
0
$\begingroup$

Short Answer

Basically no in the general case (at least, not without guessing). Though, certain subproblems are indeed solvable.

Long Answer

In order for this to happen, you would have to assume that a human has the ability to solve mathematical problems that a TM can't in some algorithmic way. This would imply that the Church-Turing thesis is false, even though, TMK, it has been shown to be true for every known computational method discovered so far (except maybe probabilistic/quantum computation, which no longer meets the firm criteria for 'algorithm' since it involves inexact results).

However, there are indeed solvable subsets of the halting problem, such as determining whether or not a TM will halt within a certain number of computational steps (think 'ticks') upon a given input, which would be reasonably doable for both a TM and a human.

Though, considering how poor the general populus is at performing any sort of mathematics, you might get your answer of 'no' in a much different way.

Epilouge

You should look up a proof of the halting problem's unsolvability. There is at least 1 exceedingly simple proof that gives an example of a machine who's halting state cannot be properly predicted given the machine itself as an input, which serves as a counterexample to the very existence of an arbitrary machine that could solve the halting problem in the general case (for TM's).

Improve this answer
$\endgroup$
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 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? $\endgroup$
    – David Richerby
    Nov 10, 2014 at 9:35
  • $\begingroup$ 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? $\endgroup$
    – babou
    Nov 10, 2014 at 11:32
  • 1
    $\begingroup$ Non determinstic turing machines are not more powerfull than turing machines. Randomness is not enough to become superior to Turing Machines. See my answer $\endgroup$
    – CoffeDeveloper
    Jun 7, 2016 at 15:47
-2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – Tom van der Zanden
    Jul 24, 2015 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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