-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A simple simulator for Turing machines
--   
--   This package provides some basic functions and types to simulate a
--   Turing machine.
@package turing
@version 0.1.1


-- | This module defines everything required to simulate a simple
--   deterministic Turing machine. There are several equivalent but
--   slightly different definitions of Turing machines in use - ours has
--   the machine write <i>and</i> move in each step of execution. In
--   addition, we allow a special movement <a>DontMove</a> that results in
--   just a write operation.
--   
--   You just define a transition function using suitable state and input
--   types and run it:
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   let
--       f (q, Just 0) = Just (q, Just 0, MoveRight)
--       f ("even", Just 1) = Just ("odd", Just 0, MoveRight)
--       f ("odd", Just 1) = Just ("even", Just 0, MoveRight)
--       f _ = Nothing
--       t = mkTuringMachine f "even" ["even"] -- a machine that decides parity
--   in run t [0, 0, 1, 1, 1]
--   :}
--   Reject
--   </pre>
module Data.Turing

-- | Abstract type representing a Turing machine. It is parameterized over
--   the alphabet and state types. A full definition contains the initial
--   state, a list of accepting states and the transition function.
--   Construct through <a>mkTuringMachine</a>.
data TuringMachine s q

-- | Construct a Turing machine from the transition function, its initial
--   state and a list of accepting states.
mkTuringMachine :: TransitionFunction s q -> q -> [q] -> TuringMachine s q

-- | A Turing machine has three options of moving its read head: left,
--   right, or no move at all.
data Movement
MoveLeft :: Movement
MoveRight :: Movement
DontMove :: Movement

-- | The transition function maps the current state and tape contents to a
--   triple describing the new state, the value to write to the tape, and a
--   head movement. If the function is <a>Nothing</a> for the current state
--   and tape contents, the machine halts.
type TransitionFunction s q = (q, Maybe s) -> Maybe (q, Maybe s, Movement)

-- | A machine can either accept or reject the input (for now).
data MachineResult
Accept :: MachineResult
Reject :: MachineResult

-- | Run a machine indefinitely on the given input. If it halts, it either
--   accepts or rejects the input.
run :: Eq q => TuringMachine s q -> [s] -> MachineResult

-- | Run a machine for the given number of steps. If this is enough for it
--   to halt, the result is the same as for <a>run</a>, wrapped in
--   <a>Just</a>; otherwise it is <a>Nothing</a>.
runFor :: (Integral i, Eq q) => i -> TuringMachine s q -> [s] -> Maybe MachineResult
instance GHC.Show.Show Data.Turing.MachineResult
instance GHC.Classes.Eq Data.Turing.MachineResult
instance GHC.Show.Show Data.Turing.Movement
instance GHC.Classes.Eq Data.Turing.Movement