3
$\begingroup$

Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program is irreducible if no subsequence of it has the same behavior as it.

Given a string $s$, we are interested in the longest irreducible program outputting it, and an upper bound on its length. Due to Higman's lemma, the set of irreducible programs outputting $s$ is finite, so such a bound must exist.

When is it computable? I can't think of any encoding in which an upper bound would be incomputable, but also not show it's always computable.

If the encoding is unary, only dependent on the length of the string, then we can just look at any program outputting $s$ for a bound.

Otherwise, an idea I had was showing that if there's an irreducible program outputting $s$ of length $|p| \geq n$, then there must be one outputting it of length $n \leq |p| \leq f(n)$, where $f(n)$ is some computable function, and then from Kőnig's lemma that's enough for an upper bound (which would be very large, but still computable). However, I have no idea if it's true, which $f$ to choose, and how to prove it.

Another possible approach might be to construct a set of all irreducible programs which output it, by dovetailing. After some finite time we will find all programs, but we need to somehow tell when we that's the case. Perhaps we can search somehow for a proof that any program that avoids them all can't output the string.

Improve this question
$\endgroup$
10
  • $\begingroup$ Just to clarify the question: given a finite alphabet $Σ$, you are asking if there exists a partial computable function $F: Σ^* \dashrightarrow Σ^*$ such that if we call $B_F$ the function taking $s\in Σ^*$ to the greatest length $B_F(s)$ of an element of $L_s := \{p\in Σ^* : F(p){\downarrow} = s\}$ such that no (not-necessarily-consecutive) subword is also in $L_s$, this function $B_F$ is not upper-bounded by a computable function — correct? $\endgroup$
    – Gro-Tsen
    Commented Dec 16, 2023 at 22:14
  • $\begingroup$ @Gro-Tsen yes, with the added condition that we can translate Turing machines to and from strings $p$, and I prefer natural examples — common programming languages, for example — if those exist. For example, is this boundable if $F$ is a Python interpretor? $\endgroup$
    – Daniel Weber
    Commented Dec 16, 2023 at 22:21
  • 1
    $\begingroup$ Translating Turing machines “from” $p$ is probably included in the condition that $F$ is computable. But it would be best if you were extremely precise in explaining what you mean by this condition, because what you are asking for seems very much like the sort of things a Friedberg numbering is supposed to make you think twice about: so, is a Friedberg-style numbering a “translation” in your sense? ❧ Also, it would be nice if you gave some background or motivation for the question. $\endgroup$
    – Gro-Tsen
    Commented Dec 16, 2023 at 22:34
  • 3
    $\begingroup$ @JoelDavidHamkins In the context of Higman's lemma, “substring” means a subset of the characters in the program, taken in the same order, but not necessarily consecutive, so even if you require a start-of-program and an end-of-program marker, that does not prevent a substring from being a valid program. (And the argument around Higman's lemma is: assume there were an infinite number of “irreducible” programs $p_i$ producing $s$: order them in some way; then by Higman's lemma we could find $i<j$ such that $p_i$ is a substring of $p_j$, contradicting irreducibility of $p_j$.) $\endgroup$
    – Gro-Tsen
    Commented Dec 16, 2023 at 23:35
  • 2
    $\begingroup$ OK, I can think of another motivation for this question besides code bowling: Kolmogorov complexity of a string is defined as the length of the shortest program that outputs it, so it's natural to wonder about the longest. Now obviously the longest doesn't exist because one can always add stupid stuff to a program, so it's fairly natural to wonder about the longest irreducible program that outputs the string (“anti-Kolmogorov complexity”? “Kolmogorov simplicity”? 😅). And then wonder about its computability in some sense. $\endgroup$
    – Gro-Tsen
    Commented Dec 17, 2023 at 9:50

1 Answer 1

Reset to default
6
$\begingroup$

I can't answer in the case of Python or any such “natural” programming language, but let me show that whenever $\#\Sigma \geq 2$ there is an encoding such that the function you define is non-computable.

The programming language in question has two “modes”, determined by a different program syntax: in “compute” mode it is a normal programming language, whereas in “proof” mode, it can only output a string (independently of its input) if that string is a theorem of first-order ZFC, and this behavior is obtained by giving a full proof of that theorem as program. The only thing we need to add is the requirement that no “compute mode” program is a substring of a “proof mode” program, say, by requiring that compute mode programs start with a special symbol that is not part of proof mode.

To be more precise, here's a possible way of doing it: say $\Sigma = \{C,P\}$. A valid program is either a nonempty sequence of $C$'s, in which case it encodes the $e$-th general recursive function where $e$ is the length of the string, or a sequence of $P$'s, in which case if $n$ is its length, then $n$ must be the Gödel encoding of a valid proof in ZFC, and the output of the program is the constant function with value the conclusion of that proof. Anything else is considered invalid (and behaves as the totally undefined function).

Clearly this programming language is convertible to and from Turing machines: to compute from Turing machines, just use compute mode in every case. To compute to Turing machines, compute mode is standard, and for proof mode, just check that the program is a valid proof and output its conclusion.

Now given a string $s$, if $s$ is a theorem of ZFC, there will be a “proof mode” program that outputs it, namely a proof of $s$. The first proof of $s$ is an irreducible program in the sense you defined (since substrings of the program can only code valid “proof mode” programs). There will, of course, be a “compute mode” program which does the same, but no matter: to bound the maximal length of a program which outputs $s$ we need to bound the length of the first proof of $s$, and this is clearly not possible by a computable function. (If you prefer, use the Busy Beaver instead of this, by demanding that the program be a complete execution trace of whatever string you're trying to output.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! You need proof mode programs to start with a special character, not compute mode, otherwise a proof could still be a subsequence of a compute program $\endgroup$
    – Daniel Weber
    Commented Dec 17, 2023 at 3:15
  • $\begingroup$ @CommandMaster It's fine if a proof is a subsequence of a compute program: the only point of compute mode is to fulfill your requirement on Turing-completeness, but we don't care if compute mode programs are irreducible; what we want is to have very long irreducible programs, so we want proof mode programs not to have compute mode programs as subsequences. $\endgroup$
    – Gro-Tsen
    Commented Dec 17, 2023 at 9:46

You must log in to answer this question.

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