Why the halting problem is unsolvable

Use proof-by-contradiction to draw that no such algorithm can exist.

  • 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.