Turing began by defining what is computable. He said, in essence, that a theorem is computable if it can be proven in a finite amount of time by a Turing machine. If a theorem requires an infinite amount of time on a Turing machine, then, for all intents and purposes, the theorem is not computable, and we don’t know if the theorem is correct or not. Therefore, it would not be provable. Simply put, Turing then expressed the question raised by Gödel in a concise form: Are there true statements that cannot be computed in a finite amount of time by a Turing machine, given a set of axioms? Like the
...more
