<p>Given any computable function <span class="math-container">$f : \mathbb{N} \to \mathbb{N}$</span> the set of its indices <span class="math-container">$S_f = \{n \in \mathbb{N} \mid \phi_n = f\}$</span> is for all practical purposes &quot;the set of all programs computing <span class="math-container">$f$</span>&quot; (because the indices encode Turing machines computing <span class="math-container">$f$</span>).</p>
<p>Now <span class="math-container">$S_f$</span> is <em>never</em> computably enumerable (c.e.), let alone generated by any sort of simple &quot;padding&quot; procedure. Indeed, the <a href="https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem" rel="nofollow noreferrer">Rice-Shapiro</a> theorem chracterizes c.e. index sets, but <span class="math-container">$S_f$</span> violates the condition of the theorem.</p>
<p>To put it another way: for any computable map <span class="math-container">$p : \mathbb{N} \to S_f$</span>, the complement <span class="math-container">$S_f \setminus p(\mathbb{N})$</span> is infinite. So as long as &quot;padding&quot; is computable, it misses infinitely many elements of <span class="math-container">$S_f$</span>.</p>

CC BY-SA 4.0
2024-05-02T10:00:13.853Z
“because its complement is c.e.” → I don't think so? It follows from the [Rice-Shapiro theorem](https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem) that $S_f$ is not c.e., but also that $S_f$ is not co-c.e. unless $f$ is the partial function defined nowhere. For example, the sets $S_f$ for $f : ℕ → ℕ$ *total* computable are seen to be all many-to-one equivalent, and also many-to-one equivalent to the universal halting problem. Let me know if I went wrong somewhere!
Jean Abou Samra
CC BY-SA 4.0
2024-05-02T20:39:36.817Z
Ah yes, let me fix the proof. Thanks for pointing this out. (Ok, I hope I got it right.)
Andrej Bauer
CC BY-SA 4.0
2024-05-01T22:57:46.390Z
2024-05-02T20:41:45.283Z
2024-05-02T20:41:45.283Z
Andrej Bauer
<p>It's well-known that every computable function has infinitely many representations (when they're expressed via recursive functions, or programs, etc.). I'm trying to understand whether there are infinitely many representations that are fundamentally &quot;different&quot; in some way. I'm imagining using algorithmic mutual information (or another similar AIT-based measure) to define &quot;different&quot;, but am running into problem.</p>
<p>The reason (that I'm familiar with) for why said functions have infinitely many representations is the padding lemma. For any given program, you can form another representation that is &quot;padded&quot; by taking any halting program, running that before the given program, and then just throwing away the answer and continuing on with your given program. And I understand that this means that there will be padded versions of a function that are not provably equivalent to a non-padded version of that function.</p>
<p>But here's my question; is there a <em>fact of the matter</em> about whether a given program has mere &quot;padding&quot; in it? That is, for any given program, could we say that there exists a non-padded version of it? Of course, a la Kolmogorov complexity, there will exist a <em>smallest</em> program that is equivalent to the other program, in that they represent the same function. But that's not what I want; the smallest program might work completely differently from some other (un-padded) program.</p>
<p>Here's an example for concreteness. There are many sorting algorithms that &quot;feel&quot; totally different: quick sort, bubble sort, merge sort, et cetera. But are there <em>infinitely</em> many sorting algorithms that all feel totally different from each other?</p>
<p>If the answer is &quot;yes&quot;, then what I want to know next is whether there exist functions which have infinitely many &quot;un-padded&quot; representations, all of which have approximately zero algorithmic mutual information with each other.</p>

CC BY-SA 4.0
2024-04-30T22:00:42.030Z
Not *every* computable function has infinitely many "different" unpadded representations - consider the function that always outputs $0$ ($1$). Anything other than $\textbf{return 0 (1)}$ is padding. So, I would suggest changing the condition to every non-trivial function
Tejas
CC BY-SA 4.0
2024-04-30T23:07:25.833Z
What about a machine that calculates two numbers via 'non-trivial' algorithms, then subtracts them? But it happens that the (distinct) specifications of those two numbers are such that they always end up being equal, so the output is always $0$. Is that padded? E.G. what if you were considering numbers from the two seemingly unrelated sequences from [monstrous moonshine](https://en.wikipedia.org/wiki/Monstrous_moonshine), but when it was still a conjecture (or before it was even a conjecture)?
Dan Doel
CC BY-SA 4.0
2024-05-01T11:26:15.557Z
What about if program A is a homomorphic encryption of program B, for some arbitrary encryption key?
usul
CC BY-SA 4.0
2024-05-01T14:53:04.900Z
I think this might just boil down to whether or not there are infinitely many universal TMs which are "different" in the way described. If we have two universal TMs $U_1$ and $U_2$ which are "different", would you consider the machines which are $U_1(\left<M\right>,\cdot)$ and $U_2(\left<M\right>,\cdot)$ as "different" ways of computing the same function (the function computed by machine $M$)?
Dylan McKay
<computability><kolmogorov-complexity>
Does every computable function have infinitely many "non-padded" representations?
Alex Altair
# Does every computable function have infinitely many "non-padded" representations?

(Asked by: username_0 on 2024-04-30)

It's well-known that every computable function has infinitely many representations (when they're expressed via recursive functions, or programs, etc.). I'm trying to understand whether there are infinitely many representations that are fundamentally "different" in some way. I'm imagining using algorithmic mutual information (or another similar AIT-based measure) to define "different", but am running into problem.

The reason (that I'm familiar with) for why said functions have infinitely many representations is the padding lemma. For any given program, you can form another representation that is "padded" by taking any halting program, running that before the given program, and then just throwing away the answer and continuing on with your given program. And I understand that this means that there will be padded versions of a function that are not provably equivalent to a non-padded version of that function.

But here's my question; is there a *fact of the matter* about whether a given program has mere "padding" in it? That is, for any given program, could we say that there exists a non-padded version of it? Of course, a la Kolmogorov complexity, there will exist a *smallest* program that is equivalent to the other program, in that they represent the same function. But that's not what I want; the smallest program might work completely differently from some other (un-padded) program.

Here's an example for concreteness. There are many sorting algorithms that "feel" totally different: quick sort, bubble sort, merge sort, et cetera. But are there *infinitely* many sorting algorithms that all feel totally different from each other?

If the answer is "yes", then what I want to know next is whether there exist functions which have infinitely many "un-padded" representations, all of which have approximately zero algorithmic mutual information with each other.

**Tags:** computability, kolmogorov-complexity
> **Comments:**
> **username_1**: Not *every* computable function has infinitely many "different" unpadded representations - consider the function that always outputs $0$ ($1$). Anything other than $\textbf{return 0 (1)}$ is padding. So, I would suggest changing the condition to every non-trivial function  
> **username_2**: What about a machine that calculates two numbers via 'non-trivial' algorithms, then subtracts them? But it happens that the (distinct) specifications of those two numbers are such that they always end up being equal, so the output is always $0$. Is that padded? E.G. what if you were considering numbers from the two seemingly unrelated sequences from [monstrous moonshine](https://en.wikipedia.org/wiki/Monstrous_moonshine), but when it was still a conjecture (or before it was even a conjecture)?  
> **username_3**: What about if program A is a homomorphic encryption of program B, for some arbitrary encryption key?  
> **username_4**: I think this might just boil down to whether or not there are infinitely many universal TMs which are "different" in the way described. If we have two universal TMs $U_1$ and $U_2$ which are "different", would you consider the machines which are $U_1(\left<M\right>,\cdot)$ and $U_2(\left<M\right>,\cdot)$ as "different" ways of computing the same function (the function computed by machine $M$)?  

---

## 1 answers

### Answer by username_5 on 2024-05-01. Score: 10

Given any computable function $f : \mathbb{N} \to \mathbb{N}$ the set of its indices $S\_f = \{n \in \mathbb{N} \mid \phi\_n = f\}$ is for all practical purposes "the set of all programs computing $f$" (because the indices encode Turing machines computing $f$).

Now $S\_f$ is *never* computably enumerable (c.e.), let alone generated by any sort of simple "padding" procedure. Indeed, the [Rice-Shapiro](https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem) theorem chracterizes c.e. index sets, but $S\_f$ violates the condition of the theorem.

To put it another way: for any computable map $p : \mathbb{N} \to S\_f$, the complement $S\_f \setminus p(\mathbb{N})$ is infinite. So as long as "padding" is computable, it misses infinitely many elements of $S\_f$.

> **Comments:**
> **username_6**: “because its complement is c.e.” → I don't think so? It follows from the [Rice-Shapiro theorem](https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem) that $S_f$ is not c.e., but also that $S_f$ is not co-c.e. unless $f$ is the partial function defined nowhere. For example, the sets $S_f$ for $f : ℕ → ℕ$ *total* computable are seen to be all many-to-one equivalent, and also many-to-one equivalent to the universal halting problem. Let me know if I went wrong somewhere!  
> **username_5**: Ah yes, let me fix the proof. Thanks for pointing this out. (Ok, I hope I got it right.)  

---

