I'm struggling with a problem that I believe I've managed to reduce to a question of Kolmogorov complexity for infinite strings, but since I'm not an expert in this field, I'm not sure about the correctness of the reasoning.

Let us consider an alphabet $A$, and the set of all infinite strings $A^\omega$. Intuitively, given a function $U$ and a set of inputs $P$ such that $U : P \to A^\omega$, there exists a string $s \in A^\omega$ such that for all $p \in P$ such that $U(p) = s$, the size of $p$ is infinite.

My reasoning is based on the Incomputability of Kolmogorov complexity section of the Wikipedia page:

Theorem: There exist strings of arbitrary large Kolmogorov complexity. Formally: for each n ∈ ℕ, there is a string s with K(s) ≥ n

In other words, if I want to be able to generate all infinite sequences of a given alphabet, then I need to consider at least one infinite inputs (and not only an infinite set of inputs). Is this correct?

  • $\begingroup$ I hope the question is suitable for Mathematics.SE, I'm not sure if the result is trivial or not. Otherwise, I'm happy to have it moved to other sites. $\endgroup$ – Charles Mar 20 '14 at 13:52
  • $\begingroup$ A universal Turing machine only reads and works with finite programs. It's somewhat self-contradictory to talk about "infinite programs" in the theory of Turing machines. $\endgroup$ – Carl Mummert Mar 20 '14 at 14:17
  • $\begingroup$ @CarlMummert: Thanks, that's a good point. Does it change the reasoning if I change "given an universal turing machine U" by "given any function U"? (which is actually the setting of my problem, not a UTM). $\endgroup$ – Charles Mar 20 '14 at 14:21
  • 1
    $\begingroup$ that is what Henning Makholm is addressing in his answer; it would be true if $U$ was replaced by any function. $\endgroup$ – Carl Mummert Mar 20 '14 at 14:28

I'm not quite sure what you mean by an infinite program, but there is certainly an infinite sequence of symbols that is computed by no finite program.

This follows from a simple counting argument: Assuming $|A|\ge 2$, there are uncountably many infinite sequences of symbols, but there are only countably many finite programs.

  • $\begingroup$ By infinite program, I mean a program of infinite size, i.e., its textual representation is infinite. I need to think a bit more about the countable/uncountable argument, but that seems to do the trick, thanks! $\endgroup$ – Charles Mar 20 '14 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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