# go-tm

command module
Version: v0.0.0-...-b57eb89 Latest Latest

Go to latest
Published: Jan 22, 2019 License: MIT

### go-tm - Make a Turing Machine easily

go-tm is a library to implement both deterministic and non deterministic Turing machines easily. A related blog-post is here.

The Turing machine is a mathematical model of computation that defines an abstract machine which manipulates symbols on a strip of tape according to a list of rules. Formally, it is defined as an infinite tape of 0 with a pointer (identified by square bracket) to one specific zero,

``````... 0 0 0 0 0 [0] 0 0 0 0 0  ...
``````

a set of states identified by letters (or numbers),

``````{A, B, C}
``````

and a list of transactions, like the one

``````(A, 0, B, 1, R);
``````

where a single transaction like (A, 0, B, 1, R) has to been read as

Given a Turing machine in state A with the pointer over a 0, write 1, evolve to state B and move the pointer by one position in right direction over the tape.

The pointer can only be moved by one position at time, left, right, or stay where it is.

#### Installation

Just get the library by:

``````go get github.com/made2591/go-tm
``````

#### Usage

To create a new `Symbol`, use the `NewSymbol()` factory method

``````// will create a new Symbol with value 0
sym := NewSymbol(uint8(0))
``````

To create a new `State`, use the `NewState()` or `NewStateInitial()` or `NewStateFinal()` factory methods

``````// will create a three new State, one with Identifier "A", one INITIAL and one FINAL
sts := NewState("A")
ins := NewStateInitial()
fis := NewStateFinal()
``````

To create a new `Transaction`, use the `NewTransaction()` factory method

``````// will move from INITIAL State, reading 0, writing 0, to state "B"
tr0 := transaction.NewTransaction(state.NewInitialState(), symbol.NewSymbol(uint8(0)), state.NewState("B"), symbol.NewSymbol(uint8(1)), "N")
``````

To init a new `TuringMachine` to play the BB-2 Game

``````// create states set
iss := set.NewSet()
fss := set.NewSet()
trs := set.NewSet()

// create transaction
tr0 := transaction.NewTransaction(state.NewInitialState(), symbol.NewSymbol(uint8(0)), state.NewState("A"), symbol.NewSymbol(uint8(0)), "N")
tr1 := transaction.NewTransaction(state.NewState("A"), symbol.NewSymbol(uint8(0)), state.NewState("B"), symbol.NewSymbol(uint8(1)), "R")
tr2 := transaction.NewTransaction(state.NewState("A"), symbol.NewSymbol(uint8(1)), state.NewState("B"), symbol.NewSymbol(uint8(1)), "L")
tr3 := transaction.NewTransaction(state.NewState("B"), symbol.NewSymbol(uint8(0)), state.NewState("A"), symbol.NewSymbol(uint8(1)), "L")
tr4 := transaction.NewTransaction(state.NewState("B"), symbol.NewSymbol(uint8(1)), state.NewFinalState(), symbol.NewSymbol(uint8(1)), "R")

// init the Turing Machine
tm := turingMachine.NewTuringMachine(iss, fss, trs, state.NewState(state.INITIAL), symbol.NewSymbol(uint8(0)))

// run the Turing Machine
tm.Run()

``````

or, from inside the `root` folder of the project

``````go run main.go
``````

#### Support

Please open an issue for support.

#### Contributing

Please contribute using Github Flow. Create a branch, add commits, and open a pull request.

## Documentation ¶

There is no documentation for this package.

Path Synopsis
turing