2012-02-20

Bengt vs. Turing

Bengt's friend Alban is an engineering student, and he's trying to show Bengt that he's not completely ignorant in the more theoretical fields. As we all know, that sort of showing off can be dangerous when Bengt is involved.
"...and so, there is no program which, for any given input program and starting values, determines whether that program stops." says Alban.
"There is too."
"What? No, there really isn't."
"Is too."
"Now you're being silly."
"How much memory does your computer have?"
"16 gig, why?"
"Imagine if you had infinitely big programs. The algorithm itself might be infinitely long, and it might use an infinite amount of memory. Could there be a program which for any such program determines whether it stops?"
"If it's infinite, it doesn't stop, does it?"
"It might. It could stop on the first line, even if it has infinitely many after that."
"Okay, fine. In that case, no, obviously."
"Obviously indeed. Now let's say the programs are not infinite. For example, they might be no bigger than your 16 gig. Or more generally, n bits. Program and variables included. Is it still impossible?"
"I think so... isn't that what the theorem says?"
"I sure hope it doesn't. I can do it in O(2n) time."
"That's an insanely long time."
"But not infinite."
"Not even a little?"
"Afraid not."

  1. It seems unlikely that Bengt has proven Turing wrong. Where is the leap in Bengt's reasoning?
  2. Given his somewhat special version of the halting problem, can you find a solution that runs in O(2n) time?
  3. Is there perhaps an even faster way? Can you find one that is faster than O(2n)? Or prove that there isn't one?
  4. Let's ignore Bengt's sneaky redefinitions, and try another modification to the original halting problem. Let A be a program that may or may not stop, and let B be a program trying to check whether A stops. Let f(A,B) be the statement "B can determine whether A stops". The theorem says that "∃B ∀A f(A,B))" (there is a B that works for every A) is false. But what about "∀A ∃B f(A,B)" (for every A there is a B that works)? Can we, for every program, find a testing program that checks if it stops? If A is also allowed to take a number as input, does that make a difference?