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)$?
Can a Turing machine compute the outcome of any machine that is less powerful than a Turing machine?
9
-
$\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$– ArielOct 25, 2016 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, 2016 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, 2016 at 22:31
-
1$\begingroup$ Damnit, Alan Turing deserves a capital letter. $\endgroup$– David RicherbyOct 26, 2016 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, 2016 at 11:13
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
0
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)$.
