Given an algorithm A that consumes an infinite sequence of bits and can terminate at any point, it's straightforward to prove that either A's running time is uniformly bounded or there's an infinite bit sequence S that makes A run forever. I'm interested in the computability of S. When S is unique, I believe I know an algorithm to compute S given A. But what about the case when S is not unique? Does there exist an algorithm such that all input sequences that make it run forever are uncomputable?
|
|
There is such an algorithm, for which one cannot find a computable $S$ on which it runs forever. There is a computable tree with no computable infinite branch. See the Wikipedia entry on König's lemma; the existence of such trees shows that the computable analogue of König's lemma is false. That is, there is a decidable subset $T\subset 2^{\lt\omega}$ which forms an infinite finitely branching tree, and we can decide membership in $T$, but there is no computable infinite branch through $T$. Consider the algorithm that halts on strings not in $T$. Thus, the only way to make the algorithm run forever is to provide it with an infinite branch through $T$. But there is no computable such branch. Meanwhile, the low-basis theorem implies that there will be a sequence $S$ that is of low complexity. Consider the tree of all sequences $s$ on which the machine has not yet halted on them in $|s|$ steps. This is a computable tree, and if infinite, it will have a low branch. |
|||||
|
