Article

On approximating real-world halting problems

Authors:

Christian Schindelhauer,

Martin ZieglerAuthors Info & Claims

FCT'05: Proceedings of the 15th international conference on Fundamentals of Computation Theory

Pages 454 - 466

https://doi.org/10.1007/11537311_40

Published: 17 August 2005 Publication History

Abstract

No algorithm can of course solve the Halting Problem, that is, decide within finite time always correctly whether a given program halts on a certain given input. It might however be able to give correct answers for ‘most' instances and thus solve it at least approximately. Whether and how well such approximations are feasible highly depends on the underlying encodings and in particular the Gödelization (programming system) which in practice usually arises from some programming language.

We consider BrainF*ck (BF), a simple yet Turing-complete real-world programming language over an eight letter alphabet, and prove that the natural enumeration of its syntactically correct sources codes induces a both efficient and dense Gödelization in the sense of [Jakoby&Schindelhauer'99]. It follows that any algorithm M approximating the Halting Problem for BF errs on at least a constant fraction ε_M> 0 of all instances of size n for infinitely many n.

Next we improve this result by showing that, in every dense Gödelization, this constant lower bound ε to be independent of M; while, the other hand, the Halting Problem does admit approximation up to arbitrary fraction δ> 0 by an appropriate algorithm M_δ handling instances of size n for infinitely many n. The last two results complement work by [Lynch'74].

References

[1]

D.F. BAILEY: "Counting Arrangements of 1's and -1's", pp.128-131 in Mathematics Magazine vol.69 (1996).

[2]

R.V. BOOK: "Telly languages and complexity classes", pp.186-193 in Information and Control vol.26:2 (1974).

[3]

C.S. CALUDE, M.J. DINNEEN, C.-K. SHU: "Computing a Glimpse of Randomness", pp.361-370 in Experimental Mathematics vol.11:3 (2001).

[4]

C.S. CALUDE, P. HERTLING, B. KHOUSSAINOV, Y. WANG: "Recursively enumerable reals and Chaitin ω numbers", pp.125-149 in Theoretical Computer Science vol.255 (2001).

Digital Library

[5]

G.J. CHAITIN: Algorithmic Information Theory, Cambridge University Press (1987).

Digital Library

[6]

O. GOLDREICH: "Combinatorial property testing (a survey)", pp.45-59 in Proc. DIMACS Workshop in Randomized Methods in Algorithm Design (1997).

[7]

A. JAKOBY, C. SCHINDELHAUER: "The Non-Recursive Power of Erroneous Computation", pp.394-406 in Foundations of Software Technology and Theoretical Computer Science (FSTTCS 1999), Springer LNCS vol.1738.

Digital Library

[8]

S. KÖHLER: "Zur Approximierbarkeit des Halteproblems in einer praktischen Gödelisierung", Bachelor's Thesis, University of Paderborn (2004).

[9]

M. LI, P. VITÁNI: An Introduction to Kolmogorov Complexity and its Application, 2nd Edition, Springer (1997).

Digital Library

[10]

N. LYNCH: Approximations to the Halting Problem, pp.143-150 in J. Computer and System Sciences vol.9 (1974).

Digital Library

[11]

M. MACHTEY, P. YOUNG: An Introduction to the General Theory of Algorithms, The Computer Science Library (1978).

Digital Library

[12]

C.H. PAPADIMITRIOU: Computational Complexity, Addison-Wesley (1995).

[13]

H. ROGERS JR: Theory of Recursive Functions and Effective Computability, Mc-Graw Hill (1967).

[14]

G.F. ROSE, J.S. ULLIAN: "Approximation of Functions on the Integers", pp.693- 701 in Pacific Journal of Mathematics vol.13:2 (1963).

[15]

C.P. SCHNORR: "Optimal Enumerations and Optimal Gödel Numberings", pp.182- 191 in Mathematical Systems Theory vol.8:2 (1975).

[16]

C. SMITH: A Recursive Introduction to the Theory of Computation, Springer (1994).

Digital Library

[17]

R.I. SOARE: Recursively Enumerable Sets and Degrees, Springer (1987).

Digital Library

[18]

E. SPECKER: "Nicht konstruktiv beweisbare Sätze der Analysis", pp.145-158 in J. Symbolic Logic vol.14:3 (1949).

[19]

http://wikipedia.org/wiki/BrainFuck; Wikipedia, the free encyclopedia (2005).

Cited By

Alfonseca MCebrian M Fernandez Anta ACoviello LAbeliuk ARahwan I(2021)Superintelligence Cannot be ContainedJournal of Artificial Intelligence Research10.1613/jair.1.1220270(65-76)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1613/jair.1.12202
Younan YPhilippaerts PPiessens FJoosen WLachmund SWalter TAl-Shaer EJha SKeromytis A(2009)Filter-resistant code injection on ARMProceedings of the 16th ACM conference on Computer and communications security10.1145/1653662.1653665(11-20)Online publication date: 9-Nov-2009
https://dl.acm.org/doi/10.1145/1653662.1653665

Recommendations

Computing halting probabilities from other halting probabilities

The halting probability of a Turing machine is the probability that the machine will halt if it starts with a random stream written on its one-way input tape. When the machine is universal, this probability is referred to as Chaitin's omega number, and ...
Halting Stack Automata

It is shown that every two-way (deterministic) stack automaton language is accepted by a two-way (deterministic) stack automaton which for each input has a bound on the length of a valid computation. As a consequence, two-way deterministic stack ...
Index Problems for Game Automata

For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a nondeterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FCT'05: Proceedings of the 15th international conference on Fundamentals of Computation Theory

August 2005

576 pages

ISBN:3540281932

Editors:
Maciej Liśkiewicz
Institut für Theoretische Informatik, Universität zu Lübeck, Germany
,
Rüdiger Reischuk
Institut für Theoretische Informatik, Universität zu Lübeck, Ratzeburger Allee 160, Lübeck, Germany

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 August 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alfonseca MCebrian M Fernandez Anta ACoviello LAbeliuk ARahwan I(2021)Superintelligence Cannot be ContainedJournal of Artificial Intelligence Research10.1613/jair.1.1220270(65-76)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1613/jair.1.12202
Younan YPhilippaerts PPiessens FJoosen WLachmund SWalter TAl-Shaer EJha SKeromytis A(2009)Filter-resistant code injection on ARMProceedings of the 16th ACM conference on Computer and communications security10.1145/1653662.1653665(11-20)Online publication date: 9-Nov-2009
https://dl.acm.org/doi/10.1145/1653662.1653665

View Options

View options

Media

Figures

Other

Tables

View Table of Contents