2
$\begingroup$

This question already has an answer here:

So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable.

So any human can determine if a problem halts with rigorous inspection, so why can't a very advanced, say human AI, solve the halting problem?

Also, is there a machine, say more powerful than a turing machine, that can solve this problem?

PS: I might be making some bad assumptions, please point that out if so.

$\endgroup$

marked as duplicate by D.W., vonbrand, Luke Mathieson, Guy Coder, A.Schulz Feb 11 '14 at 11:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ It's undecidable because there is a well-known proof of this fact. Is there some aspect of the proof you'd like help with? As for humans, does this program halt for all positive integer input $x$? while (x!=1) { if (x is even) { x = x/2; } else { x = 3*x + 1;}} $\endgroup$ – David Richerby Jan 30 '14 at 15:02
  • $\begingroup$ We have a reference question that gives you several proofs for the first question. $\endgroup$ – Raphael Jan 30 '14 at 15:20
  • $\begingroup$ the general problem is unsolvable but the precise boundary between decidable and undecidable languages is an area of very active/open research.... in other words algorithms to analyze halting problems are getting better all the time via advancing research see eg adventures in ATP.... $\endgroup$ – vzn Jan 31 '14 at 22:19
6
$\begingroup$

It can be proved that the halting problem cannot be solved by any Turing machine. There are several question regarding this on this side which you can look up.

It is not true that humans can determine if a given Turing machine halts. For example, we have been unable so far to compute many values of busy beaver functions, which measure the maximal number of steps a halting Turing machine can run given the number of tape symbols and number of states.

According to the Church–Turing thesis, every machine can be simulated by a Turing machine. So DNA computers, quantum computers and the like will not help. All they can do (especially the latter) is to dramatically speed up computation, but they cannot help computing non-computable functions.

There is a field known as hyper-computation which studies machines stronger than Turing machines, but these are not believed to be realizable by most practitioners. Recursion theory explores such models from a more theoretical perspective.

$\endgroup$
  • 1
    $\begingroup$ Would a hypothetical hyper-computer require different universal constants? $\endgroup$ – Igglyboo Jan 30 '14 at 14:31
  • 1
    $\begingroup$ I have no idea. You can explore hypercomputation via Wikipedia, Google, Bing, or any other means of your choice, for example you could go to conferences on the subject. $\endgroup$ – Yuval Filmus Jan 30 '14 at 14:32
  • 1
    $\begingroup$ One could also use a suitable oracle machine to solve the Halting Problem. While oracle machines are also somewhat "bogus" in the sense that hypercomputation is, they're much more studied, as you know. $\endgroup$ – Rick Decker Jan 30 '14 at 15:18
  • 1
    $\begingroup$ @RickDecker Right, this is known as recursion theory. $\endgroup$ – Yuval Filmus Jan 30 '14 at 17:22
  • 1
    $\begingroup$ @YuvalFilmus What do you think of this book amazon.com/…? $\endgroup$ – Turbo Aug 6 '15 at 12:08
7
$\begingroup$

The major bad assumption is that "any human can determine if a problem halts with rigorous inspection". The strong Goldbach conjecture states that every even integer greater than 2 can be expressed as the sum of two primes. So consider the following program.

n = 4
loop
  if there exists two primes p and q and p + q = n then
    n = n + 2
  else
    return
  endif
end loop

The program loops until it finds an even integer that can't be expressed as the sum of two primes. So if it halts, the conjecture is proven false. If indeed "any human could determine if a program halts", we could settle this, and several other famous conjectures (at least theoretically).

$\endgroup$

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