# 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 '16 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.
– Raphael
Oct 25 '16 at 22:31
• Similarly, what is "a machine less powerful then a TM"? Any single machine is ... not all that powerful.
– Raphael
Oct 25 '16 at 22:31
• Damnit, Alan Turing deserves a capital letter. Oct 26 '16 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.
– Raphael
Oct 26 '16 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)$.