5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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 $\endgroup$
    – Tejas
    Commented Apr 30 at 22:00
  • 4
    $\begingroup$ 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, but when it was still a conjecture (or before it was even a conjecture)? $\endgroup$
    – Dan Doel
    Commented Apr 30 at 23:07
  • 1
    $\begingroup$ What about if program A is a homomorphic encryption of program B, for some arbitrary encryption key? $\endgroup$
    – usul
    Commented May 1 at 11:26
  • 1
    $\begingroup$ 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$)? $\endgroup$
    – Dylan McKay
    Commented May 1 at 14:53

1 Answer 1

Reset to default
10
$\begingroup$

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 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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ “because its complement is c.e.” → I don't think so? It follows from the Rice-Shapiro 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! $\endgroup$
    – Jean Abou Samra
    Commented May 2 at 10:00
  • $\begingroup$ Ah yes, let me fix the proof. Thanks for pointing this out. (Ok, I hope I got it right.) $\endgroup$
    – Andrej Bauer
    Commented May 2 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.