Turing machines are a model of computation

Caution: this section is a work in progress

Consider the following Turing machine:

Try out this machine by putting in a string below. Be sure to quote your input string with double quotes, and stick to the alphabet within the quotes! Press the play button, then use the step button to simulate each step of the Turing machine one at a time. Try with a few strings, and see if you can figure out what the machine is doing.

Alphabet is: {A, C, G, T}

Input should be surrounded by double quotes

Have you figured out what the machine is doing?

Reveal answer

In short, this machine replaces the last T in the input with an A.

To understand how the machine operates, let's break down the different parts of its algorithm:

The self-transition on q0 moves the read/write head to the right until a blank is reached.
Once the blank is reached, the machine goes to q1.
The self-transition on q1 moves the read/write head to the left until a T is found. Because the machine is scanning from right to left at this point, the T that is found is guaranteed to be the very last one in the input.
Finally, that T is replaced by an A, and the machine goes to qH.

For this reason, we will be calling this machine the lastTtoA machine.

Writing out each transition separately is a bit tedious, so we will introduce some abbreviation:

When there are multiple transitions that have the same replacement behavior (writes the same character, or does not write anything) and movement between the same pair of nodes, we can simply write the all the characters to read before the semicolon. For example, two transitions A;R and C;R can be collapsed as AC;R.

How would you abbreviate the lastTtoA Turing machine according the rules above?

Reveal answer

Here's another machine you can play around with. Unlike the previous example, this machine is an acceptor, not a transducer. Can you figure out which strings this machine accepts?

Because I ask students to determine the behavior of this machine as an exercise in my class, I'm not providing the solution to the above question here.

Alphabet is: {0, 1, #}

Input should be surrounded by double quotes

Turing machines can be encoded as strings

In Chapter 1, we saw how complex objects, such as graphs, can be encoded as a string. Turing machines can also be encoded as strings. Let's explore how with an example.

Let's look at the lastTtoA Turing machine again:

Here, we see the machine as diagram, a visual representation that is not easy for computers to work with. To represent the machine as a string, the first step is to identify what important characteristics are needed to fully describe the machine. Can you identify what these characteristics are?

Reveal answer

To fully describe the machine, we need to describe:

The states in the machine.
Which state is the initial state.
Which states are halt, accept and reject states.
What the different transitions are.

And that's it! Just like with graphs, the layout of the states doesn't change the structure (and therefore the behavior) of the machine.

Try to come up with your own string encoding to represent Turing machines as strings. Make sure you fully capture all the characteristics of the machine as listed above. Then, take a look at the example encoding below:

Reveal answer

"q0->q0: CGTA;R
 q0->q1: _;L
 q1->q1: CGA_;L
 q1->qH: T;A,S"

Each line represents a transition between two states, with the parameters of the transition (which character is read, which character is written and how the read/write head moves) following the states. Here's how this encoding captures all the characteristics of the machine:

States are implicitly listed out by being present in the various transitions.
q0 is assumed to be the initial state.
qH, qA and qR are assumed to be the halt, accept and reject states respectively.
The transitions are listed out line by line.

There are plenty of problems with this encoding. For example, because we assign :, -> and various other characters special meaning in the encoded string (for example, : separates the states in a transition from the parameters of the transition), any machine that uses those characters in the state names or the transition parameters can't be represented with this encoding. However, we will assume our Turing machines don't use these characters, so this encoding will suffice for our purposes. Hopefully, your encoding was better!

Nondeterministic Turing machines let you try multiple possibilities

Alphabet is: {x, A, C, G, T}

Input should be surrounded by double quotes