Question: Give a formal definition for a Turing machine with 1 tape but with 2 heads. Your definition should be in the style of Definition 3.3,
Give a formal definition for a Turing machine with 1 tape but with 2 heads. Your definition should be in the style of Definition 3.3, modified to describe the fact that the control unit controls two heads that can independently read, write and move left or right.

DEFINITION 3.3 A Turing machine is a 7-tuple, (Q.?. ?.?.Qo.qaccept.qreject), where Q, , ? are all finite sets and 1. Q is the set of states, 2. 2 is the input alphabet not containing 3. ? is the tape alphabet, where E?and ?-? 4. 8: Q x ?-> Q . ? x { L. R} is the transition function, 5. q) ? Q is the start state, 6. qaccept E Q is the accept state, and 7. qreject E Q is the reject state, where qreject?qaccept. the blank symbol u
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
