Trusted answers to developer questions

Danyal Ahmed

In 1936, **Alan Turing** invented the Turing machine. He called it an automatic machine.

A Turing machine is a mathematical model. It accepts the **recursively Enumerable languages,** and consists of infinite length tape divided into cells on which input is given. The machine is more powerful than the *PushDown Automata* and *Finite State Machine*.

A tape sequence of infinite symbols contains a pointer of a tape head*,* and it points to the symbol on which the current control is present.

A tape head is either moving one step left or one step right depending upon the situation and having an option to read or write at that position.

It consists of a tape head that reads from the input tape. Next, a state register stores the state of the Turing machine. The tape head reads from the input tape and is replaced according to the situation with another symbol. This changes its internal state. It then moves either to the left of the tape or the right. Finally, the input string is accepted if the Turing machine reaches the final state(F). Otherwise, it is rejected.

Here, it consists of 7 tuples:

- X: It defines a
- ∑: It defines the input alphabet.
- Q: It defines the
- q0: It is necessary for the initial state.
- B: It is necessary for the blank symbol.
- F: It is necessary for the set of final states.
- δ: It is necessary for a transition function; here, the transition function is defined as δ: Q × X → Q × X × {Left_shift, Right_shift}.

Let's look at an example of a Turing machine {a^n*b^n where n>=1} given below:

- First of all, the input string is
*aaabbb* - At state
*q0*, it takes the*a*from the input tape head and replaces it with the symbol*x,*and then moves to the next state. - At state
*q1*, if it reads the*a,*it will be the same in that state; if it takes b, it replaces it with*y*to move to the next state. - At state
*q2*, it will repeat the same process as done in the previous two steps, but if it takes*x*from the head, then it will move to state*q0*. - Now again, at state
*q0*, if it takes*y,*it moves to the*q3*state, and the rest of*y*will be accepted in state*q3*. - At state
*q3*, if it takes*B*, it moves to the final state (*F*), and the given string is accepted.

RELATED TAGS

computing

CONTRIBUTOR

Danyal Ahmed

RELATED COURSES

View all Courses

Keep Exploring

Related Courses