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