Turing Machines

Question

I'm reading a book on Languages & Automata and I'm not understanding Turing Machines. I've taught myself about DFA's NFA's and Pushdown Automata without any problems. Can someone please explain what this is doing?

B = {w#w|w ∈ {0, 1}*}

The following figure contains several snapshots of Ml 's tape while it is computing in stages 2 and 3 when started on input 011000#011000.

Thanks alot!

Answer 1

Turing machine is a hypothetical machine with a tape where symbols are stored. It can have multiple heads that can read symbols from the tape or write symbols to the tape.

Now your grammar says B = {w#w|w ∈ {0, 1}*}, that is any string of the form "w#w", where w is any combination of 0's and 1's or none at all. So let's say w = 011000 for this particular example. The resulting string will be 011000#011000 and your turing machine will be verifying if it follows this grammar.

Your turing machine has one head in this case. It starts at the beginning of string. Reads the first character which is 0. Mark it "x": meaning I've read this. Then goes immediately after the # and checks if what it just read is matching. In this case it's 0 as well so it marks it as matching "x". It then goes back to previous position and does the same for next character. It keeps doing this until it reaches #. When it reads hash or #, it checks for the end of the string and if it is the end of string, it accepts this string saying yes this follows the given grammar.

Answer 2

"Imagine an endless row of hotel rooms, and each room contains a lightbulb and a switch that controls it. Initially, all the rooms are dark. A robot starts at one of the rooms, and has the ability to operate switches and move to adjacent rooms.

The robot has several states that it can be in, and each state determines what it should do based on whether the current room is light or dark. For example, a robot's rules could include these states:

The "scared" state:

If the room is dark, turn on the light and move to the room to the left.

If the room is light, do nothing and go to the "normal" state. The "normal" state:

If the room is light, turn off the light and move to the room on the right.

Otherwise, go to the "scared" state.

One special state is the "stop" state. When the robot finds itself in this state, the process is complete.

Suppose a robot has n states (not including the "stop" state), and it stops. What is the maximum number of light rooms at this point?

This system is in direct allegory to Turing machines. The hotel is the tape, the robot is the Turing machine, and dark rooms and light rooms are 0 and 1 cells."

It is from googology wiki. I gave an idea to it, but, of course, this text has been improved since me.