What is undecidability

Question

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

Answer 1

In principle, there might be a notion of computability that goes beyond the notion of Turing computability. That there is not is usually called the Church-Turing Thesis. There is an enormous amount of evidence for the Church-Turing Thesis. But unless we declare that by definition computable means Turing computable, the Thesis cannot be proved, since it says that a certain informal notion (computability) coincides with a formal notion.

Answer 2

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.

Answer 3

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer.

A decision problem is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem equivalently as the set of inputs for which the problem returns yes. These inputs can be natural numbers, but also other values of some other kind, such as strings of a formal language. Using some encoding, such as a Gödel numbering, the strings can be encoded as natural numbers. Thus, a decision problem informally phrased in terms of a formal language is also equivalent to a set of natural numbers. To keep the formal definition simple, it is phrased in terms of subsets of the natural numbers.

Formally, a decision problem is a subset of the natural numbers. The corresponding informal problem is that of deciding whether a given number is in the set. A decision problem A is called decidable or effectively solvable if A is a recursive set. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set. Partially decidable problems and any other problems that are not decidable are called undecidable.

Answer 4

First, yes, to your question "Does it mean that humans can never invent a new technique that always decides whether a Turing machine will halt?", mostly because the rules of the game have been set: the formalism of TMs. (at this point it will be helpful to actually go into some of those details and see the construction that shows that assuming the existence of such a TM that checks for halting results in a contradiction).

But even so, suppose you were given such a magical 'new technique'...this has been investigated under the name 'oracle'...even with an oracle that decides if a TM can halt on given input, it turns out that there are still problems that can't be solved with a TM (by pretty much a similar paradoxical construction that showed that the plain old halting problem is undecidable).

Aside from all that, there are two general difficulties with the halting problem that might lead to misunderstanding (if ignoring the technical details): knowing what is being quantified over, and dealing with infinity.

• what is asked for is an algorithm (to be implemented on a TM) that takes as input the specs for another TM and a parameter and is supposed to return the answer to the questions 'Does the given TM halt for the given input parameter?'. The point is that, even though you might be able to show for a particular TM that it halts (or does not) on the given input, but you're suppose to be able to show it for -any- TM. That's kind of a tall order.

• the other problem is, for an input that doesn't halt on the given TM...well, you don't know that ahead of time, so how do you know if the TM is going on forever, or just taking a really long time? You can't run things for as long as you want (that's sort of the definition of infinite). So -that's not a possible strategy, to check for -nonhalting- by simulating.

Given the main result (there's no general algorithm that will show for -any-TM if it halts on a given input), it turns out, possibly in the direction you're looking for, that for many subclasses of all possible TMs, there -are- algorithms that can decide if one will halt or not. That is, maybe if you restrict your formalism a little bit, there just might be a compiler (the halting problem TM for this subclass) that will tell you if you have some annoying infinite loops in there (does not halt for some input).