Class 34: Introduction to Turing Machines

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

1. Using JFLAP, construct a machine that reads in a string over the alphabet {a,b}, erases it, and prints a "1" on the tape if its lenght is odd and a "0" if its lenth is even. For example, if "aabba" is on the tape when the machine starts, just "1" should be on the tape when the machine halts.

2. One fun thing you can do with a Turing Machine is to send it into an infinte loop. The following machine halts if its input begins with a, and goes into an infinite loop otherwise. I mean, it's one way of showing that you don't like a string. You can think of it as throwing a tantrum.

   

   Use JFLAP to construct (and test!) a machine that halts when its input is a palindrome over {a,b} and goes into an infinite loop otherwise. What you leave on the tape is up to you.

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. We let our FA's input tape be infinitely long, we let the machine write on it as well as read on it, and we let the machine dictate how the tape read/write head moves and when computation halts.

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 "  " in the transitions stands for a blank.

This machine writes a blank no matter what it reads, and keeps moving right. When reads the first blank (i.e. the end of the input) it halts.

Lab Excercises

The following problems were given as excercises in the lab. Construct a machine with JFLAP that:

1. swaps all the as and bs in the input. E.g. abb → baa.

2. swaps all the as and bs in the input and leaves the read/write head pointing to the first character in the string.

3. Copies the first letter of the string to the square following the first blank after the string. E.g. abb → abb a.

4. Copies the input. E.g. abb → abb abb.

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