Register to reply

What's the difference between Turing Machine and UTM?

by xeon123
Tags: difference, machine, turing
Share this thread:
Apr30-12, 03:12 PM
P: 81
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?
Phys.Org News Partner Mathematics news on
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
May2-12, 01:31 PM
Sci Advisor
PF Gold
P: 39,542
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.
May2-12, 08:55 PM
P: 95
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.

Register to reply

Related Discussions
Turing machine Introductory Physics Homework 1
X+y Turing machine Calculus & Beyond Homework 4
Turing Machine Quantum Physics 4
Turing machine help! Engineering, Comp Sci, & Technology Homework 0
Turing machine problem Engineering, Comp Sci, & Technology Homework 1