Variants of turing machines PDF

Preview

Summary

This is easy to learn lecture note for variants of turing machine....

Description

Variants of turing machines Turing machines have variants due to following factors: 1. 2. 3. 4. 5.

The difference in number of tapes each turing machine has. Difference in dimensions of tape. Presence of more than one head with a single tape. Presence of a stationary head. More than one transition for the head on the same state.

Multi-tape turing machines It is a device which has:     

Has finite state and finite number of tapes. Each tape is divided into cells and each cell holds a symbol. The symbols include a blank and also input symbols. Each tape is connected to the finite control by means of a read/write head. The head can move in either direction and also remain stationery.

Non-deterministic turing machine It can be defined similar to NDFA (Non-deterministic Finite Automata).  It allows more than one edge leaving from any state with the same input alphabet.  It does not accept the languages which are not accepted by a deterministic turing machine.  It has a transition function δ such that for each state q and tape symbol X, δ(q,X) is a set of triples {(q1,Y1,D1),(q2,Y2,D2),….,(qk,Yk,Dk)} where k is any finite integer. Universal Turing machine (UTM) These are machines which can be programmed just like a general purpose computer.

 It takes two arguments: the description of computation and description of input string.  UTMs are extremely powerful. They have ability to simulate the behavior of any computer. That is why it is called Universal turing machine.  It can calculate any recursive function.  It can decide any recursive language.  It can accept any recursively enumerable language. Enumeration machine Enumerator is a turing machine with an attached printer. The TM can use the printer as an output device to print strings. Whenever the turing machine adds a string to the list, it sends the string to the printer....