My favorites | Sign in
Project Home Downloads Issues Source
Project Information
Members
Featured
Downloads

This is a multi-tape Turing Machine project written in Haskell. You are welcome to contribute.

Usage

You can create a more robust executable or modify TM.hs to suit your needs. I provided a simple main script that requires four arguments:

  1. Path to file which contains the tapes;
  2. Path to file which contains the transitions;
  3. Number of the initial state;
  4. true or false.

1. A tape is a string. Separate them with a newline. The blank symbol is #.

2. The transitions are more complicated, so I wrote an example:

    ((0,['0','#']), (1,[('0', R),('b',R)]))
    ((1,['0','#']), (1,[('0', R),('b',R)]))
    ((1,['1','#']), (2,[('1', H),('b',H)]))
    ...
Each line is the type: ((State, [Symbol]), (State, [(Symbol, Action)])).
For the first line, you should read: In state 0, if I have '0' in the first tape and '#' in the second one, go to state 1; then write '0' in the first tape and move the head to the right, and write 'b' in the second tape and move the head to the right. You can't have two equal 'first elements' of the tuple. This isn't a non-deterministic turing machine.
The types:
  • State is an integer.
  • Symbol is a character.
  • Action must be L, R or H. L - left, R - right and H - Halt.
The machine accepts a language when it finds a halting action (H). If you have multiple tapes, the H must be in one of them.

3. An integer that represents the initial state. It's almost always 0.

4. If you need a verbose run, use true. It prints the tapes, head position and state of the machine for every step.

Example:
    -- step: 0 -- state: 0
    0000011111
    ^

    #
    ^

    -- step: 1 -- state: 1
    0000011111
     ^

    b#
     ^

Installation

If you have cabal-install:

  1. tar zxf hstm-0.1.0.tar.gz
  2. cd hstm-0.1.0
  3. cabal install

Or else:

  1. tar zxf hstm-0.1.0.tar.gz
  2. cd hstm-0.1.0
  3. runhaskell Setup configure
  4. runhaskell Setup build
  5. runhaskell Setup install
Powered by Google Project Hosting