Timeline for A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Mar 10, 2011 at 20:44 | comment | added | Joel David Hamkins | Q3. In the two-way infinite tape model, the current best theorem is not much better than the 13.5% from the no-transitions-to-halt-state argument. However, in the model where any state can be decreed halting, then you get the full theorem, because it is extremely likely to halt quickly, as you are likely to encounter a halting state quickly. So that model can handle the (program,input) situation. | |
| Mar 10, 2011 at 20:43 | comment | added | Joel David Hamkins | Q1. Yes, the model is universal; it is one of the completely standard models. Q2. The theorem in the paper is only for fixed input, but works with arbitrary input (even infinite input). For (program,input) pairs, the theorem is not as nice, and the full question is open. | |
| Mar 10, 2011 at 19:11 | comment | added | user13550 | "Proof of Main Theorem: We now prove the Main Theorem. Let B be the set of programs that on input 0 either halt before repeating a state or fall off the tape before repeating a state." Q3. This method will not work assuming we have a Two way infinite tape Universal Turing Machine. Thus, by definition of halting problem one should be able to comment on all UTM models. Is there any general method using which we can comment on the halting Probability of a Random <Program, Input> Pair ? | |
| Mar 10, 2011 at 19:09 | comment | added | user13550 | "Lemma 1.2 The collection of programs having no transition reaching the halt state has asymptotic probability 1/e2, which is about 13.5%." Q1. Is the model proposed in the proof a Universal Turing Machine i.e. we consider all the programs that are possible (with both repeating and non-repeating states) and all possible inputs ? Q2. A randomly chosen program might have a transition to the halt state, but as in original Query we have a random <Program, Input> Pair. But the current input might not lead to a halt state. Thus, input also effects the probability.? | |
| Mar 10, 2011 at 19:08 | comment | added | user13550 | Thanks a lot for your reply. But I have few doubts/issues regarding the explanation(paper) and it would be great if you could clarify. | |
| Mar 10, 2011 at 13:46 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |