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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ 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. $\endgroup$– Michal R. PrzybylekCommented May 12, 2011 at 14:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered May 12, 2011 at 14:25