.Open Class Meeting 07 on Restricted 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 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 Today .Item 7 .Item Chapter 8 sections 8.5, 8.6 .Item Ex .Item Restricted $TM .Row Next .Item 8 .Item Chapter 8 section 8.7+$Minsky .Item Ex .Item The Halting Problem .Item Start $Project .Close.Table (Minsky): Study my six page handout from Minsky's 1964 "Computation: Finite and Infinite Machines". (Project): Working in a team of 3 or 4 people design, code, and test a simple Turing Machine simulator. .Set Notes You may use any language that can be demonstrated in class. You may choose any kind of user interface you like. Your $TM simulator does not have to have infinite memory capacity like a real $TM. Do the simplest thing that can possibly work. Consult with me in my office hours. .Close.Set Process .List Start by thinking about the design and developing tests for your code... First deadline: bring a progress report to class and present it. Grading: pass/fail. Any running set of tests will pass. Second deadline: bring a report on the final status, present it, and hand in a hard copy for grading. .Close.List .See ./projects.html .Open 8.5 Restricted Turing Machines 345 . Ch 8.5 pp 352-353 -- Recursively Enumerable Languages What is a recursively enumerable language? The word dates back to the older theory of `Recursive Functions` when a `recursively enumerable` language was a set of strings that could be generated by a recursive procedure. This name is now given to languages that are accepted by some Turing Machine -- even if rejection some times happens by the machine never coming to a conclusion -- terminating. A .Key recursive language was a language could be recognized by a recursive function. These days -- by a TM that either halts rejecting the language or accepts the language(and halts). One of the key results of the old recursive function theory (we'll research this later...) was that recursive definitions that did not have to terminate on all inputs were more powerful than those that always halted. . 8.5.1 Turing Machines With Semi-infinite Tapes 345 . Ch 8 pp 346 How do we simulate a semi-infinite tape into a two way infinite tape I call this trick/technique `folding the table`. There are two tracks: Upper and Lower and we have a stored value:{U,L} indicating which is which. The lower track is backwards! If we had a two-side tape like this .Table tape ... x y z a b c .Row head - - - - - ^ - - .Close.Table then an equivalent one sided TM is like this: .Table upper a b c .Row lower * z y x .Row head - ^ - - .Row store U .Close.Table If we had a two-side tape like this .Table tape ... x y z a b c .Row head - - - ^ - - .Close.Table then an equivalent one sided TM is like this: .Table upper a b c .Row lower * z y x .Row head - ^ - - .Row store L .Close.Table Also note the trick of pseudo-blanks. . 8.5.2 Multistack Machines 348 Two stacks make a TM. . Ch 8.5.2 pp 349 -- Multistack Machines What's the difference between B the blank symbol and $ the endmarker? A TM doesn't need an "end of input" symbol because it's input has no end..... (but is mosly blank).. The $ end marker is only found after the end of the "real" data input to the acceptor. A blank might appear in the middle of TM data. . Ch 8.5 pp pg349 -- Multistack machines How exactly does a multistack machine work? I understand it is like a PDA, but where does it exactly differ? It can have more than one stack to store intermediate results. Plus it has operations that can pop data off one stack and push it onto another stack. . Ch 8.5.2 pp 348 - 349 -- Multistack Machines Theorem 8.13 Could you explain Theorem 8.13 in more detail, and give an example using the theorem. In class I ran some steps in which two stacks simulated a TM shown earlier in the book. . 8.5.3 Counter Machines 351 . Ch 8.5.3 pp 351 -- Counter Machines Can you demonstrate counter machines using pictures, to give a better understanding? In class I ran one the exercise solutions. Tracing the two counters .Table Input i j .Row abc$ 0 0 .Row bc$ 1 1 .Row ... .Close.Table Think of counter machines as programs with `unsigned long int` variables. It only uses statements like this: .As_is i++; .As_is if(i!=0)i--; else exit(FAILURE); Plus the ability to test two conditions for each variable: .As_is i==0 .As_is i!=0 But remember these variables can get as big as we need. . 8.5.3 And C/C++ .Set 3 or 4 counters make a TM. The machines control unit is a program. It can be coded using labels for states and gotos. We only need 3 very long ints... plus .Set operator ++ operator -- operator ==0 .Close.Set So here is a universal C program:-( .As_is int main(....){ .As_is VeryLongInt i,j,k,l; .As_is q0://initial state .As_is ... .Close.Set . Ch 8.5.3 pp 351 -- Counters What happens if a program does try to subtract from a counter that is at 0? I think that the acceptor halts and rejects the input string. . 8.5.4 The Power of Counter Machines 352 You don't need to learn about CFL's for this course. They will not be mentioned in the final. The trick of using the prime numbers to encode n-tuples into a number is called `Godel numbering`. . 8.5.5 Exercises for Section 8.5 354 There is a misprint in part b that I found on the web site for the book. The correct language is: { 0^n 1^m | m>=n>=1 } Hint. .List The solution for `a` is not on the web -- you can get credit for trying it. Don't attempt the !! exercises. Look at the solution to * c before you attempt b. .Close.List . Ch 8.5.1 c pp 354 -- Counter Machines Would you please explain how to use two counters to describe the language represented by problem 8.5.1 c? I used my solution to this (based on the web solution) as my simulation of a counter machine, above. .Close .Open 8.6 Turing Machines and Computers 355 . 8.6.1 Simulating a Turing Machine by Computer 355 . Ch 8.7 pp 362 -- Words of Fixed Maximum Length Reading the book's explanation on why it allows words to grow by 1 bit at a time, I'm a little confused by why the "more liberal" approach simplifies their proof. Does forcing words to be a fixed maximum length actually reduce the asymptotic complexity of the simulation of a computer by a Turing machine, or is the complexity the same as their "more liberal" approach? If the words don't grow then you have a finite state machine. Then all you have to worry about is the secondary storage: disks and tapes. But the time the simulator requires depends on how much data is stored: TMs don't have random access. So the book works out a way that allows for this to grow -- but not too fast. In effect they are allowing for the fact that real computers take longer to multiply and divide numbers than they do to add, subtract, copy, etc. numbers. . Ch 8 pp 359 -- TM and simulation of a computer Can you go over figure 8.22 and explain how a TM simulates a computer? I did a lot of hand waving... . 8.6.2 Simulating a Computer by a Turing Machine 356 . Ch 8.6.2 pp 356-361 -- Are there things a computer can do that a Turing machine cant ? We had a fun debate: My summary: a TM is not a real machine so has none of the defects of real computers: breakdowns, abuse, pornography, upgrades, ... even tho' we can simulate a lot of these by adding a state. For example [blue screen of death]. . 8.6.3 Comparing the Running Times of Computers and Turing Machines 361 . Ch 5, ch8 pp 361-362 -- Running times of computers and TM I got a bit confused with this section. Is it possible for you to go over the running time differences? Again: hand waving. . Deadline for Class 7 Fewer points if delivered after this message .Close .Close Class Meeting 07 on Restricted Turing Machines . Next The Halting Problem by Minsky .See ./08.html