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.