ToC: Lesson 4 Turing Machines

Journal Nyarly's Journal: ToC: Lesson 4 Turing Machines 2

Journal by Nyarly on Monday August 26, 2002 @04:57PM

Recap: we've spent three lessons building up the ideas of strings and languages and recogition devices and whatnot. Finally we've gotten up to the idea of Finite State Machines, and all their glory. But there's till something missing.

There's still an entire class of languages we can even begin to recognize with anything we've seen so far. Consider a language defined as those strings containing the same number each of three symbols. We'll even make it easy: all of the first symbol will come first, then all the second, then the third. There just isn't a FSM that can recognize a string in that language. If I said "up to ten of each character" (or even "up to a million"), you could build the machine - it amounts to a chain of states that count across the first symbol (e.g."A"), and at the first occurance of the second character, you have a series of states to count for the correct number of the second and then third symbols ("B and C"). If you get to the end of the B-C chain, accept the string, otherwise reject it. Well and good, but if I don't guarantee an upper limit, you need an infinite number of states. Can't we do better than an Infinite State Machine?

Yes, we can. It's called a Turing Machine. "Turing" as in Alan Turing, as in Turing Test, UNIVAC, the Church-Turing thesis, and cracking Enigma during the Second World War. And later harassed by a grateful Britain to the point of suicide.

But leaving that aside for the moment, let's talk about what a Turing Machine is. Take a Finite State Machine. Now take a memory structure. The classic description is a tape, like a long strip of paper, composed of an infinite number of cells into each of which a single symbol can be written. It has a first cell, but no last cell. There's a head that can move left one cell, move right one cell, read the symbol on the tape at its position, or write a symbol to the tape at its position. If it tries to go left from the first cell, it remains where it is. Easy. Now, we attach the tape to the FSM with the following simple rules:

Instead of using just the next symbol in the string, the FSM uses the symbol under the head on the tape.
Consequently, rather than feeding the string into the FSM, we put it on the tape, one symbol per cell.
In addition to changing state, the machine either outputs a symbol to moves the head left or right.

See: simple. Now we can accept our language of like numbers of A's, B's and C's with what amounts to eight states. Quick overview: if you read an A, replace it with a D, and go right until you find a B, which you replace with a D, and then go right until you find a C, which you replace with a D, and then go left until you're back at the beginning. Go right over D's until you find an A and repeat, unless you get to the end of the string, in which case accept the string. If at any time you read a wrong character (an empty cell when you were looking for a C, or a C instead B, or whatever), reject the string. If Slashdot let me do tables, I'd do up the states and outputs, but it doesn't so actually representing the machine is an exercise for the reader.

Notice, as an interesting characteristic of a Turing Machine, that not only can it accept or reject a string, it can not halt at all. This is new, and a necessary result of a Turing Machine's ability to deal with what we'll call recursive languages. The difference is that while a FSM always halts at the end of it's input (and acceptance depended on whether that halt was in an accepting state or not), a Turing machine has an infinite number of ways to never halt. Consider a state where if it reads an A it writes an A. Result: it never halts, reading and writing A's forever. Or if could scan right until it finds an A, and then scan left until it reaches the beginning of the tape. Result: it sweeps back and forth ad infinitum.

There is, in fact, and entire class of languages based on this property. Consider the idea of semidecision, where a Turing Machine accepts a word into a language by halting if it entered as input, but otherwise does not halt. A language for which there is a Turing Machine that halts for it is called recursively enumerable

When you come down to it, Turing Machines are the big deal in this subject of discourse. In fact, the single most important result of any Theory of Computation course deals with Turing Machines. And, that result, and all it's depressing implications, applies to the very machine you're reading this article on, and every other computer, too. But we'll discuss that next lesson.

This discussion has been archived. No new comments can be posted.