Chapter 12, Problem 15CRP

Program Plan Intro

Turing machine:

• A Turing Machine denotes a mathematical computation model that defines abstract machine.
• It manipulates symbols on tape strip based on table of rules.
• It can operate on an infinite memory tape that is divided into discrete cells.
• It has a head pointer that points to cell currently being read and it can move in both directions.
• It can be expressed as a 7-tuple that includes (Q, T, B, ∑, δ ,q0, B, F) , the details are shown below:
  • The symbol “Q” denotes a finite set of states.
  • The symbol “T” denotes tape alphabet.
  • The symbol “B” denotes a blank symbol.
  • The symbol “∑” denotes an input alphabet.
  • The symbol “δ” denotes a transition function.
  • The symbol “q0” denotes an initial state in the machine.
  • The symbol “F” denotes a set of final states.
•   The time complexity denotes measure of count of times tap moves when machine is initialized for some input symbols.