Read both the informal and formal definitions of TMs (165–170). For now, you can skim or skip over the definition of configuration (page 168 at \"As a Turing machine computes\" through the end of page 169), though we will certainly need it later.
\n", "Watch W8E1: Turing Machines.
\n", "Read the book's examples of TMs (170–175).
\n", " \n", "q1 | [0] 0 0 0 |
q2 | _ [0] 0 0 |
q3 | _ x [0] 0 |
q4 | _ x 0 [0] |
q3 | _ x 0 x [_] |
q5 | _ x 0 [x] _ |
q5 | _ x [0] x _ |
q5 | _ [x] 0 x _ |
q5 | [_] x 0 x _ |
q2 | _ [x] 0 x _ |
q2 | _ x [0] x _ |
q3 | _ x x [x] _ |
q3 | _ x x x [_] |
q5 | _ x x [x] _ |
q5 | _ x [x] x _ |
q5 | _ [x] x x _ |
q5 | [_] x x x _ |
q2 | _ [x] x x _ |
q2 | _ x [x] x _ |
q2 | _ x x [x] _ |
q2 | _ x x x [_] |
accept | _ x x x _ [_] |
q1 | [0] 1 1 0 0 0 # 0 1 1 0 0 0 |
q2 | x [1] 1 0 0 0 # 0 1 1 0 0 0 |
q2 | x 1 [1] 0 0 0 # 0 1 1 0 0 0 |
q2 | x 1 1 [0] 0 0 # 0 1 1 0 0 0 |
q2 | x 1 1 0 [0] 0 # 0 1 1 0 0 0 |
q2 | x 1 1 0 0 [0] # 0 1 1 0 0 0 |
q2 | x 1 1 0 0 0 [#] 0 1 1 0 0 0 |
q4 | x 1 1 0 0 0 # [0] 1 1 0 0 0 |
q6 | x 1 1 0 0 0 [#] x 1 1 0 0 0 |
q7 | x 1 1 0 0 [0] # x 1 1 0 0 0 |
q7 | x 1 1 0 [0] 0 # x 1 1 0 0 0 |
q7 | x 1 1 [0] 0 0 # x 1 1 0 0 0 |
q7 | x 1 [1] 0 0 0 # x 1 1 0 0 0 |
q7 | x [1] 1 0 0 0 # x 1 1 0 0 0 |
q7 | [x] 1 1 0 0 0 # x 1 1 0 0 0 |
q1 | x [1] 1 0 0 0 # x 1 1 0 0 0 |
q3 | x x [1] 0 0 0 # x 1 1 0 0 0 |
q3 | x x 1 [0] 0 0 # x 1 1 0 0 0 |
q3 | x x 1 0 [0] 0 # x 1 1 0 0 0 |
q3 | x x 1 0 0 [0] # x 1 1 0 0 0 |
q3 | x x 1 0 0 0 [#] x 1 1 0 0 0 |
q5 | x x 1 0 0 0 # [x] 1 1 0 0 0 |
q5 | x x 1 0 0 0 # x [1] 1 0 0 0 |
q6 | x x 1 0 0 0 # [x] x 1 0 0 0 |
q6 | x x 1 0 0 0 [#] x x 1 0 0 0 |
q7 | x x 1 0 0 [0] # x x 1 0 0 0 |
q7 | x x 1 0 [0] 0 # x x 1 0 0 0 |
q7 | x x 1 [0] 0 0 # x x 1 0 0 0 |
q7 | x x [1] 0 0 0 # x x 1 0 0 0 |
q7 | x [x] 1 0 0 0 # x x 1 0 0 0 |
q1 | x x [1] 0 0 0 # x x 1 0 0 0 |
q3 | x x x [0] 0 0 # x x 1 0 0 0 |
q3 | x x x 0 [0] 0 # x x 1 0 0 0 |
q3 | x x x 0 0 [0] # x x 1 0 0 0 |
q3 | x x x 0 0 0 [#] x x 1 0 0 0 |
q5 | x x x 0 0 0 # [x] x 1 0 0 0 |
q5 | x x x 0 0 0 # x [x] 1 0 0 0 |
q5 | x x x 0 0 0 # x x [1] 0 0 0 |
q6 | x x x 0 0 0 # x [x] x 0 0 0 |
q6 | x x x 0 0 0 # [x] x x 0 0 0 |
q6 | x x x 0 0 0 [#] x x x 0 0 0 |
q7 | x x x 0 0 [0] # x x x 0 0 0 |
q7 | x x x 0 [0] 0 # x x x 0 0 0 |
q7 | x x x [0] 0 0 # x x x 0 0 0 |
q7 | x x [x] 0 0 0 # x x x 0 0 0 |
q1 | x x x [0] 0 0 # x x x 0 0 0 |
q2 | x x x x [0] 0 # x x x 0 0 0 |
q2 | x x x x 0 [0] # x x x 0 0 0 |
q2 | x x x x 0 0 [#] x x x 0 0 0 |
q4 | x x x x 0 0 # [x] x x 0 0 0 |
q4 | x x x x 0 0 # x [x] x 0 0 0 |
q4 | x x x x 0 0 # x x [x] 0 0 0 |
q4 | x x x x 0 0 # x x x [0] 0 0 |
q6 | x x x x 0 0 # x x [x] x 0 0 |
q6 | x x x x 0 0 # x [x] x x 0 0 |
q6 | x x x x 0 0 # [x] x x x 0 0 |
q6 | x x x x 0 0 [#] x x x x 0 0 |
q7 | x x x x 0 [0] # x x x x 0 0 |
q7 | x x x x [0] 0 # x x x x 0 0 |
q7 | x x x [x] 0 0 # x x x x 0 0 |
q1 | x x x x [0] 0 # x x x x 0 0 |
q2 | x x x x x [0] # x x x x 0 0 |
q2 | x x x x x 0 [#] x x x x 0 0 |
q4 | x x x x x 0 # [x] x x x 0 0 |
q4 | x x x x x 0 # x [x] x x 0 0 |
q4 | x x x x x 0 # x x [x] x 0 0 |
q4 | x x x x x 0 # x x x [x] 0 0 |
q4 | x x x x x 0 # x x x x [0] 0 |
q6 | x x x x x 0 # x x x [x] x 0 |
q6 | x x x x x 0 # x x [x] x x 0 |
q6 | x x x x x 0 # x [x] x x x 0 |
q6 | x x x x x 0 # [x] x x x x 0 |
q6 | x x x x x 0 [#] x x x x x 0 |
q7 | x x x x x [0] # x x x x x 0 |
q7 | x x x x [x] 0 # x x x x x 0 |
q1 | x x x x x [0] # x x x x x 0 |
q2 | x x x x x x [#] x x x x x 0 |
q4 | x x x x x x # [x] x x x x 0 |
q4 | x x x x x x # x [x] x x x 0 |
q4 | x x x x x x # x x [x] x x 0 |
q4 | x x x x x x # x x x [x] x 0 |
q4 | x x x x x x # x x x x [x] 0 |
q4 | x x x x x x # x x x x x [0] |
q6 | x x x x x x # x x x x [x] x |
q6 | x x x x x x # x x x [x] x x |
q6 | x x x x x x # x x [x] x x x |
q6 | x x x x x x # x [x] x x x x |
q6 | x x x x x x # [x] x x x x x |
q6 | x x x x x x [#] x x x x x x |
q7 | x x x x x [x] # x x x x x x |
q1 | x x x x x x [#] x x x x x x |
q8 | x x x x x x # [x] x x x x x |
q8 | x x x x x x # x [x] x x x x |
q8 | x x x x x x # x x [x] x x x |
q8 | x x x x x x # x x x [x] x x |
q8 | x x x x x x # x x x x [x] x |
q8 | x x x x x x # x x x x x [x] |
q8 | x x x x x x # x x x x x x [_] |
accept | x x x x x x # x x x x x x _ [_] |
Read the subsection \"Terminology for Describing Turing Machines\" (184–185).
\n", "This section can be read after Tuesday's class.
\n", "Read the rest of Section 3.3 (182–184).
\n", " \n", "Read page 176.
\n", " \n", "Read the subsection \"Multitape Turing Machines\" (176–178).
\n", "q0 | [1] 0 1 # 1 0 1 | ε |
q1 | [1] 0 1 # 1 0 1 | # [_] |
q1 | _ [0] 1 # 1 0 1 | # 1 [_] |
q1 | _ _ [1] # 1 0 1 | # 1 0 [_] |
q1 | _ _ _ [#] 1 0 1 | # 1 0 1 [_] |
q2 | _ _ _ [#] 1 0 1 | # 1 0 [1] _ |
q2 | _ _ _ [#] 1 0 1 | # 1 [0] 1 _ |
q2 | _ _ _ [#] 1 0 1 | # [1] 0 1 _ |
q2 | _ _ _ [#] 1 0 1 | [#] 1 0 1 _ |
q3 | _ _ _ # [1] 0 1 | # [1] 0 1 _ |
q3 | _ _ _ # 1 [0] 1 | # 1 [0] 1 _ |
q3 | _ _ _ # 1 0 [1] | # 1 0 [1] _ |
q3 | _ _ _ # 1 0 1 [_] | # 1 0 1 [_] |
accept | _ _ _ # 1 0 1 [_] | # 1 0 1 [_] |
Read:\n", "
q0 | [0] 1 0 0 1 0 |
q10 | $ [1] 0 0 1 0 |
q10 | $ 1 [0] 0 1 0 |
q10 | $ 1 0 [0] 1 0 |
q2 | $ 1 [0] # 1 0 |
q2 | $ [1] 0 # 1 0 |
q2 | [$] 1 0 # 1 0 |
q3 | $ [1] 0 # 1 0 |
q41 | $ # [0] # 1 0 |
q41 | $ # 0 [#] 1 0 |
q51 | $ # 0 # [1] 0 |
q6 | $ # 0 [#] # 0 |
q6 | $ # [0] # # 0 |
q2 | $ [#] 0 # # 0 |
q3 | $ # [0] # # 0 |
q40 | $ # # [#] # 0 |
q50 | $ # # # [#] 0 |
q50 | $ # # # # [0] |
q6 | $ # # # [#] # |
q6 | $ # # [#] # # |
q6 | $ # [#] # # # |
q6 | $ [#] # # # # |
q6 | [$] # # # # # |
accept | [$] # # # # # |
You're not responsible for the rest of this section, and you can read it after Thursday's class.
\n", "Watch (optional) W8E6: RAM Machines and Beyond.
\n", "