Basics: The Turing Machine (with an interpreter!)

As long as I'm doing all of these basics posts, I thought it would be worth
explaining just what a Turing machine is. I frequently talk about things
being Turing equivalent, and about effective computing systems, and similar things, which all assume you have some clue of what a Turing machine is. And as a bonus, I'm also going to give you a nifty little piece of Haskell source code that's a very basic Turing machine interpreter. (It's for a future entry in the Haskell posts, and it's not entirely finished, but it does work!)

The Turing machine is a very simple kind of theoretical computing device. In
fact, it's almost downright trivial. But according to everything that we know and understand about computation, this trivial device is capable of any computation that can be performed by any other computing device.

The basic idea of the Turing machine is very simple. It's a machine that runs on
top of a tape, which is made up of a long series of little cells, each of which has a single character written on it. The machine is a read/write head that moves over the tape, and which can store a little bit of information. Each step, the
machine looks at the symbol on the cell under the tape head, and based on what
it sees there, and whatever little bit of information it has stored, it decides what to do. The things that it can do are change the information it has store, write a new symbol onto the current tape cell, and move one cell left or right.

That's really it. People who like to make computing sound impressive often have
very complicated explanations of it - but really, that's all there is to it. The point of it was to be simple - and simple it certainly is. And yet, it can do
anything that's computable.

To really understand how that trivial machine can do computations, it helps to be a bit formal. In formal terms, we talk about a turing machine as a tuple: (S, s0, A, T), where:

  • S is a finite list of possible states that the machine can be in. The state is the information that the machine can store in the head to make decisions. It's a very limited amount of information; you can think of it as either
    a specific list of states, or a small set of small numbers. For most Turing machines,
    we'll use it as a specific list of states. (You'll see what I mean in a minute.)
  • s0S is the initial state - the state that the
    machine will be in when it starts a computation.
  • A is the machine's alphabet, which is the set of symbols
    which can appear on the machine's tape.
  • T is the machines transition function. This is the real
    heart of the machine, where the computation is defined. It's a function from
    the machine state and the alphabet character on the current tape cell to the
    action that the machine should take. The action is a triple consisting of
    a new value for the machine's state, a character to write onto the current
    tape cell, and a direction to move the tape head - either left or right.

So, for example, let's look at a simple machine. This is one of the classic
examples: a Turing machine that does subtraction using unary numbers. A unary
number "N" is written as a series of N 1s. For the program, we'll give the machine an
input in the format "N-M=" written onto the tape; after running the machine, the tape
will contain the value of M subtracted from N. So, for example, we could use "1111-11="
as an input; the output would be "11".

The alphabet is the characters "1", " " (blank space), "-" (minus sign), and "=" (equal sign). The machine has four states: {"scanright", "eraseone", "subone", "skip"}. It starts in the state "scanright". It's transition function is given by the following table:

FromState Symbol ToState WriteChar Dir
scanright space scanright space right
scanright 1 scanright 1 right
scanright minus scanright minus right
scanright equal eraseone space left
eraseone 1 subone equal left
eraseone minus HALT space n/a
subone 1 subone 1 left
subone minus skip minus left
skip space skip space left
skip 1 scanright space right

What this machine does is move to the right until it sees the equal sign; it erases the equal sign and moves to the left, erases one digit off of the second number, and replaces it with the equal sign (so the second number is reduced by one, and the equal sign is moved over one position). Then it scans back to the minus sign (which separates the two numbers), and erases one digit of the first number, and then switches back to scanning to the right for the equal. So one at a time, it erases one digit from each of the two numbers. When it reaches the equal sign, and starts going back to erase a digit from the second number, and hits the "-" before it finds a digit, that means its done, so it stops. Let's look at a simple execution trace. In the trace, I'll write the
machine state, followed by a colon, followed by the tape contents surrounded by "[]", with the current tape cell surrounded by "{}".

