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.

  • 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$ Jan 30, 2014 at 15:02
  • $\begingroup$ We have a reference question that gives you several proofs for the first question. $\endgroup$
    – Raphael
    Jan 30, 2014 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, 2014 at 22:19

2 Answers 2


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.

  • 1
    $\begingroup$ Would a hypothetical hyper-computer require different universal constants? $\endgroup$
    – Igglyboo
    Jan 30, 2014 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$ Jan 30, 2014 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$ Jan 30, 2014 at 15:18
  • 1
    $\begingroup$ @RickDecker Right, this is known as recursion theory. $\endgroup$ Jan 30, 2014 at 17:22
  • 1
    $\begingroup$ @YuvalFilmus What do you think of this book amazon.com/…? $\endgroup$
    – Turbo
    Aug 6, 2015 at 12:08

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
  if there exists two primes p and q and p + q = n then
    n = n + 2
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).


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