Asymptotic proportion of hard instances of the halting problem

Valmari Antti: Asymptotic proportion of hard instances of the halting problem. In: Acta cybernetica, (21) 3. pp. 307-330. (2014)

[thumbnail of actacyb_21_3_2014_3.pdf]
Cikk, tanulmány, mű

Download (256kB) | Preview


Although the halting problem is undecidable, imperfect testers that fail on some instances are possible. Such instances are called hard for the tester. One variant of imperfect testers replies "I don't know" on hard instances, another variant fails to halt, and yet another replies incorrectly "yes" or "no". Also the halting problem has three variants: does a given program halt on the empty input, does a given program halt when given itself as its input, or does a given program halt on a given input. The failure rate of a tester for some size is the proportion of hard instances among all instances of that size. This publication investigates the behaviour of the failure rate as the size grows without limit. Earlier results are surveyed and new results are proven. Some of them use C++ on Linux as the computational model. It turns out that the behaviour is sensitive to the details of the programming language or computational model, but in many cases it is possible to prove that the proportion of hard instances does not vanish.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2014
Volume: 21
Number: 3
ISSN: 0324-721X
Page Range: pp. 307-330
Language: English
Place of Publication: Szeged
Event Title: Symposium on Programming Languages and Software Tools (2013) (Szeged)
Related URLs:
DOI: 10.14232/actacyb.21.3.2014.3
Uncontrolled Keywords: Számítástechnika
Additional Information: Bibliogr.: p. 329-330. és a lábjegyzetekben ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 17. 10:38
Last Modified: 2022. Jun. 20. 09:29

Actions (login required)

View Item View Item