scanright:  [ {1}1111111-111= ]"
scanright:  [ 1{1}111111-111= ]"
scanright:  [ 11{1}11111-111= ]"
scanright:  [ 111{1}1111-111= ]"
scanright:  [ 1111{1}111-111= ]"
scanright:  [ 11111{1}11-111= ]"
scanright:  [ 111111{1}1-111= ]"
scanright:  [ 1111111{1}-111= ]"
scanright:  [ 11111111{-}111= ]"
scanright:  [ 11111111-{1}11= ]"
scanright:  [ 11111111-1{1}1= ]"
scanright:  [ 11111111-11{1}= ]"
scanright:  [ 11111111-111{=} ]"
eraseone :  [ 11111111-11{1}  ]"
subone   :  [ 11111111-1{1}=  ]"
subone   :  [ 11111111-{1}1=  ]"
subone   :  [ 11111111{-}11=  ]"
skip     :  [ 1111111{1}-11=  ]"
scanright:  [ 1111111 {-}11=  ]"
scanright:  [ 1111111 -{1}1=  ]"
scanright:  [ 1111111 -1{1}=  ]"
scanright:  [ 1111111 -11{=}  ]"
eraseone :  [ 1111111 -1{1}   ]"
subone   :  [ 1111111 -{1}=   ]"
subone   :  [ 1111111 {-}1=   ]"
skip     :  [ 1111111{ }-1=   ]"
skip     :  [ 111111{1} -1=   ]"
scanright:  [ 111111 { }-1=   ]"
scanright:  [ 111111  {-}1=   ]"
scanright:  [ 111111  -{1}=   ]"
scanright:  [ 111111  -1{=}   ]"
eraseone :  [ 111111  -{1}    ]"
subone   :  [ 111111  {-}=    ]"
skip     :  [ 111111 { }-=    ]"
skip     :  [ 111111{ } -=    ]"
skip     :  [ 11111{1}  -=    ]"
scanright:  [ 11111 { } -=    ]"
scanright:  [ 11111  { }-=    ]"
scanright:  [ 11111   {-}=    ]"
scanright:  [ 11111   -{=}    ]"
eraseone :  [ 11111   {-}     ]"
Halt:       [ 11111  { }-     ]"

See, it works!

One really important thing to understand here is that we do not have a program. What we just did was define a Turing machine that does subtraction. The machine does not take any instructions: the states and the transition function are an intrinsic part of the machine. So the only thing this machine can do is to subtract.

The real genius of Turing wasn't just defining this simple computing machine. It was realizing the concept of the program: you could design a Turing machine whose input tape contained a description of a Turing machine - that is a program - followed by an input to the program. This single machine - the Universal Turing machine - could simulate any other Turing machine; one machine which could perform any computation.

Turing machines are a lot of fun to play with. Figuring out how to do things
can be fascinating. Figuring out how to define a Universal turing machine's transition function is an amazing thing to do; it's astonishing how simple the universal machine can be!

For your enjoyment, I've implemented a Turing machine programming language. You feed it a Turing machine description, and an input string, and it will give you a
trace of the machines execution like the one above. Here's the specification of the
subtraction machine written in my little Turing language:

states { "scanright" "eraseone" "subtractOneFromResult" "skipblanks" } initial "scanright"
alphabet { '1' ' ' '=' '-' } blank ' '
trans from "scanright" to "scanright" on (' ') write ' ' move right
trans from "scanright" to "scanright" on ('1') write '1' move right
trans from "scanright" to "scanright" on ('-') write '-' move right
trans from "scanright" to "eraseone" on ('=') write ' ' move left
trans from "eraseone" to "subtractOneFromResult" on ('1') write '=' move left
trans from "eraseone" to "Halt" on ('-') write ' ' move left
trans from "subtractOneFromResult" to "subtractOneFromResult" on ('1') write '1' move left
trans from "subtractOneFromResult" to "skipblanks" on ('-') write '-' move left
trans from "skipblanks" to "skipblanks" on (' ') write ' ' move left
trans from "skipblanks" to "scanright" on ('1') write ' ' move right

I think it's pretty clear as a syntax, but it still needs explanation.

  • The first line declares the possible states of the machine, and what state it starts in. This machine has four possible states - "scanright", "eraseone", "subtractOneFromResult", and "skipblanks". When the machine starts, it will be in the state "skipright".
  • The second line declares the set of symbols that can appear on the tape, including what symbol will initially appear on any tape cell whose value wasn't specified by the input. For this machine the symbols are the digit 1, a blank space, the equal sign, and the subtraction symbol; the blank symbol is on any tape cell whose initial value wasn't specified.
  • After that is a series of transition declarations. Each declaration specifies
    what the machine will do for a given pair of initial state and tape symbol. So, for example, if the machine is in state "scanright", and the current tape cell contains the equal-to sign, then the machine will change to state "eraseone", write a blank
    onto the tape cell (erasing the "=" sign), and move the tape cell one position
    to the left.

