Timeline for Probability that a Turing machine is universal?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 12, 2021 at 20:56 | history | edited | Joel David Hamkins |
edited tags
|
|
| Jul 26, 2011 at 21:46 | vote | accept | twiz | ||
| Jul 26, 2011 at 21:46 | |||||
| Jul 25, 2011 at 10:32 | comment | added | twiz | I want to ask whether there exists a Turing machine that always halts and gives the correct answer, not whether that is provable in some axiomatization. I don't know if I understand your first question: My input tape has finite length (it exists in addition to the working tape, and it can be assumed that it is impossible to modify it), and I want to know whether it can be decided for all initial values on the input tape if it halts. If the input tape was always zero, the program would always halt or not halt, so there must exist a program that tells the correct result. | |
| Jul 24, 2011 at 23:19 | answer | added | Joel David Hamkins | timeline score: 21 | |
| Jul 24, 2011 at 20:56 | comment | added | David Harris | Undecidability is not a property of the axiomatic system, but an intrinsic property of certain subsets of $\omega$. The poster is asking whether one can decide this for all inputs to the Turing machine, so a distribution on inputs is not meaningful either. | |
| Jul 24, 2011 at 18:56 | comment | added | user5810 | Are the bits starting on the input tape also chosen at random, or are they all zero? For your first question, do you want undecidable in ZF or something else (like PA)? | |
| Jul 24, 2011 at 17:00 | history | asked | twiz | CC BY-SA 3.0 |