Timeline for Can a model of "true computation" exist? What would be its consequences?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 2, 2023 at 3:26 | history | suggested | CommunityBot | CC BY-SA 4.0 |
fixing the grammar in the subject line; adding some MathJax
|
| Oct 1, 2023 at 18:19 | review | Suggested edits | |||
| S Oct 2, 2023 at 3:26 | |||||
| Oct 1, 2023 at 13:17 | comment | added | Andreas Blass | Since statements about Turing machines can be coded in arithmetic and vice versa, I see no significant difference between "true computation" and "true arithmetic". I think any difference would have to be created by imposing some (artificial) restrictions on the expressive power of one of the two theories. (This might have been the reason for @C7X's Comment, asking about the expressive power.) | |
| Oct 1, 2023 at 8:10 | review | Close votes | |||
| Oct 8, 2023 at 3:09 | |||||
| Oct 1, 2023 at 7:01 | comment | added | symmetrickittens | @C7X Good point. It seems that this set of statements will have to contain TA in some way for many statements about halting to be well-defined. Honestly I'm not picky about how to define the set, as long as the Motivation is fulfilled. | |
| Oct 1, 2023 at 6:17 | comment | added | C7X | Which kinds of statements are considered "first-order statements about Turing machines"? (E.g. are statements of the form "Turing machine X halts on all inputs" considered? Are statements of the form "Turing machine X halts for sufficiently large inputs X" considered?) | |
| S Oct 1, 2023 at 5:13 | review | First questions | |||
| Oct 1, 2023 at 5:44 | |||||
| S Oct 1, 2023 at 5:13 | history | asked | symmetrickittens | CC BY-SA 4.0 |