Finally, the code. You'll need GHCI to run it; at the moment, it won't work in
Hugs (I don't have the parsing library in my version of Hugs), and I haven't worked
out the linkage stuff to make it work under the GHC compiled mode.


--
-- A Simple Turing machine interpreter
-- Copyright 2007 by Mark C. Chu-Carroll
--    markcc@gmail.com
--   http://scienceblogs.com/goodmath
-- 
-- You can do anything you want with this code so long as you
-- leave this copyright notice intact.
--
module Turing where
import Text.ParserCombinators.Parsec
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language 
import System.Environment

data Motion = MoveLeft  | MoveRight deriving (Show)

data Transition = Transition String String [Char] Motion  Char deriving (Show)
--                           from    to      on    move   write

data TuringMachine = Machine [String] String   [Char]    Char    [Transition] deriving (Show)
--                           states   initial  alphabet  blank   transitions

data MachineState = TMState [Char] Char [Char]  String  deriving (Show)
--                           tape-left curcell  curstate

getBlankSym :: TuringMachine -> Char
getBlankSym (Machine _ _ _ bl _) = bl 

findMatchingTransition :: [Transition] -> String -> Char -> Maybe Transition
findMatchingTransition [] _ _ =  Nothing
findMatchingTransition translist state c =
     let matches = filter (transitionMatches state c) translist
     in case matches of
          [] -> Nothing
          t:[] -> Just t
          _ -> error "Ambiguous transition" 
       where transitionMatches state c (Transition from to on move write) =
                        (from == state) && (elem c on)

runTransition :: TuringMachine -> [Char] -> Char -> [Char] -> String -> Transition -> MachineState
runTransition m (l:left) c right state (Transition from tostate on MoveLeft write) =
   TMState left l (write:right) tostate
runTransition m left c [] state (Transition from tostate on MoveRight write) =
   TMState (write:left) (getBlankSym m) [] tostate
runTransition m left c (r:right) state (Transition from tostate on MoveRight write) =
   TMState (write:left) r right tostate

stepMachine :: TuringMachine -> MachineState -> MachineState
stepMachine machine@(Machine _ _ _ _ translist) st@(TMState tapeleft c taperight state) =
       let trans = findMatchingTransition translist state c 
       in case trans of
          (Just t) -> runTransition machine tapeleft c taperight state t
          Nothing -> error "No applicable transition from state"




getMachineStateString (TMState left c right state) =
(state ++ ":[" ++ (reverse left) ++ "{" ++ [c] ++ "}" ++ right ++ "]")

runTracedMachine :: TuringMachine -> [Char] -> [String]
runTracedMachine tm@(Machine states initial alphabet blank transitions) (t:tape) =
    runTracedMachineSteps tm (TMState [] t tape initial) where
        runTracedMachineSteps machine state =
           let newstate@(TMState left c right st) = stepMachine machine state
           in if st == "Halt" 
               then [getMachineStateString newstate]
               else let trace=runTracedMachineSteps machine newstate
                    in ((getMachineStateString newstate):trace)




runMachine :: TuringMachine -> [Char] -> [Char]
runMachine tm@(Machine states initial alphabet blank transitions) (t:tape) =
    runMachineSteps tm (TMState [] t tape initial) where
        runMachineSteps machine state =
           let newstate@(TMState left c right st) = stepMachine machine state
           in if st == "Halt" 
               then (concat [(reverse left), [c], right])
               else runMachineSteps machine newstate


---------------------------------------------------------------------------
-- Parsing code - implemented using the Parsec monadic parser library.
---------------------------------------------------------------------------

-- Basic setup stuff - use a standard haskell style lexer; set up the reserved words
-- and symbols in the lexer.
lexer :: P.TokenParser ()
lexer = P.makeTokenParser (haskellDef
                        { P.reservedNames = ["states","alphabet","trans","from","to","on","write","move","left","right","initial","blank"] })


reserved = P.reserved lexer
symbol = P.symbol lexer
braces = P.braces lexer
parens = P.parens lexer
charlit = P.charLiteral lexer
strlit = P.stringLiteral lexer
ident = P.identifier lexer
whitespace = P.whiteSpace lexer

states = reserved "states"
alphabet = reserved "alphabet"
trans = reserved "trans"
from = reserved "from"
to = reserved "to"
on = reserved "on"
write = reserved "write"
move = reserved "move"
initial = reserved "initial"
blank = reserved "blank"

left = do { reserved "left"
          ; return MoveLeft
          }

right = do { reserved "right"
           ; return MoveRight
           }

-- statesDecl ::= "states" "{"  strlit+  "}" "initial" strlit
statesDecl = do { states
                ; strlst  right)
   ; return (Transition fromState targetState chrs dir wrchar)
               }


