1
$\begingroup$

It is known that a Turing machine cannot predict the outcome of another Turing machine. Given a machine $M$ less powerful than any Turing machine (i.e. able to decide less languages, i.e. a subset of langauges, than any Turing machine), does there exist a Turing machine $T$ which can always compute $M$ such that $T(M, x) = M(x)$?

$\endgroup$
  • $\begingroup$ Duplicate cs.stackexchange.com/questions/51863/…. The question was edited, but the answers there are well fitted for your question. Some concrete examples of natural models are given (counter machines). See the answer by David for a simple obviously weaker model with undecidable halting (or checking output) problem. $\endgroup$ – Ariel Oct 25 '16 at 22:29
  • 1
    $\begingroup$ "a turing machine cannot predict the outcome of another turing machine" -- that sentence as is is wrong. There are certainly TMs that can "predict" "outcome" for some TMs. Your intuition is flawed. $\endgroup$ – Raphael Oct 25 '16 at 22:31
  • $\begingroup$ Similarly, what is "a machine less powerful then a TM"? Any single machine is ... not all that powerful. $\endgroup$ – Raphael Oct 25 '16 at 22:31
  • 1
    $\begingroup$ Damnit, Alan Turing deserves a capital letter. $\endgroup$ – David Richerby Oct 26 '16 at 8:16
  • 1
    $\begingroup$ @JeromeBaek You are asking something that is either barely a question or very basic. Hence, I suspect that "nitpicks" may be all of the issue here. (I know that they often are.) Maybe if you used more precise language we could get to another level. $\endgroup$ – Raphael Oct 26 '16 at 11:13
1
$\begingroup$

Pick any model of computation, say a class of Arbitrary Automata $\mathcal{A}$, so that $F_{\mathcal{A}} \subseteq \mathrm{RE}$, i.e. this model is sub-Turing-complete.

Since TMs are an admissible numbering and $\mathcal{A}$ is a numbering of some set of (semi-)computable functions, for every $A \in \mathcal{A}$ there is a Turing machine $f(A)$ with $F_A = F_{f(A)}$ -- and we know that this compiler $f$ is computable.

By the existence of a universal Turing machine $U$, we get that $U(\langle f(A) \rangle, x) = A(x)$ for all $x$. Applying the s-m-n theorem gives us a TM $T$ with $T(\langle A \rangle, x) = U(\langle f(A) \rangle, x) = A(x)$.

$\endgroup$

Your Answer

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

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