Turing Machine was invented by Alan Turing in 1936 and it is used to accept Recursive Enumerable Languages (generated by Type-0 Grammar). Turing Machine (Halt State Version) A Turing Machine is a sextuple of the form 7-tuple (Q, T, B, ∑, Ξ΄, q0, B, F) where: Q is a finite set of states T is the tape alphabet (symbols which can be written on Tape) B is blank symbol (every cell is filled with B except input alphabet initially) ∑ is the input alphabet (symbols which are part of input alphabet) Ξ΄ is a transition function which maps Q × T → Q × T × {L,R}. Depending on its present state and present tape alphabet (pointed by head pointer), it will move to new state, change the tape symbol (may or may not) and move head pointer to either left or right. q 0 is the initial state F is the set of final states. If any state of F is reached, input string is accepted A Turing machine is a...