HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Does a Universal Turing Machine have more computational power than a non-universal one?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
nonuniversalthanmorecomputationalpoweronedoesmachineturing

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#14691, answer score: 9

Revisions (0)

No revisions yet.