2

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?

Charles
  • 525
  • 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. – Charles Mar 20 '14 at 13:52
  • 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. – Carl Mummert Mar 20 '14 at 14:17
  • @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). – Charles Mar 20 '14 at 14:21
  • 1
    that is what Henning Makholm is addressing in his answer; it would be true if $U$ was replaced by any function. – Carl Mummert Mar 20 '14 at 14:28

1 Answers1

3

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.

hmakholm left over Monica
  • 286,031
  • 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! – Charles Mar 20 '14 at 14:00