Models of Computation | Lecture Notes 10

2016 October 17. Monday.

What is this?

Fall 2016, University of Kentucky, Models of Computation, CS 575, with Dr Judy Goldsmith. These incomplete lecture notes are just my own, not proofread or endorsed by Dr G or UKY.

Reminder of what a turing machine is

You have a piece of scotch tape. The tape starts on the left and goes forever towards the right. The tape is broken into one-inch squares. Each square can either contain a letter or be empty. You put a carpenter ant on the first square. The ant has a finite number of states it can be in. (They might be {“looking for food”, “carrying food home”, “running away from danger”}.) The ant also knows, in a given state, what actions each letter correspond to. So maybe our ant is in state $S\_4$ , sees a letter $c$ on the ground, and it knows in its programming that it should switch to state $S\_2$ , replace the $c$ with an $f$ , and move left.

Remember that a Deterministic Finite Automaton was a machine that would take in a string and either accept or reject it. Same with the turing machine. You write your string on the squares of the tape and the ant will either accept or reject. (Well now it might also run forever.)

The languages accepted by a turing machine

Remember that a language is some set of strings. Remember that DFAs are limited in that they cannot describe some languages. For example, it is not possible to construct a DFA that accepts exactly $L = \{a^n b^n : n \in \mathbb{N} \}$ . We say a language is regular if there is some DFA that describes it. For turing machines, the word is recursively enumerable. Here is a picture that shows the hierarchy:

Simulate two way tape with a one way tape

The normal turing machine is only infinite one direction. Showing that you can simulate a turing machine whose tape is infinite both ways, using the normal one.

Here is a random normal turing machine:

b|b|a|a|a|b|a|b|e|e|e|…

Here is that same machine with the states labeled in order:

0|1|2|3|4|5|6|7|8|9|10|… b|b|a|a|a|b|a|b|e|e|e|…

Here is a random turing machine that is infinite both directions:

…|-6|-5|-4|-3|-2|-1|0|1|2|3|4|5|6|… …|e|e|b|a|b|a|a|a|a|a|a|e|e|…

Here is that same machine numbered in a weird way:

…|11|9|7|5|3|1|0|2|4|6|8|10|12|… …|e|e|b|a|b|a|a|a|a|a|a|e|e|…

And here is a normal turing machine that copies from that last one:

0|1|2|3|4|5|6|7|8|9|10|11|12|… a|a|a|b|a|a|a|b|a|e|e|e|e|…

So we’ve copied the two-way tape onto our one-way tape. Now we just need to add in the programming and our construction will work.

If the old machine was in the positive half and moved right, the new machine moves right two.
If the old machine was in the positive half and moved left, the new machine moves left two.
If the old machine was in the negative half and moved left, the new machine moves right two.
If the old machine was in the negative half and moved right, the new machine moves left two.
If the old machine went from 0 to -1, our new machine moves right one.

And that’s lecture.

Public Domain Dedication.