1
Write short note on Universal Turing Machine.

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015

1
2
• A Turing machine is said to be universal Turing machine if it can accept:

• The input data, and

• An algorithm (description) for computing.

• This is precisely what a general purpose digital computer does. A digital computer accepts a program written in high level language. Thus, a general purpose Turing machine will be called a universal Turing machine if it is powerful enough to simulate the behavior of any digital computer, including any Turing machine itself.

• More precisely, a universal Turing machine can simulate the behavior of an arbitrary Turing machine over any set of input symbols. Thus, it is possible to create a single machine that can be used to compute any computable sequence.

If this machine is supposed to be supplied with the tape on the beginning of which is written the input string of quintuple separated with some special symbol of some computing machine M, then the universal Turing machine U will compute the same strings as those by M.

• The model of a Universal Turing machine is considered to be a theoretical breakthrough that led to the concept of stored programmer computing device.

• Designing a general purpose Turing machine is a more complex task. Once the transition of Turing machine is defined, the machine is restricted to carrying out one particular type of computation.

• Digital computers, on the other hands, are general purpose machines that cannot be considered equivalent to general purpose digital computers until they are designed to be reprogrammed.

• By modifying our basic model of a Turing machine we can design a universal Turing machine. The modified Turing machine must have a large number of states for stimulating even a simple behavior. We modify our basic model by:

• Increase the number of dimensions of input tape

• Adding a special purpose memory

• All the above modification in the basic model of a Turing machine will almost speed up the operations of the machine can do.

• A number of ways can be used to explain to show that Turing machines are useful models of real computers. Anything that can be computed by a real computer can also be computed by a Turing machine. A Turing machine, for example can simulate any type of functions used in programming language. Recursion and parameter passing are some typical examples. A Turing machine can also be used to simplify the statements of an algorithm.

• A Turing machine is not very capable of handling it in a given finite amount of time. Also, Turing machines are not designed to receive unbounded input as many real programmers like word processors, operating system, and other system software.

2