-- machine ::= statesDecl alphaDecl transDecl+
machine = do { (i,sts)  Parser a -> String -> IO a
run p input 
= case (parse p "" input) of 
Left err -> do{ putStr "parse error at " 
; print err 
; error "Parse error"
} 
Right x -> return x 


runTParser ::  String -> IO TuringMachine
runTParser input =
run (do { whitespace
        ; x  String -> IO ([String])
runTracedMachineOnString m str =
do
tm  String -> IO String
runMachineOnString m str =
    do
    tm  do   
             print "Enter input for parser:"
             s  do
        print (concat ["Parse error"])

runFromFile :: String -> IO ()
runFromFile filename =
do
       m  do   
             print "Enter input for parser:"
             s  do
        print (concat ["Parse error"])
Categories

More like this

So I spent two weeks in Wyoming, participated in a wedding in Louisiana, moved two apartments worth of stuff, visited Louisiana again to get a marriage license for myself (20 days left!), collected data for an experiment demonstrating a new result we're trying to get published quickly (hot topic,…
What started me on this whole complexity theory series was a question in the comments about the difference between quantum computers and classical computers. Taking the broadest possible view, in theory, a quantum computer is a kind of non-deterministic machine - so in the best possible case, a…
One of my fellow ScienceBloggers, [Karmen at Chaotic Utopia](http://scienceblogs.com/chaoticutopia/2006/11/puzzling_at_a_simpleminde…) pointed out a spectacularly stupid statement in [Casey Luskin's critique of Carl Zimmer][lutkin] (*another* fellow SBer) at the Discovery Institutes "Center for…
"The miracle of the appropriateness of the language of mathematics for the formulation of the laws of physics is a wonderful gift which we neither understand nor deserve." - E. P. Wigner Our universe, or at least our understanding of the universe, appears to allow us to see its naked underbelly…

Note that for a much simple Turing machine syntax, you can find a bunch of solutions by lookint at this old Perl Quiz-of-the-Week. For example, there's this TM interpreter in perl, and this one in Haskell (much shorter than the one posted above).

There's even this TM program that solves an earlier perl quiz-of-the-week with a turing machine. (Though the given perl code to clean the output has a typo; I should have left out the $_= bit)

There's also a TM program that multiplies two base ten numbers.

Just a little error check:

The first line declares the possible states of the machine, and what state it starts in. This machine has four possible states - "scanright", "eraseone", "subtractOneFromResult", and "skipblanks". When the machine starts, it will be in the state "skipright".

That last word should be "scanright", correct?

The things that [a Turing machine] can do are change the information it has store, write a new symbol onto the current tape cell, and move one cell left or right.

Makes Sal's observation that living cells contain Turing machines seem rather unspectacular. Heck, just about any catalyst could be considered a basic Turing machine, right?

By Anonymous (not verified) on 04 Feb 2007 #permalink

Oops, forgot to sign my name on that last comment. Didn't mean to sound like a coward or anything like that.

For what it is worth, it works with the full latest version of (Win)Hugs, which includes most of the hierarchical libraries including Parsec.

By Ãrjan Johansen (not verified) on 04 Feb 2007 #permalink

To get it to compile you'll need to change the module name to Main.

After that ghc -package parsec Turing.hs should compile it.

You don't need to modify the code - it'll compile as written if you compile it with:

ghc -package parsec -main-is Turing Turing.hs

(If you had already attempted to compile it without the proper options, you'll need to delete the .hi file first)

Note that there's either a bug or an oversight: the error that you get if you go off the left end of the tape is the error from Haskell telling you that the runTransition function doesn't handle all possible cases, rather than something specific to the tape.

To see this, run the sample program with an input tape of "11-111=".

Also, in contrasting Mark's Turing machine interpreter with the one I wrote long ago, I notice some design decisions that I made differently which I think made the code easier to deal with. (However, those decisions kill the "derives Show" ability which Mark seems very fond of)

I'll rework the code a bit to use my decisions and see if it becomes any cleaner.

just about any catalyst could be considered a basic Turing machine

Interesting observation. It could probably be correct if you allow one state, one direction and a probabilistic 'tape'. (Though the 'head' will see see the same symbol all the time.) Some enzymes could probably be reconfigured (to inactivate them, for example) but that wouldn't be under program control.

But perhaps parts of the cell translation machinery more closely fits the bill as basic Turing machines if enzymes doesn't cut it. (As I believe several 'tapes' are allowed.) For example ribosomes as read/write heads. They read a messenger RNA 'tape' and writes a protein 'tape'. And change state under RNA 'tape' control when they attach at the start codon and detach at the termination codon (with some help from release factors) ( http://en.wikipedia.org/wiki/Ribosomes ; http://en.wikipedia.org/wiki/Eukaryotic_translation ).

By Torbjörn Larsson (not verified) on 04 Feb 2007 #permalink

As I responded to a post about a year ago (http://goodmath.blogspot.com/2006/03/turing-machine-tricks.html), there is this program vturing.exe aka "Visual Turing" that presents an animated display. In fact, that comment is now the _only_ google hit for vturing.exe. So I do not know the legal case for handing it out (it was a freeware program), but I do have it if anybody is interested. Runs on W95 thru XP. Runtime only. I guess the source code is now god-food.

By david1947 (not verified) on 04 Feb 2007 #permalink

Busy Beaver Numbers! Do Busy Beaver numbers!

By ObsessiveMathsFreak (not verified) on 04 Feb 2007 #permalink

If you want something else that's fairly fun, try downloading JFLAP. It's free for personal or school use (I'm using it in class), and it's a tiny little JAR file. No installation or anything, just a 2mb executable.

There are two great things about it. One, it has a very intuitive visual interface. None of this typing business. ^_^ Just select your mode ("Add state", "Add transition", etc) and start clicking!

Second, it handles so many automata! Just reading down the list, it can handle finite and pushdown automata, mealy, moore, and turing machines (single and multi-tape, for the last one), grammars (directly!), L-systems (whatever they are), regexps, and can apply multiple forms of the pumping lemma to both regular and context-free languages.

You can find it by just searching for JFLAP. You have to fill out a short usage survey (about 10 multiple-choice questions) to download the program.

By Xanthir, FCD (not verified) on 05 Feb 2007 #permalink

Holy crap. I just had an insight into why I always found Turing machines so confusing.

I mean, I understood what they were, how they worked, and definitely knew their significance. But I just never got them; that is, how to make them. It seemed too complicated.

I built one in jflap, and it all clicked. It's just an automaton like any other! The problem was that I'd only ever seen Turing machines written out like you did, Mark - as a list of state transitions. That's just hard for me to grasp. On the other hand, I was taught FSMs as graphs first, then as a tuple. It is immensely easier to create and understand an FSM drawn out as a graph with nodes and arrows than it is as a table of transitions.

I was really confused when I fired up the Turing Machine portion of JFLAP, and saw the exact same interface as I used for FSMs. After a second, though, I got it! A Turing Machine is just an FSM that can choose which direction to move and can change the symbols on the tape!

I don't know why this is such a revelation to me, since I've known about TMs since I was 10, but it was. My life is now complete. ^_^

By Xanthir, FCD (not verified) on 05 Feb 2007 #permalink

I'm a little confused when you say:

One really important thing to understand here is that we do not have a program. What we just did was define a Turing machine that does subtraction. The machine does not take any instructions: the states and the transition function are an intrinsic part of the machine. So the only thing this machine can do is to subtract.

Maybe it is a matter of terminology. What is a program? A program that just subtracts still seems like a program. If we designed a Turing machine that, say, took a chess board and returned a move, would you say it isn't a program, it is just a Turing machine that plays chess? You seem to imply that a program takes a set of instructions. Normally we call that an interpreter.

Cotton:

A program is a piece of data containing instructions for a machine to execute.

The subtraction machine, shown above, does not take any instructions. It can never do anything except subtraction. It's not a machine with a subtraction program; it's a machine
that can only do subtraction.

The easiest way to really grasp that distinction is to think of it as a real physical machine. The tape would be a series of blocks with little dials on top, which could be moved to show "1", "-", "=", or " ". The head would be a machine that could move back and forth over the tape. On the head would be a state wheel, which would have four settings: "scanright", "eraseone", "subone", and "skip". When you turned the machine on, it would start moving back and forth over the cells, changing their settings, and moveing its
own state wheel. This machine doesn't have a subtraction
program - it's a subtraction machine, and because it doesn't read a program at all, it can never do anything but subtraction. There's no way to tell it to do anything different: the way that it does subtraction is physically part of the mechanism of the machine. It's like a piece of one of those old mechanical calculators that accountants used to use: push the "minus" button, and some set of cogs and wheels inside the machine spins and does a subtraction. But you can never change what that button does - because
the machine doesn't have the capacity to change.

A programmable machine can take an input telling it what to do. It doesn't have a single fixed function like the subtraction machine - it can be given different sets of instructions to make it do different things. It's like the laptop I'm using. I've got a calculator program that acts a lot like an old fashioned calculator, with a "tape" showing all of the calculations I've done. But it's just a program that I found and ran on my computer. I can change it to make it different, or I can run an entirely different program. The machine reads information from memory, interprets that information as instructions, and does the computation described by those instructions. But it's a general machine that can be given any set of instructions.

Does that help?

think of a real machine that has a wheel which can be in 4 positions, and which moves back and forth over a