State and explain the power and limitations of a Turing machine.

Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016


Power of Turing Machine

The turing machine has a great computational capabilities. So it can be used as a general mathematical model for modern computers.

Turing machine can model even recursively enumerable languages. Thus the advantage of turing machine is that it can model all the computable functions as well as the languages for which the algorithm is possible.

Limitations of Turing Machine

1. Computational complexity theory

a. A limitation of Turing machines is that they do not model the strengths of a particular arrangement well.

b. For instance, modern stored-program computers are actually instances of a more specific form of abstract machine known as the random access stored program.

c. An experimental prototype to machine or RASP machine model. Like the Universal Turing machine the RASP stores its "program" in "memory" external to its finite-state achieve Turing machine machine's "instructions".

d. The RASP's finite-state machine is equipped with the capability for indirect addressing thus the RASP's "program" can address any register in the register-sequence. The upshot of this distinction is that there are computational optimizations that can be performed based on the memory indices, which are not possible in a general Turing machine; thus when Turing machines are used as the basis for bounding running times, a 'false lower bound' can be proven on certain algorithms' running times. An example of this is binary search, an algorithm that can be shown to perform more quickly when using the RASP model of computation rather than the Turing machine model.

2. Concurrency a. Another limitation of Turing machines is that they do not model concurrency well.

b. For example, there is a bound on the size of integer that can be computed by an always halting nondeterministic Turing machine starting on a blank tape.

c. By contrast, there are always-halting concurrent systems with no inputs that can compute an integer of unbounded size.

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more