Autosolvability of halting problem instances for instruction sequences
| Authors | |
|---|---|
| Publication date | 2009 |
| Number of pages | 18 |
| Publisher | Ithaca, NY: ArXiv |
| Organisations |
|
| Abstract | We position Turing's result regarding the undecidability of the halting problem as a result about programs rather than machines. The mere requirement that a program of a certain kind must solve the halting problem for all programs of that kind leads to a contradiction in the case of a recent unsolvability result regarding the halting problem for programs. In this paper, we investigate this autosolvability requirement in a setting in which programs take the form of instruction sequences. |
| Document type | Report |
| Published at | http://arxiv.org/abs/0911.5018 |
| Downloads |
319472.pdf
(Submitted manuscript)
|
| Permalink to this page | |
