What's the difference between Turing Machine and UTM?

1. Apr 30, 2012

xeon123

1 - I'm trying to see what's the difference between a Turing Machine and a universal Turing Machine. Aren't the same?

2 - If I have a Touring Machine that to solve a problem, for example, adding numbers, what is the purpose of a Universal Touring Machine?

2. May 2, 2012

HallsofIvy

First, it is "Turing" rather than the "Touring" you have in a few places (I know- your fingers just want to go to the letters of more familiar words!). They are named for British mathematician Alan Turing.

A Turing Machine is a conceptual system for doing a particular calculation such as adding two numbers. A "universal Turing machine" is, just as the name would imply, a much more general system in which part of the input would tell the machine if it was to add, multiply, or something else.

3. May 2, 2012

dcpo

A Turing machine takes an input string and according to its internal workings either produces an output string and halts, or calculates forever. As mentioned above, this kind of machine can be used to do things like adding numbers, finding circuits in graphs, and indeed (theoretically) anything that can be suitably represented and solved by a step by step procedure (this the Church-Turing thesis). A universal Turing machine 'U' is a special kind of Turing machine that takes as input a string containing both another Turing machine, T say, (in coded form - to define a UTM we require a method of encoding every TM uniquely), and another input string 'I'. U operates by simulating T on I, and its output (or failure to halt) will mimic exactly the output (or failure to halt) of T acting on I.

Turing machines don't solve practical problems, and I believe real computers are more closely related to unlimited register machines in the way they operate in practice (in theory though any calculation you can do on a computer you can do with a TM). You'll never meet a problem that you need a UTM to solve (unless you are working in theoretical computer science), but they provide a theoretical basis for general computing, that is, computers that can run different programs to do different things. Here in 2012 this is hardly surprising, as we have real computers that do exactly that, but in 1936 this was a profound idea.