**Reading**-
Sections 4.1 of
*Theory of Computing, A Gentle Introduction*, introduces Turing Machines. But we're really only worrying about the first 3 pages of that section right now. **Homework**- Then printout the homework and answer the questions on that paper.

**Introduction**-
We've considered two computational models so far: FAs and
PDAs. We've proved a wide variety of things about what these
models are capable of computing and what they're not capable
of computing. From a practical standpoint, these models are
extremely important. From them we get algorithms for pattern
matching (as in egrep and perl) and parsing (as in bison), and
the formalisms of regular expressions and grammars are used in
specifications of programming languages, data formats and
protocols. From a theoretical standpoint, however, they're
both just warm-ups for the main event: a computational model
with the full power of what we call "a computer".
This model is called a

*Turing Machine*, and it was invented and investigated by Alan Turing in the 1930's ... before we really had computers! Essentially, it is a finite automaton + an array. In particular:- We let our FA's input tape be infinitely long to the right (i.e. 1-way infinite),
- we let the machine write on it as well as read from it, and
- we let the machine dictate how the tape read/write head moves and when computation halts.

Each transition is labeled with three things: the symbol you read, the symbol you write, and the tape head move you make ("L" for left, "R" for right, and "S" for stay). There is a special state called the "halt state", and after transitioning to that state, the computation stops. If you move left from the leftmost square of the tape, the Turing machine "crashes".

For this class we played with examples of such machines using JFLAP. Once we're familiar with them informally, we'll go back and give formal definitions.

**Example 1**-
Below is a simple Turing Machine that erases it's input.
Note: the "
This machine writes a blank no matter what it reads, and keeps moving right. When it reads the first blank (i.e. the end of the input) it halts. We specifically ran it in class on the input tape

`a`

`b`

`b`

**Lab Excercises**-
The following problems were given as excercises in class.
You'll use JFLAP
and choose the
*Turing Machine*option. [**Note:**JFLAP's Turing machine model is slightly different than ours. The JFLAP Turing machine has a two-way infinite tape, rather than one-way. I want you to avoid using JFLAP's two-way infiniteness! In other words, your machine should never touch the tape square that is left of the square the tape head originally points to!] Construct Turing Machines (input alphabet is {a,b} for all problems) with JFLAP that:-
swaps all the
*a*s and*b*s in the input. E.g.`abb`

→`baa`

. -
swaps all the
*a*s and*b*s in the input and leaves the read/write head pointing to the first character in the string.

**Note:**This should be a 1-way infinite tape solution! I.e. your machine should never touch the tape square that is left of the square the tape head originally points to! -
Copies the first letter of the string to the square
following the first blank after the string.
E.g.
`abb`

→`abb a`

. -
Copies the input with a blank in between the input and the
copy. E.g.
`abb`

→`abb abb`

. - Halts if the input is a palindrome, goes into an infinite loop otherwise.

**Note:**Please save each machine as a separate JFLAP file. You might need them later! -
swaps all the

Christopher W Brown Last modified: Wed Nov 18 13:30:09 EST 2009