A Turing machine is an abstract "machine" that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model that defines such a device. Despite the model's simplicity, given any computer algorithm, a Turing machine can be constructed that is capable of simulating that algorithm's logic. (cited from wiki)
go get github.com/kkdai/tm
Following is sample code to implement a TM to rewrite all tape 0 to 1 as follow:
package main
import (
"fmt"
. "github.com/kkdai/tm"
)
func main() {
nTM := NewTM()
//Input State and declare if it is final state
nTM.InputState("0", false)
nTM.InputState("1", true)
//Input config
// InputConfig parameter as follow:
// - SourceState,
// - Input
// - Modified Value
// - DestinationState
// - Tape Head Move Direction
nTM.InputConfig("0", "1", "1", "1", MoveRight)
nTM.InputConfig("0", "0", "1", "0", MoveLeft)
nTM.InputConfig("1", "0", "1", "0", MoveLeft)
nTM.InputConfig("1", "1", "1", "1", MoveRight)
//Input tape data
nTM.InputTape("0", "0", "1", "1", "0", "0", "0")
//Run TM to the finish (if exist)
nTM.Run()
fmt.Println("New Tape:=", nTM.ExportTape())
}- Coursera: Automata
- https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/four.html
- Wiki: 圖靈機
- https://en.wikipedia.org/wiki/Turing_machine_examples
It is one of my project 52.
This package is licensed under MIT license. See LICENSE for details.