A probabilistic anytime algorithm for the halting problem

DOI10.3233/COM-170073zbMath1394.68260OpenAlexW2614456850MaRDI QIDQ4683154

Monica E. Bad Dumitrescu, Cristian S. Calude

Publication date: 20 September 2018

Published in: Computability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/com-170073

zbMATH Keywords

halting problemanytime algorithmrunning time distribution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability distributions: general theory (60E05) Undecidability and degrees of sets of sentences (03D35) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

Computable model discovery and high-level-programming approximations to algorithmic complexity ⋮ Superintelligence Cannot be Contained: Lessons from Computability Theory

This page was built for publication: A probabilistic anytime algorithm for the halting problem