What is undecidability
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
Solution 1:
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:
n = 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.
Solution 2:
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.
Solution 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.