Timeline for Models of computation with decidable halting problem?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2011 at 16:34 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Added ITRM example
|
| Jun 16, 2011 at 16:11 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Various improvements
|
| Jun 16, 2011 at 15:35 | comment | added | Joel David Hamkins | I agree. The classical argument that I mention runs program $q$ on input $q$ and then modifies its behavior based on the outcome, and this is an explicit use of a universal program. | |
| Jun 16, 2011 at 15:21 | comment | added | David Harris | This seems to depend more on having universal programs, rather than the halting set being decidable. In any reasonable model of computation, the set of programs can be coded as natural numbers. In this sense, the halting problem is always well-defined. For example, in primitive recursion, the halting problem is decidable by a primitive recursive function (trivially). However, primitive recursion does not have a universal program. | |
| Jun 16, 2011 at 12:58 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |