Home > Theory of Machines > Theory of Computation: Turing Machines?

Theory of Computation: Turing Machines?

  1. heater2
    November 25th, 2009 at 16:06 | #1

    Your textbook or lecture notes will probably have an example Turing Machine that recognizes 0^n1^n; it’s a standard example. The core idea in that machine is that after you check the formatting of the string (0s then 1s) you scan back and forth, crossing off a 1 for each 0, and see if it all comes out even.
    0^(2n)1^n is just like this, except that you want to cross of a 1 for every *two* 0s. Try to modify the algorithm in the book to do this instead; and think about what happens if, when looking for a pair of 0s, you find only one 0 and the next symbol isn’t a 0.

  1. No trackbacks yet.