Timeline for When is an upper bound on the longest irreducible program outputting something computable?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8 at 14:43 | comment | added | Daniel Weber | Posted to CS Theory | |
| S Feb 11 at 8:04 | history | bounty ended | CommunityBot | ||
| S Feb 11 at 8:04 | history | notice removed | CommunityBot | ||
| Feb 9 at 7:29 | history | edited | Daniel Weber | CC BY-SA 4.0 |
added 326 characters in body
|
| S Feb 3 at 6:37 | history | bounty started | Daniel Weber | ||
| S Feb 3 at 6:37 | history | notice added | Daniel Weber | Improve details | |
| Dec 17, 2023 at 9:54 | history | became hot network question | |||
| Dec 17, 2023 at 9:50 | comment | added | Gro-Tsen | 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. | |
| Dec 17, 2023 at 3:20 | comment | added | Daniel Weber | @Gro-Tsen I specifically meant to exclude Friedberg-style numbering with this condition, because it isn't an interesting example. The motivation for this question are code bowling challenges on Code Golf Stack Exchange. | |
| Dec 16, 2023 at 23:50 | comment | added | Joel David Hamkins | @Gro-Tsen Thanks for the explanation! | |
| Dec 16, 2023 at 23:35 | comment | added | Gro-Tsen | @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$.) | |
| Dec 16, 2023 at 23:30 | answer | added | Gro-Tsen | timeline score: 6 | |
| Dec 16, 2023 at 23:30 | comment | added | Joel David Hamkins | Could you explain the bit about Higman's lemma? Suppose I take Turing machine programs and code them with strings, but with an end-of-program marker, and strings lacking that marker are taken as a trivial default program which gives no output. If a program gives output $s$, then there will be infinitely many Turing machines giving that string, and with the end-of-program marker, these will all be irreducible. These seems to contradict your claim that there will be only finitely many, and so I think I don't understand you. | |
| Dec 16, 2023 at 23:25 | comment | added | Joel David Hamkins | For most common programming languages, not every string is a program. If one gives up on every string being a program, it is easy to ensure the irreducibility condition, simply by having an end-of-program marker, and this will trivialize the question. | |
| Dec 16, 2023 at 22:34 | comment | added | Gro-Tsen | 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. | |
| Dec 16, 2023 at 22:21 | comment | added | Daniel Weber | @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? | |
| Dec 16, 2023 at 22:14 | comment | added | Gro-Tsen | 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? | |
| Dec 16, 2023 at 21:06 | history | asked | Daniel Weber | CC BY-SA 4.0 |