definition module TuringMachines

import StdMaybe
import IterableClass
from StdOverloaded import class ==, class toString
from StdClass import class Eq

:: TuringMachine a = { alphabet :: [a],
                       inputs :: [a],
                       transition :: Int (Maybe a) -> TuringMachineMove a }

:: TuringMachineState a = { machine :: TuringMachine a,
                            state :: Int,
                            tapeHead :: Int,
                            tape :: Tape a,
                            running :: TuringMachineTermination }

:: TuringMachineTermination = Running | Normal | Abnormal

:: TuringMachineMove a = Step Int (Maybe a) Direction | Halt

:: Direction = Left | Right

:: Tape a :== [Maybe a]

instance == Direction
instance == (TuringMachineMove a) | == a
instance == TuringMachineTermination

instance toString Direction
instance toString (TuringMachineMove a) | toString a
instance toString TuringMachineTermination
instance toString (Tape a) | toString a
instance toString (TuringMachineState a) | toString a

instance step (TuringMachineState a) | == a

initTuringMachine :: (TuringMachine a) (Tape a) -> TuringMachineState a | Eq a
run :: (TuringMachineState a) -> TuringMachineState a | == a