From earlier, State Machines

Recall, if you will, FSAs represent regular expressions, but they can't count. So we added a stack and created push-down automaton which has unbounded storage but without unbounded access - it can only access the top of the stack.

Turing Machines

All reading material will cover this, as well as ReadingRoom/TuringMachines materials. Turing test - test for AI by asking a computer acting as a human and a human questions and seeing if you can figure out which is which. Not particularly related, but neat!

• Instead of just having a stack and only being able to access the top, Turing machines have a tape that allow you to access any square at a time. (Think random access memory.) Structure of the Turing machine will be similar to PDA except the part for the tape. == Components of a Turing machine ==
  • states
  • alphabet (input)
  • alphabet (tape - output)
  • start state
  • set of accepting states
  • set of rejecting states (sometimes)
  • transition table === Transition table ===

    in state w/input under the tape head -> new state, write output and/or move head

JFLAP, again

Apparently JFLAP is great for Turing machines, but I can't easily show one. For each transition you have A : B , C where

• A: what's under the head currently
• B: what to replace it with
• C: L for shift left, R for shift right, S for stay

Random leftover bits

You can use deterministic or non-deterministic Turing machines. You can also rewrite a two way infinite tape (-2, -1, 0, 1, 2) as an one way infinite tape (0, 1, -1, 2, -2) by also rewriting your transition table. This simply proves that a two way tape isn't any more powerful than a one way tape, but it may save you time to have a two way tape instead of having to interleave them for a one way tape. You can, also add a second (or third, if you're craaazy) tape, but again you can combine these into one tape, showing that you get no additional power. You end up with no additional power, but it will be incredibly ugly (think converting NFSA into DFSA). All of this is just to show that you need no additional machinery to add a second tape.

• The point: A two tape Turing machine is a faster Turing machine, but it's still a Turing machine. You can't do anything more powerful than a single tape Turing machine, but it can be substantially easier to build, understand, and run.