Turing machine

From HaskellWiki

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

2.2.1.1.2 Halting

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

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.

Category: Theoretical foundations