MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I think I do not understand. What does it mean that "an algorithm consumes an infinite sequence of bits"? What do you mean by an "algorithm"? If you think of a Turing machine $T$ that starts with an infinite input tape, than obviously the set $P$ of input sequences that make $T$ to return true have to be of the form: $P = L \\circ \\{0, 1\\}^\\inf$, for a pratially recursive language $L$, and the set $N$ that make $T$ to loop forever have to be of the same form, where now $L$ is co-partially recursive. In such a case $S$ cannot be unique unless $L$ is recursive. – Michal R. Przybylek May 12 '11 at 14:06
up vote 7 down vote accepted

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.

share|cite|improve this answer
This seems to be right. Thanks! – Vladimir Slepnev May 12 '11 at 14:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.