On approximating real-world halting problems
Fundamentals of Computation Theory: 15th International Symposium, FCT 2005 …, 2005•Springer
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 …
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 …
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].
Springer