[Math] undecidability

computabilitycomputer science

What does it mean that some problem is undecidable?

For instance the halting problem.

Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?

If not, what techniques are allowed such that halting problem is still undecidable?

For instance induction is a good technique, why cant one discover some new technique?

I have trouble understanding how some new invention cannot solve the halting problem.

Given some computer and a program, is there really insufficient information stored in it to determine if it will halt?

It seems like a purely mechanical problem

Best Answer

Let me start by noting that if there were a simple algorithm to solve the halting problem, much of modern mathematics would be completely different. For instance, consider the following program:

  1. n = 2

  2. Test whether 2n is a sum of two primes. If not, exit. Otherwise, n = n+1 and go to step 1.

Whether this program halts is equivalent to Goldbach's conjecture! So the halting problem is a pretty sweeping thing. So the reason that this problem is unsolvable is not that there is too little information encoded in it, but far too much.

The unsolvability of the halting problem means specifically that there is no Turing machine that, when presented with the input of another Turing machine (in any reasonable description) and some input, will determine whether the input Turing machine will halt on the input string (and always output a yes or no answer in a finite amount of time). This does not, of course, preclude people from finding specific ways to prove that specific Turing machines halt or do not halt, but means that there is no general way (at least, insofar as "way" means "method that a Turing machine can emulate") that will work for any such program.