Re: why is halting problem profound?

shimp wrote:
Is this non-obvious to some people? The wording of the theorem is so
abstract and it says nothing about the kind of code or instructions that
the machine is allowed to execute. It could do, or be, anything. No way
you can know until you run it.

First, most expositions of the theorem do assume a specific (theoretical) programming language, e.g. Turing machines. However, it doesn't really matter: all interesting programming languages to which the theorem applies are equivalent.

Second, it is not true that running a program is the only way you can know whether or not it halts. There exist so-called static analysis techniques with which you can prove properties of a program without ever running it.

Consider for example Euclides' algorithm to calculate the greatest common divisor:

function gcd(a, b) {
if (a = b) then
return b
else if (a > b) then
return gcd(a-b, b)
else
return gcd(a, b-a)
}

Since the sum of the arguments of the function strictly decreases in each recursive function call, we know that this algorithm terminates for all inputs, *without ever running it*.

It could be the case that some static analysis technique would exist that yields the correct answer in all cases. Turing proved that this is not the case. Arguably, the halting theorem is obvious in 2008 (at least, every computer scientist knows it), but in the 1930s it wasn't.

groente
-- Sander
.

Loading