3
$\begingroup$

There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there exists the same algorithm that would solve the problem on that model (e.g. emulation).

I was wondering, if there's a model of computation, that is equivalent to turing machines (the coding translation being just general bijection), but encoding standard input to its input would be an uncomputable problem. In essence making it an model of computation that is cut off from convetional models by it's coding being uncomputable. That would be first part of my question. I

For the second part, if such model exists, let's call it $S$, can you find other models of computations $S_0, S_1, \dots$, such that conversion between $S$ and $S_i$ would be computable by both $S$ and $S_i$? If $T, T_0, T_1,\dots$ were models of turing machine, and other conventional computation models, would $\mathcal{T}=\{T,T_0,T_1,\dots\}$ and $\mathcal{S}=\{S,S_0,S_1,\dots\}$ be two seperate "islands" of computation? Both equivalent, but no member of either family would be able to encode it's inputs to the other family? Or maybe only $\mathcal{S}$ would be able to, making some sort of partial order on such families of models of computation, like $\mathcal{T}<\mathcal{S}$?

note: I'm not sure if it's formal to talk about a model of computation as a mathematcical object, I meant most of the last paragraph mostly informally, but maybe it would suffice to just take set of all instances of such model of computation. Like $T=\{\text{all Turing machines}\}$, $T_0=\{\text{all Lambda expressions}\}$ and such .

Improve this question
$\endgroup$
2
  • $\begingroup$ When you say "I was wondering, if there's a model of computation, that is Turing-equivalent, but encoding standard input to its input would be an uncomputable problem", Turing-equivalent to what? Turing-equivalence is a relation between models (models $A$ and $B$ are Turing-equivalent if there is a Turing-computable translation between them, or something like that). $\endgroup$
    – Andrej Bauer
    Commented Jun 16, 2019 at 19:20
  • $\begingroup$ Oh, I wasn't aware of that, I meant equivalent to turing machines by some coding, the coding translation is here meant as general bijection with no computability restrictions. Will edit the post. $\endgroup$
    – Punga
    Commented Jun 16, 2019 at 19:36

1 Answer 1

Reset to default
1
$\begingroup$

Consider a standard coding of Turing machine $T_0$, $T_1$, $T_2$, ... Let $b : \mathbb{N} \to \mathbb{N}$ be a non-computable bijection. Define a new coding of Turing machines $T'_n = T_{b(n)}$. Clearly, the encoding $T'$ can do everything that Turing machines can do (whatever you do with $T$ you can do with $T'$ by composing with $b$ and its inverse), but it is not equivalent to $T$ by a computable bijection (or else $b$ would be computable).

Improve this answer
$\endgroup$

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.