-1
$\begingroup$

Subject pretty much says it all. My strong impression is that for any algorithm and any choice of programming language or computational model, if it's Turing-complete, then there must be infinitely many ways to implement the algorithm such that a fixed interpreter for the language will necessarily return the same output, even if this is essentially just a matter of adding NOOP equivalents to the code.

Is this provably true, false, or unknown? And if applicable, can someone point me towards relevant keywords, in particular if this is an established theorem or conjecture?

$\endgroup$
1

2 Answers 2

0
$\begingroup$

No sooner did I click okay on my question than a plausible answer occurred to me. Posting to make sure this makes sense.

Since any TC language must be able to simulate any other TC languages, it requires only translating any given program through a simulation in another language and back again to get a much less efficient but equivalent program. Since you could do this arbitrarily many times, or with arbitrarily many languages in whatever order, that should work as a proof sketch.

$\endgroup$
7
  • 1
    $\begingroup$ This depends on exactly what "Turing-complete" means - see here. $\endgroup$ Sep 16, 2021 at 19:12
  • $\begingroup$ I was familiar with this concept, but not the name (Friedberg numberings). Yes, for my purposes, I'm discounting non-computable "magic" mappings like that which place unrealizable constraints on the translator algorithm, etc. $\endgroup$
    – Trev
    Sep 16, 2021 at 21:53
  • $\begingroup$ A Friedberg numbering is computable, though, and the existence proof is completely constructive - you could actually whip up a "Friedberg language" and use it. It's not that Friedberg numberings are noncomputable, but rather that they have too little content (they don't satisfy the relevant universality property). $\endgroup$ Sep 16, 2021 at 23:25
  • 1
    $\begingroup$ The Friedberg numbering is computable, but the translation into it isn't. We can actually make and use a Friedberg numbering; what we can't do is make a Friedberg numbering and then answer questions of the form "Where is program $P$ in this numbering?" in a computable way. $\endgroup$ Sep 16, 2021 at 23:40
  • 1
    $\begingroup$ Here's a precise statement: there is a computable partial binary function $f(x,y)$ such that for every computable partial unary function $s(x)$ there is exactly one $n$ such that $$s\simeq\lambda x.f(x,n).$$ This $f$ is basically a Friedberg numbering. $\endgroup$ Sep 16, 2021 at 23:41
0
$\begingroup$

Just add nonsense operations that don't affect the result at will.

$\endgroup$
1
  • $\begingroup$ This might not be something you can actually do, depending on how precisely we define "Turing-complete" - see here. $\endgroup$ Sep 16, 2021 at 19:13

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.