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.

Give a formal definition for a Turing machine with 1 tape but

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

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!