Timeline for Gödel's Incompleteness Theorem and the complexity of arithmetic
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 3, 2010 at 15:40 | comment | added | Hans-Peter Stricker | When we consider the natural numbers as an infinite directed graph, what are the properties of this graph, that enable it to simulate computation, and that other infinite graphs do not have? What are its sufficient and what are its necessary properties? (Infinitely many distinguishable (=adressable) nodes?) | |
| Sep 3, 2010 at 13:12 | comment | added | Stefan Geschke | Comment continued: In order to prove the existence of a function $n\mapsto\psi_n$ you would usually need to show that you can actually "simulate" computation in your structure in one way or other. | |
| Sep 3, 2010 at 13:11 | comment | added | Stefan Geschke | One rigorous definition would be the following (I know that this looks almost silly, but this is a general criterion that I can come up with): There is a computable function $f$ assigning to each natural number (or description of a Turing machine, if you wish) $n$ a sentence $\psi_n$ in the language of the structure such that the structure satisfies $\psi_n$ iff the Turing machine with Goedel number $n$ halts on the empty tape. Such a function exists in case of the natural numbers, namely, let $\psi_n=\varphi(t_n)$. | |
| Sep 3, 2010 at 11:07 | comment | added | Hans-Peter Stricker | How could "simulate (or express) computation" be defined rigorously? | |
| Sep 3, 2010 at 10:46 | history | answered | Stefan Geschke | CC BY-SA 2.5 |