A statistical anytime algorithm for the Halting Problem

DOI10.3233/COM-190250zbMath1485.68119MaRDI QIDQ5131647

Monica E. Bad Dumitrescu, Cristian S. Calude

Publication date: 9 November 2020

Published in: Computability (Search for Journal in Brave)

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

zbMATH Keywords

order statistics; halting problem; anytime algorithm; running time

Mathematics Subject Classification ID

60E15: Inequalities; stochastic orderings

68W40: Analysis of algorithms

62G30: Order statistics; empirical distribution functions

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Computable model discovery and high-level-programming approximations to algorithmic complexity