SA
Skip to main content

Halting Problem

2022-05-11

  • Imagine there is a function bool doesItHalt({function f, input i}) that returns if the parameter function f(i) halts or not.
  • Now consider the following functions:
pair duplicator(input i) {
return {i, i}
}

bool invertHalt(bool b) {
if(b) {
while(true); // hangs forever
return 0;
} else {
return 0;
}
}
  • Essentially, if f(i) halts, the invertHalt will hang (i.e., wouldn't halt), and if f(i) hangs, the invertHalt will halt.
  • Let us consider the composition of the two functions:
bool unknown(input i) {
auto a = duplicator(i) // a = {i, i}
auto b = doesItHalt(a) // does i(i) halt?
auto c = invertHalt(b) // hangs if i(i) halts and vice versa.
}
  • Will unknown(unknown) halt? What should doesItHalt({unknown, unknown}) return?
  • Let us suppose it will return true. Then, it means that doesItHalt({unknown, unknown}) returned false because invertHalt(b) would've hung otherwise. Therefore, this contradicts our supposition that doesItHalt({unknown, unknown}) returns true.
  • Let us suppose it will return false. Then, it means that doesItHalt({unknown, unknown}) would return true because invertHalt wouldn't hang otherwise. Therefore, this contradicts our supposition that doesItHalt({unknown, unknown}) returns false.
  • Therefore, unknown cannot hang nor halt; therefore, no such doesItHalt can exist.

Links to This Note