.Open Programming and Extending Turing Machines . Context .Table Date .Item Meet'g .Item Study(2 pts) .Item Bring(5 pts) .Item Topic(5 pts) .Item Notes .Row Previous .Item 5 .Item Chapter 8 sections 8.1, 8.2 .Item Ex .Item Turing Machines $TM .Row Today .Item 6 .Item Chapter 8 sections 8.3, 8.4 .Item Ex .Item Programming $TM .Row Fri Apr 21 .Item - .Item - .Item - .Item Last day to drop .Row Next .Item 7 .Item Chapter 8 sections 8.5, 8.6 .Item $Ex .Item Restricted $TM .Close.Table .Open 8.3 Programming Techniques for Turing Machines 329 . 8.3.1 Storage in the State 330 . Ch 8.3.1 pp 330-331 -- Storage in the State I\'m terribly confused on how this process works. Can you detail why the transition function is defined as it is? A Turing machine has a finite number of states in its CPU. However, the number of states is not always small (like 6). Like a Pentium chip we can store values in it -- as long as there are only finite number of them. For example all real computers have registers but there are only a fixed number of them, AND each register can only hold one of a fixed (and finite) number of bits. Example: a simple computer with control unit holding a PC with a 16bit address + arithmetic unit holding one double length 64 bit Arithmetic Register. This has stores 40 bits of information plus a small internal control state: {fetch, decode, compute, store, next} perhaps. So we have a finite state machine with 2^80 states! It is sad that we don't have a high level language for TMs then we could write statements like x=tape.head; perhaps. Suppose that we wanted to code (in C++) a TM with states 'q0', 'q1',... plus storage 'x' we might write code like this .As_is q0: b=tape.head; tape.move_right(); goto q1; .As_is q1: if(tape.head()==B) return FAILS; .As_is if(tape.head()==x) tape.move_right(); goto q1; .As_is ... . Ch 8.4 pp 830-831 -- Example 8.6 I found it very confusing, the idea of storage in states. Could you go over this kind of problem? And is it beneficial to convey the transition function in table format, as it was done in sections 8.1 and 8.2, for this example and what would the table be in this case? A typical transition table when data is being stored has entries like this .Table State Read Next Write Move .Row (q0,B) 1 (q1,1) 1 R .Row (q0,B) 0 (q1,0) 0 R .Close.Table We might interpret this as part of a step that stores the symbol read from the tape in the CPU. Note: the book uses "[]" where I use "()". Tabulating the 6 states >< 3 symbols on page 331 is not difficult and may help. But suppose you have a CPU that has 6 binary flags stored in it plus 3 control states. Now you have 3*64 states to write down... Tabulating all possible states is not very helpful for machines with structured or compound states.... unless you allow variables and conditions to appear in the state descriptions AND expressions in the body of the table. The other thing missing from the table is the documentation that explains what each transition means. . 8.3.2 Multiple Tracks 331 . Ch 8 pp 331 -- Multitrack Turing Machine Can you explain multiple track idea and its relation to the Turing Machine? And maybe show one example in class? Key idea: \Gamma is the Cartesian product of a finite number of finite sets. (Cartesian product works like a struct in C/C++) For example: computer tape storage is multi-track tape with something like 8 or 9 bits in each cell. You can recognise a multi-track machine by looking at the transitions because each will have `tuples` as the read and write symbols. .As_is (*,1)/(B,0)-> .As_is (*,0)/(B,1)-> .As_is (B,0)/(B,0)-> .As_is (B,1)/(B,1)-> Suppose that all of the above are on a loop from `q` to `q` in a diagram then we have these entries in the table: .Table State Next Read Write Move .Row q (*,1) q (B,0) R .Row q (*,0) q (B,1) R .Row q (B,1) q (B,1) R .Row q (B,0) q (B,0) R .Close.Table Both have the effect of taking a marked (*) bits and flipping them. Exercise: complete the \delta descriptions that fit with the above: .Set ... \delta(q, (*,i)) = (___________,_________, R), \delta(q, (_____,i)) = (B,i, R), ... .Close.Set Note the book is using "[]" in place of '()' for tuples. Other books use '<>'! . Error on page 332 In the description of \Sigma does not mention the encoding of "c" as `[B,c]`. . Ch 8.3.2 pp 331-333 -- Multiple Tracks In example 8.7, i had problem understanding the transition functions, and the duty or assignment for each part in the function. Can you explain, what each part of the transition function is supposed to mean or do? . 8.3.3 Subroutines 333 . Ch 8 pp 335 -- Subroutines Would you please explain a little bit more on figure 8.14 and figure 8.15, on how the subroutine Copy works? . 8.3.4 Exercises for Section 8.3 334 .Close .Open 8.4 Extensions to the Basic Turing Machine 336 . 8.4.1 Multitape Turing Machines 336 Note: try not to confuse a multi-tape machine with a multi-track single tape machine! You can recognize a multitape machine by its table of transitions. Here is a piece of a 2-tape machine .Table State Symbol1 Symbol2 New1 New2 Move1 Move2 .Row q0 a b c d L R .Row ... .Close.Table Which means that in state `q0`, if the first head sees an "a", and the second head sees a "b" then it write "c" on tape 1 and moves that head left, and it also writes "d" on tape 2 and moves that head right. Notice that we have two symbols that are read, two are written and their are two moves. The transition would be something like: .As_is ab/cd<--> . Ch 8 pp 335 -- Figures 8.15 8.16 8.17 Could you please explain the two diagrams step by step. Figure 8.15 and figure 8.16 or 8.17 . Ch 8.4.1 pp 336 -- Multitape Turing Machines Why use multi-tape Turing Machines if they are equivalent to single tape Turing Machines? They are easier to program.... and run `faster`. . 8.4.2 Equivalence of One-Tape and Multitape TM's 337 . 8.4.3 Running Time and the Many-Tapes-to-One Construction 339 . Ch 8.4.3 pp 339-340 -- Introduction to Turing Machines Could you go over how Many-Tapes-to-One Construction is used in the time complexity of a TM? This wasn't clear to me in the chapter. . 8.4.4 Nondeterministic Turing Machines 340 . Ch 8 pp 340 -- Nondeterministic Turing Machine Can you clarify the difference between a nondeterministic Turing Machine and a deterministic one? . Ch 8.4 -- NTM How does a nondeterministic Turing machine differ from a deterministic Turing machine? Group discussion: what makes a TM non-deterministic? .Set The machine has choices in some states and with some symbols: there is at least one pair of state>