Asymptotic proportion of hard instances of the halting problem

DOI10.14232/ACTACYB.21.3.2014.3MaRDI QIDQ2937541zbMATHOpenAlexFDO

Authors Antti Valmari

Publication date 9 January 2015

Published in Acta Cybernetica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.7066

zbMATH Keywords

halting problemapproximating testergeneric-case testerthree-way tester

Mathematics Subject Classification ID

Theory of programming languages (68N15)

Abstract: 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.

Recommendations

• The halting problem is decidable on a set of asymptotic probability one
• A probabilistic anytime algorithm for the halting problem
• Generic algorithms for halting problem and optimal machines revisited
• Most programs stop quickly or never halt
• A statistical anytime algorithm for the halting problem

Cited in

(4)

• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 4049059 (Why is no real title available?)
• What percentage of programs halt?
• scientific article; zbMATH DE number 5506884 (Why is no real title available?)

This page was built for publication: Asymptotic proportion of hard instances of the halting problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2937541)