7
$\begingroup$

I'm a bit confused about these concepts. As far as I understand, something is Turing complete when it can simulate a Turing machine. And there is this thing called a Universal Turing machine which is universal because it can simulate a Turing machine. Which to me, implies there are Turing machines that are not universal and cannot simulate a Turing machine. Does this mean non-universal Turing machines are not Turing complete?

Could anyone clarify this concepts for me?

$\endgroup$
3
  • 1
    $\begingroup$ this is a somewhat subtler/trickier concept than one might guess ... one has to limit the concept of a "conversion function" between the inputs/outputs, but on the other hand such "conversion functions" are quite common in CS ... if the "conversion functions" are not limited then there is a sense in which every TM is TM complete because the complexity of the computation can be shifted to the "conversion functions"... anyway it will become more clear if you work through the proof of how a universal TM actually works, it is not too hard ... $\endgroup$
    – vzn
    Commented Oct 2, 2013 at 2:59
  • $\begingroup$ @vzn would you please explain or give an example of conversion functions in a turing machine ? it is really important for research purpose ... $\endgroup$
    – abc
    Commented Oct 31, 2015 at 20:34
  • 1
    $\begingroup$ @Abdulrhman its a subtle issue/ long story that is not explained much in papers and hard to summarize but an example is wolfram rule 110 proven (so-called) "weakly" turing complete by Cook due to this issue. the "conversion function" here requires infinitely repeating patterns. so there is a significant degree of complexity in existing "conversion functions" and some theory needs to be developed here to avoid contradictions. suggest further discussion in Computer Science Chat. $\endgroup$
    – vzn
    Commented Nov 1, 2015 at 18:26

2 Answers 2

10
$\begingroup$

In short yes, a non-universal Turing Machine is not Turing-complete.

The key part is that a computational model is Turing-complete if it can simulate any Turing Machine (or using the transitivity of the simulations, if it can simulate a Universal Turing Machine).

As you note, many Turing Machines are not Universal, they compute something, but they can't simulate any computation that any Turing Machine could do.

A possibly intuitive practical way of thinking about this is that Turing Machines are normally equivalent to programs - they take a particular type of input and compute some output. Universal Turing Machines are equivalent to programming languages or computers - you can build/run any program/Turing Machine on them. Of course I'm using "equivalent" very loosely here.

$\endgroup$
1
  • $\begingroup$ Let me see if I get it. A Turing Machine is a Turing complete machine because it can run programs that can compute anything. Theses programs can be either Turing Complete (like running Visual Studio on Windows) or not (like running Paint). A Universal Turing Machine is a Turing Machine loaded with a Turing complete program. Right? $\endgroup$
    – Juan
    Commented Oct 2, 2013 at 18:53
5
$\begingroup$

This is a response to the following comment by Juan Luis Soldi but was too long to put in a comment.

Let me see if I get it. A Turing Machine is a Turing complete machine because it can run programs that can compute anything. Theses programs can be either Turing Complete (like running Visual Studio on Windows) or not (like running Paint). A Universal Turing Machine is a Turing Machine loaded with a Turing complete program. Right?

The Visual Studio / Paint analogy isn't a million miles from the truth but it contain a couple of problems that ought to be discussed.

First, in my opinion it's best not to think of Turing machines as being "loaded with a program", because that leads to confusion. A Turing machine computes a single function, kind of like those cheap little games machines that, say, only play Tetris. Remember that, historically, Turing machines predate the stored program computer by about fifteen years. The definition of the machine includes the transition function, which is fixed: the machine and the program are the same thing and, if you want to change the program, you have to change the hardware.

A universal Turing machine is a Turing machine whose input is a description of a Turing machine and its input. The universal Turing machine simulates the machine described in its input. (As such, it's a bit more like an interpreter than a compiler.) So, if a universal Turing machine $U$ has as input a description of a machine $M$ and its input $x$, its output will be whatever $M$ outputs when it's given input $x$. If $M$ doesn't halt when given input $x$, then $U$ will not halt when given a description of $M$ and $x$.

Now, Turing completeness is a property of models of computation. A model of computation is Turing-complete if defines exactly the same class of functions as Turing machines. So Turing machines are Turing-complete by definition. The lambda-calculus is Turing complete because every lambda-calculus term can be translated into a Turing machine and every Turing machine can be translated into a lambda-calculus term.

Strictly speaking, a universal Turing machine (UTM) is not Turing-complete. This is because it only computes one function: if its input describes a Turing machine $M$ and $M$'s input, the UTM tells you what that machine would have done. Why isn't this Turing-complete? Well, there's a Turing machine $T$ that accepts all inputs of even length and rejects all inputs of odd length and no UTM can do that. The UTM can simulate $T$ but the UTM itself isn't accepting exactly the even-length inputs. Rather, it's accepting all inputs that start with the description of $T$, followed by an even-length input for $T$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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