To my understanding, the notion of Turing-computability of a partial map $ℕ_0 \dashrightarrow ℕ_0$ depends on the encoding of $ℕ_0$.

Say $Σ$ is an alphabet and $γ \colon Σ^\ast → ℕ_0$ is a bijection. A partial map $f\colon ℕ_0 \dashrightarrow ℕ_0$ is then called computable with respect to $γ$ if its conjugation $γ^{-1} ∘ f ∘ γ \colon Σ^\ast \dashrightarrow Σ^\ast$ is computable by a turing machine over the alphabet $Σ$.

So say we have two bijective encodings $Σ^\ast → ℕ_0$ called $γ$ and $γ’$. Give these encodings rise to the same notion of computability if both make some basic maps $ℕ_0 → ℕ_0$ computable?

For example, if the successor map $ℕ_0 → ℕ_0$ is computable with respect to both $γ$ and $γ’$, are then all computable maps $ℕ_0 \dashrightarrow ℕ_0$ with respect to $γ$ and $γ’$ the same?

This seems intuitive to me, yet I don’t know if it’s true.

  • $\begingroup$ I don't see any reason to expect it to be true. As a thought experiment, imagine making $\gamma$ "computable" and $\gamma'$ "not computable", for some suitable notion of "computable". $\endgroup$ – D.W. Feb 25 '16 at 12:41
  • $\begingroup$ I don't follow your first sentence. A function is a function, and it's either computable or not. I struggle to see what kind of (reasonable) encoding of the naturals would make an otherwise computable function uncomputable, and the other way around seems even weirder. $\endgroup$ – Raphael Feb 25 '16 at 13:34
  • $\begingroup$ @Raphael I’m not excluding unreasonable encodings. Isn’t it the case, that if one defines computability of partial maps $ℕ_0 \dashrightarrow ℕ_0$ in terms of Turing machines, one implicitly uses an encoding $Σ^\ast → ℕ_0$ to do so? I’d guess that people hide this issue of dependence on encodings under the term “reasonable” encoding (well, and of course, there are canonical encodings for bijections $Σ → \{0,…,b-1\}$), but I’m very interested in that! Or is it the case that it doesn’t depend on the encoding at all? I can’t imagine. $\endgroup$ – k.stm Feb 25 '16 at 14:18
  • $\begingroup$ @D.W. You mean setting $γ’ = χ ∘ γ$ for some bijective map $χ \colon ℕ_0 →ℕ_0$ that is not computable with respect to $γ$? It might be the case that conjugating by $χ$ respects computability, i.e. for a computable map $f$ with respect to $γ$, the conjugate $χ^{-1} ∘ f ∘ χ$ might be computable with respect to $γ$ again. $\endgroup$ – k.stm Feb 25 '16 at 14:49
  • $\begingroup$ I guess I don't see why it's interesting to see what happens to a notion of computability if your input encoding is not computable. (Feels circular, anyway.) $\endgroup$ – Raphael Feb 25 '16 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.