# Can a Turing machine compute the outcome of any machine that is less powerful than a Turing machine?

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)$?

• 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. Oct 25, 2016 at 22:29
• "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. Oct 25, 2016 at 22:31
• Similarly, what is "a machine less powerful then a TM"? Any single machine is ... not all that powerful. Oct 25, 2016 at 22:31
• Damnit, Alan Turing deserves a capital letter. Oct 26, 2016 at 8:16
• @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. Oct 26, 2016 at 11:13

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