History and Philosophy of Computing The Halting Problem and Uncomputability
Exercise 1 Construct the list of values for some initial segment of some list Si which is a subset of N.
Exercise 2 Cantor's Theorem states that there are more characteristic functions of sets than there are computable ones. Because we know that each computable function corresponds to the program of a Turing Machine, the theorem says something of programs as well. Explain what informally.
Exercise 3 You have written some algorithm, you launch it and it starts running, eventually for days. How do you know if it will ever stop? Should you wait? If you are looking to assess the syntax of the program for possible reasons, what would you look for?
Exercise 4 Who proved that the halting problem was impossible to solve, and when?
Exercise 5 Can you tell if the following program halts or not? Why?
def f ( int n)
if (n == 0 )
return 1
else return n * (f ( n -1))
end
end
Exercise 6 Can you tell if the following program halts or not? Why?
def f ( int n)
if (n < 0 )
do f( n + 2 )
elsif ( n > 0 )
do f( n - 2)
end
end
Exercise 7 Can you tell if the following program halts or not on any input? Try with some large input, e.g. 156:
void f( int x) {
while (x > 1 ) {
if (x % 2 == 1 )
do x = 3*x + 1;
else
do x = x / 2 ;
}
}
When do you think it is safe to stop a computation to say it will not halt?