From 3c96313867236ba84ab2c7e1911cf99a2361590e Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Wed, 2 Sep 2015 20:16:20 +0200 Subject: Initial commit --- .gitignore | 3 ++ IterableClass.dcl | 10 +++++ IterableClass.icl | 18 ++++++++ LICENSE | 22 +++++++++ Readme.md | 130 +++++++++++++++++++++++++++++++++++++++++++++++++++++ TuringMachines.dcl | 40 +++++++++++++++++ TuringMachines.icl | 81 +++++++++++++++++++++++++++++++++ 7 files changed, 304 insertions(+) create mode 100644 .gitignore create mode 100644 IterableClass.dcl create mode 100644 IterableClass.icl create mode 100644 LICENSE create mode 100644 Readme.md create mode 100644 TuringMachines.dcl create mode 100644 TuringMachines.icl diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..2394f50 --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +*.swp +Clean System Files/ + diff --git a/IterableClass.dcl b/IterableClass.dcl new file mode 100644 index 0000000..729cd68 --- /dev/null +++ b/IterableClass.dcl @@ -0,0 +1,10 @@ +definition module IterableClass + +class step a :: a -> a +class rewind a :: a -> a + +stepn :: Int a -> a | step a +rewindn :: Int a -> a | rewind a + +stepOrRewindn :: Int a -> a | step, rewind a + diff --git a/IterableClass.icl b/IterableClass.icl new file mode 100644 index 0000000..97340ba --- /dev/null +++ b/IterableClass.icl @@ -0,0 +1,18 @@ +implementation module IterableClass + +import StdEnv + +stepn :: Int a -> a | step a +stepn 0 a = a +stepn n a = stepn (n-1) (step a) + +rewindn :: Int a -> a | rewind a +rewindn 0 a = a +rewindn n a = rewindn (n-1) (rewind a) + +stepOrRewindn :: Int a -> a | step, rewind a +stepOrRewindn 0 a = a +stepOrRewindn n a +| n < 0 = rewindn (0-n) a +| n > 0 = stepn n a + diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..fd8fd93 --- /dev/null +++ b/LICENSE @@ -0,0 +1,22 @@ +The MIT License (MIT) + +Copyright (c) 2015 Camil Staps + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. + diff --git a/Readme.md b/Readme.md new file mode 100644 index 0000000..0eca67d --- /dev/null +++ b/Readme.md @@ -0,0 +1,130 @@ +# CleanTuringMachines + +Turing machines implementation in [Clean](http://wiki.clean.cs.ru.nl/Clean). Features include: + + * Straightforward types for turing machines and their states + * Running and stepping a turing machine in execution + * Simple `toString` instances for easy display of the types + +Read further for examples. + +### License + +This program and the example are distributed under the MIT license. For more details, see the LICENSE file. + +## Types and classes + +### IterableClass + +Provides two general classes: + + class step a :: a -> a + class rewind a :: a -> a + +Both are meant to be instantiated by types that can be 'stepped'. For example, the TuringMachineState instantiates the `step` class to be able to compute the next state for a current state. The `rewind` class is currently unused, but it only made sense to include it and make this a separate module. It allows a type to step backwards. Note, that for a Turing machine it is impossible to instantiate this class, because the transition function need not have an inverse. + +There are three derivative functions: + + stepn :: Int a -> a | step a + rewindn :: Int a -> a | rewind a + stepOrRewindn :: Int a -> a | step, rewind a + +The first and second simply iterate `step` and `rewind`. Negative values for the first argument will never terminate. The latter function will evaluate to either `rewindn` or `stepn`, depending on the sign of the first argument. + +### TuringMachines + +The tape is a simple list of Maybes of an arbitrary type. `Nothing` encodes a blank, `Just a` encodes the value `a`. + + :: Tape a :== [Maybe a] + +The transition function (shown subsequently) results in a `TuringMachineMove`. This can either be a `Step`, or a `Halt`. Normally, the transition function is a partial function. Here, it is expected to be a nonpartial function to avoid runtime errors. What would normally be undefined is now `Halt`: it tells the turing machine to terminate. + + :: TuringMachineMove a = Step Int (Maybe a) Direction | Halt + :: Direction = Left | Right + +Here, `a` is the alphabet once again. A step changes state to the first argument, writes the second argument on the tape, and moves in the specified direction. + +A Turing machine state consists of a Turing machine definition, but also includes the current state, the position of the tape head, the tape itself, and whether the machine is running or not: + + :: TuringMachineState a = { machine :: TuringMachine a, + state :: Int, + tapeHead :: Int, + tape :: Tape a, + running :: TuringMachineTermination } + :: TuringMachineTermination = Running | Normal | Abnormal + +Here, `a` is the tape alphabet and `i` is the input alphabet. We will come back to that. + +As you can see, we specify states simply with integers. Mathematically, a Turing machine is a quintuple (Q,Σ,Γ,δ,q0) where Q is the set of states and q0 the initial state (Sudkamp, Languages and Machines, 1997). Here, we take the integers as Q and 0 as q0. `a` relates to Γ, `i` relates to Σ and we will get back to δ. + +The machine may be `Running`, or it may be terminated. In the latter case we distinguish between `Normal` termination (after a `Halt` move) and `Abnormal` termination (if the tape head position goes negative). + +Finaly, the definition of the Turing machine itself: + + :: TuringMachine a = { alphabet :: [a], + inputs :: [a], + transition :: Int (Maybe a) -> TuringMachineMove a } + +Again, we see the alphabet `a`. The transition function (δ) is a function from `Int` (the current state) and `Maybe a` (the character read by the tape head to a `TuringMachineMove a`. The `inputs` key specifies the input alphabet, typically a subset of the alphabet itself. It defines the characters allowed in the input. + +### Examples + +The following is a simple machine to replace `a` with `b` and vice versa. It is an example from Sudkamp, Languages and Machines, 1997, where it is represented as a state machine: + +![A graphical representation of the replace machine](http://i.stack.imgur.com/gOtXY.png) + + replace :: TuringMachine Char Char + replace = { alphabet = ['a','b'], + inputs = ['a','b'], + transition = f } + where + f :: Int (Maybe Char) -> TuringMachineMove Char + f 0 Nothing = Step 1 Nothing Right + f 1 Nothing = Step 2 Nothing Left + f 1 (Just 'a') = Step 1 (Just 'b') Right + f 1 (Just 'b') = Step 1 (Just 'a') Right + f 2 (Just 'a') = Step 2 (Just 'a') Left + f 2 (Just 'b') = Step 2 (Just 'b') Left + f _ _ = Halt + +Note the final catch-all alternative of the transition function `f`, which is used to make sure `f` is nonpartial. + +## Firing up the machine + +Getting a `TuringMachineState` from a `TuringMachine` is fairly straightforward. All you need is a `Tape`. For the example above, we may write: + + state :: TuringMachineState Char Char + state = initTuringMachine replace tape + where + tape = [Just c \\ c <- fromString "aabbaa"] + +The set builder for the tape is just ease of notation, we may as well have written `['a','a','b','b','a','b']`. A first and final blank is added to the tape by `initTuringMachine`. + +`initTuringMachine` checks that there are no characters on the tape that are not in the input alphabet, and aborts if there are. + +## Stepping and running + +From this state we can either `step`... + + state1 = step state + state5 = stepn 5 state + +... or run until termination: + + statef = run state + +## Showing results + +The `TuringMachineState` instantiates `toString`. The result of `toString statef` would be: + + Normally terminated turing machine in state 2, tape head at 0. + Tape: BbbaabbB + +As you can see, the machine definition is in no way represented by this function. + +Blanks (`Nothing` on the tape) are represented with 'B'. + +## Future ideas + + * It would be really cool to have some kind of graphical frontend and a possibility to step through the machine with some input + diff --git a/TuringMachines.dcl b/TuringMachines.dcl new file mode 100644 index 0000000..d97600a --- /dev/null +++ b/TuringMachines.dcl @@ -0,0 +1,40 @@ +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 + diff --git a/TuringMachines.icl b/TuringMachines.icl new file mode 100644 index 0000000..b37233c --- /dev/null +++ b/TuringMachines.icl @@ -0,0 +1,81 @@ +implementation module TuringMachines + +import StdEnv +import StdMaybe +import IterableClass + +instance toString Direction +where + toString Left = "Left" + toString Right = "Right" + +instance toString (TuringMachineMove a) | toString a +where + toString Halt = "Halt" + toString (Step i Nothing dir) = "Step in q" +++ toString i +++ "; write B; move " +++ toString dir + toString (Step i (Just a) dir) = "Step in q" +++ toString i +++ "; write " +++ toString a +++ "; move " +++ toString dir + +instance toString TuringMachineTermination +where + toString Running = "Running" + toString Normal = "Normally terminated" + toString Abnormal = "Abnormally terminated" + +instance toString (Tape a) | toString a +where + toString [] = "" + toString [Nothing:tape] = "B" +++ toString tape + toString [Just a:tape] = toString a +++ toString tape + +instance toString (TuringMachineState a) | toString a +where + toString st=:{state,tapeHead,tape,running} + = toString running +++ " turing machine in state " +++ toString state +++ ", tape head at " +++ toString tapeHead +++ ".\nTape: " +++ toString tape + +instance == Direction +where + (==) Left Left = True + (==) Right Right = True + (==) _ _ = False + +instance == (TuringMachineMove a) | == a +where + (==) Halt Halt = True + (==) (Step i a dir) (Step i2 a2 dir2) = i == i2 && a == a2 && dir == dir2 + (==) _ _ = False + +instance == TuringMachineTermination +where + (==) Running Running = True + (==) Normal Normal = True + (==) Abnormal Abnormal = True + (==) _ _ = False + +instance step (TuringMachineState a) | == a +where + step st=:{machine,state,tapeHead,tape,running} + | running <> Running = st + # move = machine.transition state (tape!!tapeHead) + | move == Halt = {st & running = Normal} + # (Step state write dir) = move + # tape = updateAt tapeHead write tape + # tapeHead = if (dir == Left) (-) (+) tapeHead 1 + | tapeHead < 0 = {st & running = Abnormal} + = {st & state=state, tapeHead=tapeHead, tape=tape} + + +initTuringMachine :: (TuringMachine a) (Tape a) -> TuringMachineState a | Eq a +initTuringMachine def tape +| invalid tape = abort "Invalid symbols on input" +| otherwise = {machine=def, state=0, tapeHead=0, tape=[Nothing:tape]++[Nothing], running=Running} +where + invalid [] = False + invalid [Nothing:tape] = invalid tape + invalid [Just c:tape] = not (isMember c def.inputs) || invalid tape + +run :: (TuringMachineState a) -> TuringMachineState a | == a +run m +# m = step m +| m.running == Running = run m +| otherwise = m + -- cgit v1.2.3