Kolmogorov complexity for infinite strings

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?

• 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. Commented Mar 20, 2014 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. Commented Mar 20, 2014 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). Commented Mar 20, 2014 at 14:21
• that is what Henning Makholm is addressing in his answer; it would be true if $U$ was replaced by any function. Commented Mar 20, 2014 at 14:28

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.