1
$\begingroup$

I have recently been reading up on TOC, and had this thought, which does not seem to be answered explicitly anywhere.

They way I have understood it, a system is Turing complete if it can simulate any Turing machine. But Turing machines are limited to their instructions. Does that mean not every TM is actually Turing complete? If I am not completely mistaken, only the universal TM would truly be Turing complete. Am I missing something?

$\endgroup$
1
  • 1
    $\begingroup$ The set of turing machines is turing complete. A single machine may/may not be turing complete, depending on exactly how you interpret it. $\endgroup$
    – nir shahar
    Dec 8, 2021 at 9:54

3 Answers 3

8
$\begingroup$

Turing completeness is not a property of a single program or a single machine. It does not make sense to ask “is this machine/program/gadget Turing-complete?”

Turing-completeness is a property of a model of computation, which is a mathematical structure that describes a particular way of performing computation. Some examples of models of computation:

  1. The set of all Turing machines.
  2. The set of all Turing machines with an oracle.
  3. The set of all general recursive functions.
  4. The set of all valied expressions in the $\lambda$-calculus.
  5. The set of all deterministic finite automata.
  6. The set of all push-down atomata.

Remark: There are several possible precise mathematical definitions of what a model of computation actually is. We also need a precise definition of what it means to exhibit a simulation betwen models. Computability books usually skim over these notions and just show simulations on case-by-case basis.

Anyhow, say that a model $M$ is as capabable as model $N$ when $M$ can simulate $N$. (Notice that at all times we are talking about entire models, not single machines or programs). Say that models are equivalent if each is as capabable as the other. Finally, a model is Turing-complete if it is as capable as the Turing machine model.

In the above list, the model of Turing machines with oracles is as capable as the model of Turing machines. The models of Turing machines, general recursive functions, and $\lambda$-calculus are equally capable, whereas finite automata and push-down atomata are not as capable as Turing machines.

Supplemental: There is a notion that applies to a single machine, namely that of a universal Turing machine. It is an important concept, it plays a role in proofs of Turing-completeness, but a universal Turing machine isn't by itself "Turing-complete" – that's the wrong phrase to use.

$\endgroup$
3
$\begingroup$

Andrej Bauer rightly points out that in general, it does not make sense to ask whether a particular machine/program/gadget is Turing complete.

However, it does make sense when such a device is programmable: when it can read a specification of what it needs to do, and then do that. In other words: when it implements a model of computation. We might call a programmable device Turing complete when the model it implements is Turing complete.

(Andrej Bauer maintains that we call such devices universal, not Turing complete. Let's just say that I have seen the term Turing completeness being applied to devices and to programs, e.g. Minecraft, Doom, and Vim.)

In this sense, every universal Turing machine is Turing complete (universal): it is programmable, and it implements the model of computation of Turing machines. However, most Turing machines aren't programmable, and most programmable Turing machines do not implement a Turing complete model of computation. So the answer to your question is still: no.

For instance, consider a Turing machine that reads a decimal number, then a hash mark, then an arbitrary string up to the next hash mark, and then outputs Y if the string has as many characters as the decimal number indicates, and N otherwise. We can say that this Turing machine is programmable, with each of its programs being a decimal number and the meaning of each program being to decide whether the given input string has the given number of characters. Clearly, this programming language, if you want to call it that, isn't Turing complete by a long stretch, so the machine isn't, either.

$\endgroup$
2
  • 2
    $\begingroup$ It should be emphasized even more that you speak of universal machines, not "Turing-complete" ones. Of course they play an important role, but the word is "universal' – not "Turing-complete". $\endgroup$ Nov 5, 2022 at 23:16
  • $\begingroup$ Thanks; I just did. I have only seen the term 'universal' used to specify Turing machines capable of running arbitrary Turing machines. $\endgroup$ Nov 7, 2022 at 11:40
-4
$\begingroup$

I believe....

According to the Church-Turing thesis: "any algorithm that can be computed in a finite length of time, can be calculated on a Turing machine". Technically making any language that can do the same thing, 'Turing Complete'. Other computers may be faster but none can be more powerful than a Turing machine because it can do anything. Remembering Turing Machines are only a mathematical concept used to evaluate the strength of modern computing programs.

$\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.