A probabilistic anytime algorithm for the halting problem
- 7 June 2018
- journal article
- research article
- Published by SAGE Publications in Computability
- Vol. 7 (2-3) , 259-271
Abstract
The Halting Problem, the most (in)famous undecidable problem, has important applications in theoretical and applied computer science and beyond, hence the interest in its approximate solutions. Experimental results reported on various models of compuKeywords
This publication has 26 references indexed in Scilit:
- Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing MachinesPLOS ONE, 2014
- Renormalisation and computation II: time cut-off and the Halting ProblemMathematical Structures in Computer Science, 2012
- Computer Runtimes and the Length of ProofsLecture Notes in Computer Science, 2012
- Proving program terminationCommunications of the ACM, 2011
- Most programs stop quickly or never haltAdvances in Applied Mathematics, 2008
- The Halting Problem Is Decidable on a Set of Asymptotic Probability OneNotre Dame Journal of Formal Logic, 2006
- On Approximating Real-World Halting ProblemsLecture Notes in Computer Science, 2005
- Reasoning about computational resource allocationXRDS: Crossroads, The ACM Magazine for Students, 1996
- Approximations to the halting problemJournal of Computer and System Sciences, 1974
- Nicht konstruktiv beweisbare Sätze der AnalysisThe Journal of Symbolic Logic, 1949