12/24/10

Halting Problem, Gödel's Proof and Liar Paradox


boolean functions
return
true or false
or never halt:

bool x() { return !x(); }

and algorithms
can't always decide
which of the 3 it is:

bool x() {
return !returnsTrue("x()"); }


Halting Problem

propositions
can be proven
true or false
or can't be proven:

x := ¬x

and math
can't always prove
which of the 3 it is:

x := ¬provable("x")


Gödel's Proof

statements
can be reasoned
true or false
or can't be reasoned:

this statement is false

and humans
can't always reason
which of the 3 it is:

this statement is not true


Strengthened Liar