Personal tools

Turing machine

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (Re-coloring syntax highlight for - Verbose syntax: of Turing machine description language)
(Re-coloring: states are green and actions are red, these complementary colors yield a nice view)

Revision as of 17:53, 30 April 2006


1 Introduction

Wikipedia article

2 Variants

There are several variants of defining the concept of a Turing machine. These varants can be classified across several aspects. I shall classify possible variants in terms of two questions:

  • how the machine behaves at transitions
  • how the the running of the machine terminates

2.1 A classifying aspect

2.1.1 Transition


product-like transition
sum-like transition
means that the head moves or writes at each transition (never both). J. Donald Monk's Mathematical Logic describes this approach. I like this approach better, because it looks more ecomical conceptually (we do not have to undo any superfluous final movings, nor do we need to introduce idle moves) and because it looks nicer for me even conceptually.

2.1.2 Halting


2.2 A construct called

 data Maybe2 a b = Nothing2 | Just2 a b

2.3 Moves

There are variants of the Turing machine concept also accross other problems, e.g. how the head and the tape moves related from each other: which is regarded as moving, which is immobile.

Using the facts that

  • the head is
    • finite (even if the states are included)
    • and even limited, even constant (fixing a concrete Turing machine): it does not grow during a run


3 Planning a programming language: incarnating most concepts

3.1 Syntax


3.1.1 Verbose syntax Example
starting : blank : move right with starting;
starting : letter 1 : write letter 1 with becoming processing;
becoming processing : blank  : write letter 1 with becoming extended;
becoming processing : letter 1 : move right with becoming processing;
becoming extended : blank : stop;
becoming extended : letter 1 : stop;

3.1.2 Concise syntax Example
0 : _ : -> / 0
0 : '1 : !'1 / @processing
@processing : _ : !'1 / @extended
@processing : '1 : -> / @processing
@extended : _ : .
@extended : '1 : . Motivation of signs

3.2 Implementation

3.2.1 Representations of main concepts Language
 module Language where
 import Util (Maybe2 (Nothing2, Just2))
 type Turing state symbol = Turing0 (Maybe state) (Maybe symbol)
 type Turing0 state symbol = state -> symbol -> Maybe2 (Action symbol) state
 data Action symbol = Write symbol | Move Bool Discernable non-emptyness: special state, special symbol
Most conceptual frameworks of Turing machine concept allow us a big liberty at chosing the set of states and symbols -- but empty set is not allowed. Of course Haskell types are never empty, but non-emptyness provided by
is not enough. We need discernable non-emptyness. This restriction is reflected directly in the representation of language concepts: we require the presence of a special symbol and a special state. The trick of
solves the problem of default state and symbol. Default symbol is called blank and default state is called start. The presence of special symbol, special state is reflected directly in the representation of language concepts -- and both are represented by

This way allows us a big liberty at chosing the set of states and symbols -- we do not have to restrict the user's freedom to use any types for both symbols and states. Strings, integers, enumarations, characters, booleans... Halting



At first I wrote a circular program to make double linked list to implement a bidirectionally infinite tape. It is superfluous, there is a more simple solution:

 module Tape where
 import Util (Stream (Cons))
 move :: Bool -> Tape a -> Tape a
 put :: a -> Tape a -> Tape a
 get :: Tape a -> a

... Utility module
 module Util where
 data Maybe2 a b = Nothing2 | Just2 a b
 data Stream a = Cons a (Stream a)

3.3 Extending language

A pattern language, or some other extending possibilities, to avoid redundances. Maybe a macro language as at David S. Woodruff's Turing machine interpreter TM. Other syntactic sugar.