On Approximating Real-World Halting Problems

摘要

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 Goedelization (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 Goedelization 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 Goedelization, this constant lower bound e 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].