Unit - 4

Turing Machine

Q1) Explain the turning machine?

A1) An information processing system (TM) may be a mathematical model that consists of associate infinite length tape divided into cells on which input is given. It consists of a head that reads the input tape.

A state register stores the state of the information processing system. Once reading an associated input image, it’s replaced with another image, its internal state is modified, and it moves from one cell to the proper or left. If the metal reaches the ultimate state, the input string is accepted, otherwise rejected.

Formal definition

A metal will be formally delineate as a 7-tuple (Q, X, ∑, δ, q0, B, F)

Where −

• Q may be a finite set of states

• X is that the tape alphabet

• ∑ is that the input alphabet

• δ may be a transition function; δ : alphabetic character × X → alphabetic  character       × X ×

• q0 is that the initial state

• B is that the blank image

• F is that the set of ultimate states

Basic model of turing machine

With the help of the following representation, the turning machine can be modeled.

1. The input tape contains an infinite number of cells, each cell containing one input symbol, so it is possible to position the input string on the tape. Blank characters fill up the empty tape.

Fig 1: Input tape

2.     The finite control and the head of tape that is responsible for reading the current symbol of input. The head of the tape will switch from left to right,

3.     A finite set of states through which the system has to go through.

4.     Finite set of symbols that are used in the construction of the turing machine logic, called external symbols.

Fig 2: Basic model of TM

Various features of the Turing machine exist:

●      It has an external memory that recalls an arbitrary, long input list.

●      It has infinite capability for memory.

●      The model has a method in which it is easy to read the input on the tape on the left or right.

●      Depending on its input, the computer may generate a certain output. It will often be appropriate for the same input to be used to produce the output. So, the distinction between input and output has been abolished in this machine. It is therefore possible to use a standard set of alphabets for the Turing machine.

Q2) What are the variations of TM?

A2) Variation of TM

1. Multiple tracks Alan Turing Machine:

●      A k-tack Alan Turing machine(for some k>0) has k-tracks and one R/W head that reads and writes all of them one by one.

●      A k-track information processing system may be simulated by one track information processing system.

2. Two-way infinite Tape Alan Turing Machine:

●      Infinite tape of two-way infinite tape information processing system is boundless in each direction left and right.

●      Two-way infinite tape information processing system may be simulated by unidirectional infinite {turing|Turing|Alan Alan Turing|Alan Mathison Turing|mathematician} machine(standard Turing machine).

3. Multi-tape Alan Turing Machine:

●      It has multiple tapes and is controlled by one head.

●      The Multi-tape information processing system is completely different from the k-track information processing system however communicative power is the same.

●      Multi-tape information processing system may be simulated by a single-tap information processing system.

4. Multi-tape Multi-head Alan Turing Machine:

●      The multi-tape information processing system has multiple tapes and multiple Heads.

●      Each tape is controlled by a separate head.

●      Multi-Tape Multi-head information processing systems may be simulated by normal information processing systems.

5. Multi-dimensional Tape Alan Turing Machine:

●      It has multi-dimensional tape wherever the head will move any direction that’s left, right, up or down.

●      Multi-dimensional tape information processing system may be simulated by a one-dimensional information processing system.

6. Multi-head Alan Turing Machine:

●      A multi-head information processing system contains 2 or additional heads to scan the symbols on constant tape.

●      In one step all the heads sense the scanned symbols and move or write severally.

●      Multi-head information processing system may be simulated by single head information processing system.

7. Non-deterministic Alan Turing Machine:

●      A non-deterministic information processing system encompasses a single, method of infinite tape.

●      For a given state and input image has at least one option to move (finite range of decisions for consecutive move), every selection has many decisions of path that it’d follow for a given input string.

●      A non-deterministic information processing system is an adored settled information processing system.

Q3) Define linear bounded automata?

A3) A multi-track non-deterministic Turing machine with a tape of some limited finite length is a linear bounded automaton.

Length = function (Length of the initial input string, constant c)

Here,

Memory information ≤ c × Input information

