2
$\begingroup$

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?

$\endgroup$
4
  • $\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
    Commented Mar 20, 2014 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
    Commented Mar 20, 2014 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
    Commented Mar 20, 2014 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
    Commented Mar 20, 2014 at 14:28

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented Mar 20, 2014 at 14:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .