tm

README

Simple Turing Machine implement in Golang

What is this Turing Machine

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. (Wiki Quote)

Install

go get github.com/pchchv/tm

Usage

package main

import (
    "fmt"
    . "github.com/pchchv/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())
}

Documentation

Index

• Constants
• type ConfigIn
• type ConfigOut
• type TM
  • func NewTM() *TM
  • func (t *TM) ExportTape() []string
  • func (t *TM) InputConfig(srcState string, input string, modifiedVal string, dstState string, ...)
  • func (t *TM) InputState(state string, isFinal bool)
  • func (t *TM) InputTape(tracks ...string)
  • func (t *TM) Run() bool
  • func (t *TM) Step() bool
• type Tape
  • func NewTape(Symbols []string) *Tape
  • func (t *Tape) DoOption(modifiedSym string, directToRight bool)
  • func (t *Tape) EndInput() bool
  • func (t *Tape) ReadSymbol() string

Constants

const (
	MoveLeft  = iota //0
	MoveRight = iota //1
)

Types

type ConfigIn

type ConfigIn struct {
	SrcState string
	Input    string
}

type ConfigOut

type ConfigOut struct {
	DstState    string
	ModifiedVal string
	TapeMove    int
}

type TM

type TM struct {
	Input        *Tape
	States       map[string]bool
	FinalStates  map[string]bool
	Inputs       map[string]bool
	Configs      map[ConfigIn]ConfigOut
	CurrentState string
}

func NewTM

func NewTM() *TM

func (*TM) ExportTape

func (t *TM) ExportTape() []string

func (*TM) InputConfig

func (t *TM) InputConfig(srcState string, input string, modifiedVal string, dstState string, tapeMove int)

Input config InputConfig parameter as follow: - SourceState, - Input - Modified Value - DestinationState - Tape Head Move Direction

func (*TM) InputState

func (t *TM) InputState(state string, isFinal bool)

Input State and declare if it is final state

func (*TM) InputTape

func (t *TM) InputTape(tracks ...string)

Input turing machine tape data

func (*TM) Run

func (t *TM) Run() bool

Run turing machine all tape data to the end

func (*TM) Step

func (t *TM) Step() bool

Step will read a input and run single step, return if it is accept

type Tape

type Tape struct {
	Symbol []string
	Head   int
}

func NewTape

func NewTape(Symbols []string) *Tape

func (*Tape) DoOption

func (t *Tape) DoOption(modifiedSym string, directToRight bool)

Run tape head move and modify value

func (*Tape) EndInput

func (t *Tape) EndInput() bool

Return if the tape is run to the end

func (*Tape) ReadSymbol

func (t *Tape) ReadSymbol() string

Read one symbol from tape