Timeline for Has decidability got something to do with primes?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 3, 2023 at 1:26 | comment | added | Kaveh | If I remember correctly, encoding and decoding can be done even in Robinson's $Q$. Need to define a cut to restrict the non-standard numbers to those that are well-behaved enough. web.math.princeton.edu/~nelson/books/pa.pdf | |
| Mar 8, 2018 at 18:25 | comment | added | Joshua Grochow | @AndrejBauer: You don't even need the prime 2. You could use the base $n$ expansion for any $n$ (such as $n=10$), regardless of whether it's prime... The main thing you're relying on is that $n^k > \sum_{i=0}^{k-1} n^i$ for any natural numbers $n,k$. | |
| Jan 26, 2017 at 22:08 | history | edited | Gerry Myerson | CC BY-SA 3.0 |
deleted improper apostrophe
|
| Apr 10, 2010 at 22:15 | comment | added | John Stillwell | See Raymond Smullyan's Theory of Formal Systems (Princeton University Press, 1961). | |
| Apr 10, 2010 at 17:05 | vote | accept | abcdxyz | ||
| Apr 2, 2010 at 9:58 | comment | added | abcdxyz | May you refer me to some source of different arithmetization that does not rely on Chinese Remainder theorem? | |
| Apr 2, 2010 at 8:57 | comment | added | Andrej Bauer | To poke further holes in your dream, observe that arithmetization can be done with finite binary strings (just 0's and 1's). To encode and talk about such strings in the language of natural numbers you only need to know about the properties of the prime number 2, not all of them. Perhaps you just have to see an alternative arithmetization that does not rely on the Chinese Remainder theorem. | |
| Mar 30, 2010 at 18:20 | comment | added | abcdxyz | I am in a dilemma, it would be nicer if the answer is yes. On one hand I believe in you. On the other hand, I want to hold to the fleeting dream. :D So I wait. | |
| Mar 30, 2010 at 18:05 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |