[FrontPage] [TitleIndex] [WordIndex

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!

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

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.

2013-07-17 10:43