3
$\begingroup$

Is it possible to have two (or more) non-universal Turing machines labeled $A_1$ and $A_2$, such that if $f(A_i)$ is the set of functions computable by $A_i$, and S={every computable function} then $S=f(A_1)\cup f(A_2)$? Is there any easy mathematical classification of which functions are computable by some given non-universal Turing machine? Or an algorithm to check if a function/formula f(x) is computable by a given Turing machine? Is it decidable which of the finite set of m-state, n-symbol (for say 20>m+n) Turing machines are universal turing machines?

I am mainly considering finite states, finite symbols, and finite symbols on starting tape.

$\endgroup$

1 Answer 1

4
$\begingroup$

Any concrete Turing machine computes only a single function, not a set of functions, so the question is not completely correct. But I think I understand what you mean.

One example would be

$$ A_1(p,i) = \cases{\bot& \text{if }i=0 \\ T_p(i) &\text{otherwise}}$$ $$ A_2(p,i) = \cases{T_p(i)& \text{if }T_p(0)\text{ terminates} \\ \bot &\text{otherwise}}$$

Then $A_1$ can only compute functions that are not defined at $0$, and $A_2$ can only compute functions that are (in addition to the everywhere undefined function). But every computable function is computable by one of them.

(There are some nitty-gritty details related to how exactly you define "can compute a particular function" -- particularly concerning whether your "can compute" allows a choice of encoding. If you're too liberal there, the entire question may collapse into a triviality).

Is there any easy mathematical classification of which functions are computable by some given non-universal turing machine? Or an algorithm to check if a function/formula f(x) is computable by a given turing machine?

If there were such an algorithm, we could use it to decide the halting problem: Suppose we want to know whether $T_a$ terminates on $0$. Then construct the machine that computes $$ f(p,i) = \cases{i &\text{if }T_a(0)\text{ terminates} \\ \bot &\text{otherwise}}$$ and ask our hypothetical algorithm if this machine can compute the identity function.

Is it decidable which of the finite set of m-state, n-symbol (for say 20>m+n) turing machines are universal turing machines?

For any particular $m$ and $n$, the restricted problem is of course "decidable", by virtue of having only finitely many inputs (the result is computable by a table lookup -- it is difficult to find out which table, but a correct table certainly exists). However, solving it for general $m$ and/or $n$ would again entail a solution to the halting problem.

$\endgroup$
2
  • $\begingroup$ Not sure I follow your last argument, the input can be any of the infinite set of finite strings, ie a tape of any length? $\endgroup$
    – Laylady
    Commented Jan 24, 2012 at 20:01
  • $\begingroup$ @Laylady: The last argument just says that there is no general algorithm that decides whether a given Turing machine is universal. If such an algorithm existed, it could be used to solve halting question by applying it to a machine that runs the mystery machine on some fixed input until it terminates, and then acts as a universal machine on the original input. $\endgroup$ Commented Jan 24, 2012 at 20:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .