Automata Turing Machine

Formal Definition

A Turing machine can be bounded as a collection of 7 tuples:

Q= finite set of states

∑= finite set of input symbols

T= tape symbol

q0= the initial state

F= a set of final states

B= a blank symbol used as an end marker for input

δ= a transition or mapping function.

Let's construct a Turing machine for some Language L.

Also read,  Arden's theorem

Example 

TM for subtracting two unary numbers f(a-b) = c where a is always greater than b.

For subtraction, the first number is greater than the second number. Let us assume that a = 3, b = 2, so the input will be:

will move right to - symbol

Move right up to '-' as:

Move right and convert '1' to '*' as follows:

Now move towards the left.

Again move towards the left.

Convert '1' to '*' and move towards the right-hand side

Now move right till 1

Convert '1' to * and move towards left

Convert '1' to '*' and move

Move right till Δ is found as follows:

Now we are in the 'HALT state' (computation is ended).

Thus we get '1' on the input tape as the answer for f(3-2), where a=3 and b=2.

The Turing machine will look like this:

Also see, Turing Machine in TOC.

Frequently Asked Questions

What is the use of a Turing machine?

The Turing machine is the most powerful computation model that reads and writes to an infinite tape.

What do you mean by halting?

The halting is a decision problem about the properties of computer programs on a fixed Turing model of computation, i.e., all programs written in some specified programming language that is enough to be equivalent to a Turing machine.

Conclusion

This article has covered the topic of Turing machines with examples in detail to clear your thoughts about this topic.

For more information regarding the Turing machine, you can visit here.
Also, for details regarding the theory of computation, you can look here.

Recommended Readings:

• Basics of TOC
• Multi Tape Turing Machine
• Non Deterministic Turing Machine
• Finite State Machine
• Automata Theory
• Regular Grammar
• Regular Expression
• Memory Hierarchy
• DFA minimization

You can also consider our Online Coding Courses such as the Machine Learning Course to give your career an edge over others.

Happy Learning!!!