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?



Finding inputs that make an algorithm run forever
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](http://en.wikipedia.org/wiki/K%C3%B6nig%27s_lemma#computability_aspects); 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](http://en.wikipedia.org/wiki/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.


