Personal tools

Turing machine

From HaskellWiki

Revision as of 23:00, 22 April 2006 by EndreyMark (Talk | contribs)

Jump to: navigation, search

Contents


1 Introduction

Wikipedia article

2 Planning a programming language: incarnating most concepts

2.1 Syntax

I was dreaming of a syntax reflecting the conceptual structure of the main concepts -- maybe reflecting even the logic of the Haskell implementation! In generally, I do not like special names (like start is for starting state, everything else...) -- I like the concept of tags much better.

2.1.1 Verbose syntax

2.1.1.1 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

2.1.2 Concise syntax

2.1.2.1 Example
0 : _ : -> / 0
0 : '1 : !'1 / @processing
@processing : _ : !'1 / @extended
@processing : '1 : -> / @processing
@extended : _ : .
@extended : '1 : .
2.1.2.2 Motivation of signs
  • 0 signing starting state comes from David S. Woodruff's Turing machine interpreter TM
  • Exclamation mark signing the concept of writing comes from the Z model-based formal specification language, where exclamation mark is used to mark output (variables)
  • Repeated colons signing compound cases come from the concept of currying.
  • At-character signing state comes from its literal meaning in natural languages (in everyday English language, as a preposition for expressing being at places times or states) -- also reflected in its use in e-mail addresses
  • Apostrophe signing a (non-blank) letter comes from using apostrophes in programming languages for character literals and from using apostrophes (or upper corners) for quotations in mathematical logic
  • Slash-character signing the concept of compound action (allowing the possibility of halting instead) comes from the theory of automata
  • Dot signing termination is hard to explain. In Prolog, dot is a terminating symbol, but in another sense: it terminates syntactical units (rules and facts), not processes!

2.2 Implementation

2.2.1 Representations of main concepts

2.2.1.1 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
2.2.1.1.1 Defaults or non-emptyness restriction
The trick of
Turing0
and
Maybe
solves the problem of default state and symbol. I mean Turing machines allow us a big liberty at chosing the set of states and symbols -- but empty set is not allowed. This restriction is reflected directly in the representation of language concepts. Default symbol is called blank and default state is called start and both are represented by
Nothing
.
2.2.1.1.2 Halting

Another -- maybe analogous -- problem is the representation of halting.

There may be alternative solutions: introduction of concepts like halting state or halting action, etc... I felt that
Maybe2
(Hugs has this data type in a library module) is a conceptually esthetic solution.
2.2.1.2 Tape

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))
 
 data Tape a = Tp {left, right :: Stream a, cell :: a}
 move :: Bool -> Tape a -> Tape a
 put :: a -> Tape a -> Tape a
 get :: Tape a -> a

...

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

2.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.