{"id":299,"date":"2007-02-03T18:38:02","date_gmt":"2007-02-03T18:38:02","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/02\/03\/basics-the-turing-machine-with-an-interpreter\/"},"modified":"2007-02-03T18:38:02","modified_gmt":"2007-02-03T18:38:02","slug":"basics-the-turing-machine-with-an-interpreter","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/02\/03\/basics-the-turing-machine-with-an-interpreter\/","title":{"rendered":"Basics: The Turing Machine (with an interpreter!)"},"content":{"rendered":"<p> As long as I&#8217;m doing all of these basics posts, I thought it would be worth<br \/>\nexplaining just what a Turing machine is. I frequently talk about things<br \/>\nbeing 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&#8217;m also going to give you a nifty little piece of Haskell source code that&#8217;s a very basic Turing machine interpreter. (It&#8217;s for a future entry in the Haskell posts, and it&#8217;s not entirely finished, but it <em>does<\/em> work!)<\/p>\n<p> The Turing machine is a very simple kind of theoretical computing device. In<br \/>\nfact, it&#8217;s almost downright trivial. But according to everything that we know and understand about computation, this trivial device is capable of <em>any<\/em> computation that can be performed by any other computing device.<\/p>\n<p> The basic idea of the Turing machine is very simple. It&#8217;s a machine that runs on<br \/>\ntop of a <em>tape<\/em>, 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<br \/>\nmachine looks at the symbol on the cell under the tape head, and based on what<br \/>\nit 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. <\/p>\n<p> That&#8217;s really it. People who like to make computing sound impressive often have<br \/>\nvery complicated explanations of it &#8211; but really, that&#8217;s all there is to it. The point of it was to be simple &#8211; and simple it certainly is. And yet, it can do<br \/>\n<em>anything<\/em> that&#8217;s computable.<\/p>\n<p><!--more--><\/p>\n<p>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, s<sub>0<\/sub>, A, T), where:<\/p>\n<ul>\n<li> <b>S<\/b> is a finite list of possible <em>states<\/em> that the machine can be in. The state is the information that the machine can store in the head to make decisions. It&#8217;s a very limited amount of information; you can think of it as either<br \/>\na specific list of states, or a small set of small numbers. For most Turing machines,<br \/>\nwe&#8217;ll use it as a specific list of states. (You&#8217;ll see what I mean in a minute.)<\/li>\n<li> s<sub>0<\/sub> &isin; <b>S<\/b> is the <em>initial<\/em> state &#8211; the state that the<br \/>\nmachine will be in when it starts a computation.<\/li>\n<li> <b>A<\/b> is the machine&#8217;s alphabet, which is the set of symbols<br \/>\nwhich can appear on the machine&#8217;s tape.<\/li>\n<li> <b>T<\/b> is the machines <em>transition function<\/em>. This is the real<br \/>\nheart of the machine, where the computation is defined. It&#8217;s a function from<br \/>\nthe machine state and the alphabet character on the current tape cell to the<br \/>\naction that the machine should take. The action is a triple consisting of<br \/>\na new value for the machine&#8217;s state, a character to write onto the current<br \/>\ntape cell, and a direction to move the tape head &#8211; either left or right.<\/li>\n<\/ul>\n<p> So, for example, let&#8217;s look at a simple machine. This is one of the classic<br \/>\nexamples: a Turing machine that does subtraction using <em>unary<\/em> numbers. A unary<br \/>\nnumber &#8220;N&#8221; is written as a series of N 1s. For the program, we&#8217;ll give the machine an<br \/>\ninput in the format &#8220;N-M=&#8221; written onto the tape; after running the machine, the tape<br \/>\nwill contain the value of M subtracted from N. So, for example, we could use &#8220;1111-11=&#8221;<br \/>\nas an input; the output would be &#8220;11&#8221;.<\/p>\n<p> The alphabet is the characters &#8220;1&#8221;, &#8221; &#8221; (blank space), &#8220;-&#8221; (minus sign), and &#8220;=&#8221; (equal sign). The machine has four states: {&#8220;scanright&#8221;, &#8220;eraseone&#8221;, &#8220;subone&#8221;, &#8220;skip&#8221;}. It starts in the state &#8220;scanright&#8221;. It&#8217;s transition function is given by the following table:<\/p>\n<table border=\"2\">\n<tr>\n<th>FromState<\/th>\n<th>Symbol<\/th>\n<th>ToState<\/th>\n<th>WriteChar<\/th>\n<th>Dir<\/th>\n<\/tr>\n<tr>\n<td>scanright<\/td>\n<td>space<\/td>\n<td>scanright<\/td>\n<td>space<\/td>\n<td>right<\/td>\n<\/tr>\n<tr>\n<td>scanright<\/td>\n<td>1<\/td>\n<td>scanright<\/td>\n<td>1<\/td>\n<td>right<\/td>\n<\/tr>\n<tr>\n<td>scanright<\/td>\n<td>minus<\/td>\n<td>scanright<\/td>\n<td>minus<\/td>\n<td>right<\/td>\n<\/tr>\n<tr>\n<td>scanright<\/td>\n<td>equal<\/td>\n<td>eraseone<\/td>\n<td>space<\/td>\n<td>left<\/td>\n<\/tr>\n<tr>\n<td>eraseone<\/td>\n<td>1<\/td>\n<td>subone<\/td>\n<td>equal<\/td>\n<td>left<\/td>\n<\/tr>\n<tr>\n<td>eraseone<\/td>\n<td>minus<\/td>\n<td>HALT<\/td>\n<td>space<\/td>\n<td>n\/a<\/td>\n<\/tr>\n<tr>\n<td>subone<\/td>\n<td>1<\/td>\n<td>subone<\/td>\n<td>1<\/td>\n<td>left<\/td>\n<\/tr>\n<tr>\n<td>subone<\/td>\n<td>minus<\/td>\n<td>skip<\/td>\n<td>minus<\/td>\n<td>left<\/td>\n<\/tr>\n<tr>\n<td>skip<\/td>\n<td>space<\/td>\n<td>skip<\/td>\n<td>space<\/td>\n<td>left<\/td>\n<\/tr>\n<tr>\n<td>skip<\/td>\n<td>1<\/td>\n<td>scanright<\/td>\n<td>space<\/td>\n<td>right<\/td>\n<\/tr>\n<\/table>\n<p> 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 &#8220;-&#8221; before it finds a digit, that means its done, so it stops. Let&#8217;s look at a simple execution trace. In the trace, I&#8217;ll write the<br \/>\nmachine state, followed by a colon, followed by the tape contents surrounded by &#8220;[]&#8221;, with the current tape cell surrounded by &#8220;{}&#8221;.<\/p>\n<pre>\nscanright:  [ {1}1111111-111= ]\"\nscanright:  [ 1{1}111111-111= ]\"\nscanright:  [ 11{1}11111-111= ]\"\nscanright:  [ 111{1}1111-111= ]\"\nscanright:  [ 1111{1}111-111= ]\"\nscanright:  [ 11111{1}11-111= ]\"\nscanright:  [ 111111{1}1-111= ]\"\nscanright:  [ 1111111{1}-111= ]\"\nscanright:  [ 11111111{-}111= ]\"\nscanright:  [ 11111111-{1}11= ]\"\nscanright:  [ 11111111-1{1}1= ]\"\nscanright:  [ 11111111-11{1}= ]\"\nscanright:  [ 11111111-111{=} ]\"\neraseone :  [ 11111111-11{1}  ]\"\nsubone   :  [ 11111111-1{1}=  ]\"\nsubone   :  [ 11111111-{1}1=  ]\"\nsubone   :  [ 11111111{-}11=  ]\"\nskip     :  [ 1111111{1}-11=  ]\"\nscanright:  [ 1111111 {-}11=  ]\"\nscanright:  [ 1111111 -{1}1=  ]\"\nscanright:  [ 1111111 -1{1}=  ]\"\nscanright:  [ 1111111 -11{=}  ]\"\neraseone :  [ 1111111 -1{1}   ]\"\nsubone   :  [ 1111111 -{1}=   ]\"\nsubone   :  [ 1111111 {-}1=   ]\"\nskip     :  [ 1111111{ }-1=   ]\"\nskip     :  [ 111111{1} -1=   ]\"\nscanright:  [ 111111 { }-1=   ]\"\nscanright:  [ 111111  {-}1=   ]\"\nscanright:  [ 111111  -{1}=   ]\"\nscanright:  [ 111111  -1{=}   ]\"\neraseone :  [ 111111  -{1}    ]\"\nsubone   :  [ 111111  {-}=    ]\"\nskip     :  [ 111111 { }-=    ]\"\nskip     :  [ 111111{ } -=    ]\"\nskip     :  [ 11111{1}  -=    ]\"\nscanright:  [ 11111 { } -=    ]\"\nscanright:  [ 11111  { }-=    ]\"\nscanright:  [ 11111   {-}=    ]\"\nscanright:  [ 11111   -{=}    ]\"\neraseone :  [ 11111   {-}     ]\"\nHalt:       [ 11111  { }-     ]\"\n<\/pre>\n<p> See, it works! <\/p>\n<p> One really important thing to understand here is that we <em>do not have a program<\/em>. What we just did was define a Turing machine that does subtraction. The machine <em>does not<\/em> take any instructions: the states and the transition function are an <em>intrinsic<\/em> part of the machine. So the <em>only<\/em> thing this machine can do is to subtract.<\/p>\n<p> The real genius of Turing wasn&#8217;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 <em>a description of a Turing machine<\/em> &#8211; that is a <em>program<\/em> &#8211; followed by an input to the program. This single machine &#8211; the <em>Universal<\/em> Turing machine &#8211; could simulate <em>any<\/em> other Turing machine; one machine which could perform any computation.<\/p>\n<p> Turing machines are a lot of fun to play with. Figuring out how to do things<br \/>\ncan be fascinating. Figuring out how to define a Universal turing machine&#8217;s transition function is an amazing thing to do; it&#8217;s astonishing how simple the universal machine can be!<\/p>\n<p> For your enjoyment, I&#8217;ve implemented a Turing machine programming language. You feed it a Turing machine description, and an input string, and it will give you a<br \/>\ntrace of the machines execution like the one above. Here&#8217;s the specification of the<br \/>\nsubtraction machine written in my little Turing language:<\/p>\n<pre>\nstates { \"scanright\" \"eraseone\" \"subtractOneFromResult\" \"skipblanks\" } initial \"scanright\"\nalphabet { '1' ' ' '=' '-' } blank ' '\ntrans from \"scanright\" to \"scanright\" on (' ') write ' ' move right\ntrans from \"scanright\" to \"scanright\" on ('1') write '1' move right\ntrans from \"scanright\" to \"scanright\" on ('-') write '-' move right\ntrans from \"scanright\" to \"eraseone\" on ('=') write ' ' move left\ntrans from \"eraseone\" to \"subtractOneFromResult\" on ('1') write '=' move left\ntrans from \"eraseone\" to \"Halt\" on ('-') write ' ' move left\ntrans from \"subtractOneFromResult\" to \"subtractOneFromResult\" on ('1') write '1' move left\ntrans from \"subtractOneFromResult\" to \"skipblanks\" on ('-') write '-' move left\ntrans from \"skipblanks\" to \"skipblanks\" on (' ') write ' ' move left\ntrans from \"skipblanks\" to \"scanright\" on ('1') write ' ' move right\n<\/pre>\n<p> I think it&#8217;s pretty clear as a syntax, but it still needs explanation.<\/p>\n<ul>\n<li> The first line declares the possible states of the machine, and what state it starts in. This machine has four possible states &#8211; &#8220;scanright&#8221;, &#8220;eraseone&#8221;, &#8220;subtractOneFromResult&#8221;, and &#8220;skipblanks&#8221;. When the machine starts, it will be in the state &#8220;skipright&#8221;.<\/li>\n<li> 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&#8217;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&#8217;t specified.<\/li>\n<li> After that is a series of transition declarations. Each declaration specifies<br \/>\nwhat the machine will do for a given pair of initial state and tape symbol. So, for example, if the machine is in state &#8220;scanright&#8221;, and the current tape cell contains the equal-to sign, then the machine will change to state &#8220;eraseone&#8221;, write a blank<br \/>\nonto the tape cell (erasing the &#8220;=&#8221; sign), and move the tape cell one position<br \/>\nto the left.<\/li>\n<\/ul>\n<p> Finally, the code. You&#8217;ll need GHCI to run it; at the moment, it won&#8217;t work in<br \/>\nHugs (I don&#8217;t have the parsing library in my version of Hugs), and I haven&#8217;t worked<br \/>\nout the linkage stuff to make it work under the GHC compiled mode.<\/p>\n<pre>\n--\n-- A Simple Turing machine interpreter\n-- Copyright 2007 by Mark C. Chu-Carroll\n--    markcc@gmail.com\n--   http:\/\/scienceblogs.com\/goodmath\n--\n-- You can do anything you want with this code so long as you\n-- leave this copyright notice intact.\n--\nmodule Turing where\nimport Text.ParserCombinators.Parsec\nimport qualified Text.ParserCombinators.Parsec.Token as P\nimport Text.ParserCombinators.Parsec.Language\nimport System.Environment\ndata Motion = MoveLeft  | MoveRight deriving (Show)\ndata Transition = Transition String String [Char] Motion  Char deriving (Show)\n--                           from    to      on    move   write\ndata TuringMachine = Machine [String] String   [Char]    Char    [Transition] deriving (Show)\n--                           states   initial  alphabet  blank   transitions\ndata MachineState = TMState [Char] Char [Char]  String  deriving (Show)\n--                           tape-left curcell  curstate\ngetBlankSym :: TuringMachine -&gt; Char\ngetBlankSym (Machine _ _ _ bl _) = bl\nfindMatchingTransition :: [Transition] -&gt; String -&gt; Char -&gt; Maybe Transition\nfindMatchingTransition [] _ _ =  Nothing\nfindMatchingTransition translist state c =\nlet matches = filter (transitionMatches state c) translist\nin case matches of\n[] -&gt; Nothing\nt:[] -&gt; Just t\n_ -&gt; error \"Ambiguous transition\"\nwhere transitionMatches state c (Transition from to on move write) =\n(from == state) &amp;&amp; (elem c on)\nrunTransition :: TuringMachine -&gt; [Char] -&gt; Char -&gt; [Char] -&gt; String -&gt; Transition -&gt; MachineState\nrunTransition m (l:left) c right state (Transition from tostate on MoveLeft write) =\nTMState left l (write:right) tostate\nrunTransition m left c [] state (Transition from tostate on MoveRight write) =\nTMState (write:left) (getBlankSym m) [] tostate\nrunTransition m left c (r:right) state (Transition from tostate on MoveRight write) =\nTMState (write:left) r right tostate\nstepMachine :: TuringMachine -&gt; MachineState -&gt; MachineState\nstepMachine machine@(Machine _ _ _ _ translist) st@(TMState tapeleft c taperight state) =\nlet trans = findMatchingTransition translist state c\nin case trans of\n(Just t) -&gt; runTransition machine tapeleft c taperight state t\nNothing -&gt; error \"No applicable transition from state\"\ngetMachineStateString (TMState left c right state) =\n(state ++ \":[\" ++ (reverse left) ++ \"{\" ++ [c] ++ \"}\" ++ right ++ \"]\")\nrunTracedMachine :: TuringMachine -&gt; [Char] -&gt; [String]\nrunTracedMachine tm@(Machine states initial alphabet blank transitions) (t:tape) =\nrunTracedMachineSteps tm (TMState [] t tape initial) where\nrunTracedMachineSteps machine state =\nlet newstate@(TMState left c right st) = stepMachine machine state\nin if st == \"Halt\"\nthen [getMachineStateString newstate]\nelse let trace=runTracedMachineSteps machine newstate\nin ((getMachineStateString newstate):trace)\nrunMachine :: TuringMachine -&gt; [Char] -&gt; [Char]\nrunMachine tm@(Machine states initial alphabet blank transitions) (t:tape) =\nrunMachineSteps tm (TMState [] t tape initial) where\nrunMachineSteps machine state =\nlet newstate@(TMState left c right st) = stepMachine machine state\nin if st == \"Halt\"\nthen (concat [(reverse left), [c], right])\nelse runMachineSteps machine newstate\n---------------------------------------------------------------------------\n-- Parsing code - implemented using the Parsec monadic parser library.\n---------------------------------------------------------------------------\n-- Basic setup stuff - use a standard haskell style lexer; set up the reserved words\n-- and symbols in the lexer.\nlexer :: P.TokenParser ()\nlexer = P.makeTokenParser (haskellDef\n{ P.reservedNames = [\"states\",\"alphabet\",\"trans\",\"from\",\"to\",\"on\",\"write\",\"move\",\"left\",\"right\",\"initial\",\"blank\"] })\nreserved = P.reserved lexer\nsymbol = P.symbol lexer\nbraces = P.braces lexer\nparens = P.parens lexer\ncharlit = P.charLiteral lexer\nstrlit = P.stringLiteral lexer\nident = P.identifier lexer\nwhitespace = P.whiteSpace lexer\nstates = reserved \"states\"\nalphabet = reserved \"alphabet\"\ntrans = reserved \"trans\"\nfrom = reserved \"from\"\nto = reserved \"to\"\non = reserved \"on\"\nwrite = reserved \"write\"\nmove = reserved \"move\"\ninitial = reserved \"initial\"\nblank = reserved \"blank\"\nleft = do { reserved \"left\"\n; return MoveLeft\n}\nright = do { reserved \"right\"\n; return MoveRight\n}\n-- statesDecl ::= \"states\" \"{\"  strlit+  \"}\" \"initial\" strlit\nstatesDecl = do { states\n; strlst &lt;- braces (many1 strlit)\n; initial\n; i &lt;- strlit\n; return (i,strlst)\n}\n-- alphaDecl ::= &quot;alphabet&quot; &quot;{&quot; charlit+  &quot;}&quot; &quot;blank&quot; charlit\nalphaDecl = do { alphabet\n; charlst &lt;- braces (many1 charlit)\n; blank\n; bl &lt;- charlit\n; return (bl, charlst)\n}\n-- transDecl ::= &quot;trans&quot; &quot;from&quot; strlit &quot;to&quot; strlit &quot;on&quot; &quot;(&quot; charlit+ &quot;)&quot; &quot;write&quot; charlit &quot;move&quot; (&quot;left&quot; | &quot;right&quot;)\ntransDecl = do { trans\n; from\n; fromState &lt;- strlit\n; to\n; targetState &lt;- strlit\n; on\n; chrs &lt;- parens (many1 charlit)\n; write\n; wrchar &lt;- charlit\n; move\n; dir &lt;- ( left  right)\n; return (Transition fromState targetState chrs dir wrchar)\n}\n-- machine ::= statesDecl alphaDecl transDecl+\nmachine = do { (i,sts) &lt;- statesDecl\n; (bl,alpha) &lt;- alphaDecl\n; trans  Parser a -&gt; String -&gt; IO a\nrun p input\n= case (parse p \"\" input) of\nLeft err -&gt; do{ putStr \"parse error at \"\n; print err\n; error \"Parse error\"\n}\nRight x -&gt; return x\nrunTParser ::  String -&gt; IO TuringMachine\nrunTParser input =\nrun (do { whitespace\n; x  String -&gt; IO ([String])\nrunTracedMachineOnString m str =\ndo\ntm  String -&gt; IO String\nrunMachineOnString m str =\ndo\ntm &lt;- runTParser m\nreturn (runMachine tm str)\nsampleInput = &quot; 11111111-111= &quot;\n------------------------------------------------------------------------\n-- Main program execution scaffolding\n-- main still needs a bit of work so that ghci will link correctly;\n-- runs fine in GHCI, but linkage errors in GHC. For now, just load\n-- this file, and then execute &quot;runFromFile&quot; from the command line.\n------------------------------------------------------------------------\nmain =\ndo\n[file] &lt;- getArgs\nm &lt;- parseFromFile (do { whitespace\n; x  do\nprint \"Enter input for parser:\"\ns &lt;- getLine\nresult  do\nprint (concat [\"Parse error\"])\nrunFromFile :: String -&gt; IO ()\nrunFromFile filename =\ndo\nm &lt;- parseFromFile (do { whitespace\n; x  do\nprint \"Enter input for parser:\"\ns &lt;- getLine\nresult  do\nprint (concat [\"Parse error\"])\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>As long as I&#8217;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 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[74,89,54],"tags":[],"class_list":["post-299","post","type-post","status-publish","format-standard","hentry","category-basics","category-haskell","category-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-4P","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/299","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=299"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/299\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=299"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=299"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=299"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}