Editing Turing machine (section)

=== Implementation ===

==== Representations of main concepts ====

===== Language =====
<haskell>
 module Language where

 import Util (Maybe2 (Nothing2, Just2))

 type Turing becoming letter = UnsafeTuring (Maybe becoming) (Maybe letter)
 type UnsafeTuring state symbol = state -> symbol -> Maybe2 (Action symbol) state
 data Action symbol = Write symbol | Move Bool
</haskell>

====== Observable non-emptiness: special state, special symbol ======
Most conceptual frameworks of Turing machine concept allow us a big liberty at choosing the set of states and symbols -- but empty set is not allowed. Of course Haskell types are never empty, but non-emptiness provided by <hask>undefined</hask> is not enough. We need discernible, observable non-emptiness. 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 <hask>Turing</hask> versus <hask>UnsafeTuring</hask> distinction with <hask>Maybe</hask> solves the problem of special state and symbol. Special symbol is called <span style="color:blue"><code>blank</code></span> and special state is called <span style="color:#0b0"><code>starting</code></span>. The presence of special symbol, special state is reflected directly in the representation of language concepts -- and both are represented by <hask>Nothing</hask>.

This way allows us a big liberty at choosing 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, enumerations, characters, booleans...
====== 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 <hask>Maybe2</hask> (Hugs has this data type in a library module) is a conceptually esthetic solution.

===== Tape =====
At first I wrote a [[Circular programming|circular program]] to make double linked list to implement a Bi-directionally infinite tape. It is superfluous, there is a more simple solution:

<haskell>
 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
</haskell>
...
===== Utility module =====
<haskell>
 module Util where

 data Maybe2 a b = Nothing2 | Just2 a b
 data Stream a = Cons a (Stream a)
</haskell>