Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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? –  Laylady Jan 24 '12 at 20:01
    
@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. –  Henning Makholm Jan 24 '12 at 20:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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