Timeline for Is there some kind of equivalence between Turing Machines and a formal system of axioms?
Current License: CC BY-SA 4.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 15, 2022 at 0:43 | comment | added | Charbel Bejjani | But for a sufficiently complex formal system, capable of coding basic arithmetic, the set of theorems in this system is not computable (enumerable but non-recursive) right? So I don't see how a Turing Machine could be equivalent to a (sufficiently complex) formal system. (since that machine could not deal with all the decidable propositions of the system) But then Penrose shows how Gödel's theorem can be stated purely in computational terms based on Turing Machines. So I guess I wanted to know at this point if there is an equivalence between the two? | |
| May 14, 2022 at 17:06 | history | answered | TomKern | CC BY-SA 4.0 |