The measurement is limited to the region bounded by constants. There are two special symbols in the input alphabet that act as left end markers and right end markers, indicating that the transitions do not switch either to the left of the left end marker or to the right of the tape's right end marker.

A linear bounded automata can be defined in  8-tuple -

(Q, X, ∑, q0, ML, MR, δ, F)

Where

●      Q is a finite set of states

●      X is the tape alphabet

●      ∑ is the input alphabet

●      q0 is the initial state

●      ML is the left end marker

●      MR is the right end marker where MR ≠ ML

●      δ is a transition function which maps each pair (state) to (state, tape symbol, Constant ‘c’) where c could become 0 or +1 or -1.

●      F is the set of final states.

Fig 4: linear bounded automata

Q4) Write the features of turing machine?

A4) Various features of turing machine

●      It has an external memory that recalls an arbitrary, long input list.

●      It has infinite capability for memory.

●      The model has a method in which it is easy to read the input on the tape on the left or right.

●      Depending on its input, the computer may generate a certain output. It will often be appropriate for the same input to be used to produce the output. So, the distinction between input and output has been abolished in this machine. It is therefore possible to use a standard set of alphabets for the Turing machine.

Q5) Construct TM for the addition function for the unary number system?

A5) The unary number is made up of only one character, i.e. The number 5 can be written in the unary number system as 11111. In this TM, we are going to perform the addition of two unary numbers.

For example

2 + 3

i.e. 11 + 111 = 11111

If you observe this process of addition, you will find the resemblance with string concatenation function.

In this case, we simply replace + by 1 and move ahead right for searching end of the string we will convert last 1 to Δ.

Input: 3+2

The simulation for 111+11Δ can be shown as below:

Move right up to + sign as:

Convert + to 1 and move right as:

Now, move right

Again move right

Now Δ has encountered, so just move left as:

Convert 1 to Δ

Thus the tape now consists of the addition of two unary numbers.

The TM will look like as follows:

Here, we are implementing the function of f(a + b) = c. We assume a and b both are non zero elements.

Q6) Explain design of Turing machine.

A6)

The Turing machine is a mathematical model of a machine that operates mechanically on a tape. There are symbols on this tape that the machine can read and write one at a time with the help of a tape head. The operation is entirely determined by a finite set of elementary instructions such as "write a 1 in state 42 if the symbol seen is 0; change to state 17 if the symbol seen is 1; write a 1 in state 17 if the symbol seen is 0 and change to state 6;" and so on. Turing imagines a person, whom he calls the "computer," who performs these deterministic mechanical laws slavishly in the original essay ("On Computable Numbers, with an Application to the Entscheidungs problem").

Fig 3: The instruction to be performed (q4) is shown over the scanned square

Fig 4: The internal state (q1) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank.

A Turing machine is made up of the following components:

• A tape with cells that are stacked one on top of the other. A symbol from a finite alphabet is contained in each cell. A specific blank symbol (here spelled as '0') and one or more other symbols make up the alphabet. The tape is supposed to be extensible to the left and right arbitrarily, ensuring that the Turing machine has access to as much tape as it requires for computing. The blank symbol is supposed to be filled in cells that have not been written in before. In some models, the tape has a specific symbol on the left end, and it extends or is infinitely extensible to the right.
• A head that can read and write symbols on the tape as well as move the tape left and right one cell at a time. In certain types, the tape is stationary while the head moves.
• A state register that stores the state of one of a finite number of Turing machines. The special start state with which the state register is initialized is one of them. These states, according to Turing, take the place of the "state of mind" that a person conducting calculations would be in.
• Given the present state(qi) of the machine and the symbol(aj) it is reading on the tape (symbol now under the head), a finite table of instructions directs the machine to do the following in order (for the 5-tuple models):
• Either delete or add a symbol (replacing aj with aj1).
• Move the head (which can take values of 'L' for one step left, 'R' for one step right, or 'N' for staying in the same spot, as indicated by dk).
• Assume the same or a different condition as directed (go to state qi1).