turing machine simulator

main.go

package main

import "fmt"

import "strings"

const (
	Q0      = "q_0"
	Q1      = "q_1"
	Q2      = "q_2"
	Q3      = "q_3"
	Q4      = "q_4"
	QReject = `q_{\mathrm{reject}}`
	QAccept = `q_{\mathrm{accept}}`
)

const (
	A = "a"
	X = "x"
)

const Empty = `\sqcup`

type Dir string

const (
	Right Dir = "R"
	Left  Dir = "L"
)

type Transition struct {
	headNext, qNext string
	dir             Dir
}

var (
	transitions = map[string]map[string]*Transition{}
)

func register(qPrev, headPrev, qNext, headNext string, dir Dir) {
	if _, ok := transitions[qPrev]; !ok {
		transitions[qPrev] = map[string]*Transition{}
	}

	transitions[qPrev][headPrev] = &Transition{
		qNext:    qNext,
		headNext: headNext,
		dir:      dir,
	}
}

func getTransition(tape []string, idx int, q string) (*Transition, bool) {
	if _, ok := transitions[q]; !ok {
		return nil, false
	}

	v, ok := transitions[q][tape[idx]]

	return v, ok
}

func initTape(arr []string) ([]string, int) {
	ret := make([]string, 10000)

	for i := range ret {
		ret[i] = Empty
	}

	copy(ret[5000:], arr)

	return ret, 5000
}

func getStatus(tape []string, idx int, q string) string {
	tapeIdx := 0
	for i := range tape {
		if tape[i] != Empty {
			break
		}
		tapeIdx = i
	}

	tapeEnd := 0
	for i := len(tape) - 1; i >= 0; i-- {
		if tape[i] != Empty {
			break
		}
		tapeEnd = i
	}

	return fmt.Sprintf("(%s, {%s}, %d)", q, strings.Join(tape[tapeIdx+1:tapeEnd], "}{"), idx-tapeIdx)
}

func main() {
	register(Q0, A, Q1, Empty, Right)
	register(Q0, Empty, QReject, Empty, Right)
	register(Q0, X, QReject, X, Right)

	register(Q1, X, Q1, X, Right)
	register(Q1, Empty, QAccept, Empty, Right)
	register(Q1, A, Q2, X, Right)

	register(Q2, X, Q2, X, Right)
	register(Q2, A, Q3, A, Right)
	register(Q2, Empty, Q4, Empty, Left)

	register(Q3, A, Q2, X, Right)
	register(Q3, X, Q3, X, Right)
	register(Q3, Empty, QReject, Empty, Right)

	register(Q4, A, Q4, A, Left)
	register(Q4, X, Q4, X, Left)
	register(Q4, Empty, Q1, Empty, Right)

	tape, idx := initTape([]string{A, A, A, A})
	q := Q0

	fmt.Print("&&", getStatus(tape, idx, q))
	for tr, ok := getTransition(tape, idx, q); ok; tr, ok = getTransition(tape, idx, q) {
		tape[idx] = tr.headNext
		if tr.dir == Right {
			idx++
		} else {
			idx--
		}

		q = tr.qNext
		fmt.Println(`\\`)
		fmt.Print(`&\to& `)
		fmt.Print(getStatus(tape, idx, q))
	}
	fmt.Println()
}