Incompleteness Ex Machina

Sebastian Oberhoff, The Logic in Computer Science Column by Yuri Gurevich


In this essay we’ll prove Gödel’s incompleteness theorems twice. First, we’ll prove them the good old-fashioned way. Then we’ll repeat the feat in the setting of computation. In the process we’ll discover that Gödel’s work, rightly viewed, needs to be split into two parts: the transport of computation into the arena of arithmetic on the one hand and the actual incompleteness theorems on the other. After we’re done there will be cake.

Full Text:



  • There are currently no refbacks.