A Busy Beaver simulator and Pixmap writer

bb5.go

package main

import "fmt"

type tm struct {
	halt int
	states []state
}

type trans struct {
	flip bool
	move int
	next int
}

type state struct {
	t0, t1 trans
}

type tape struct {
	data []bool
	position, shift int
}

// 5-state Busy Beaver
var bb5 = tm{5, []state{
	state{trans{true, -1, 1}, trans{false, -1, 0}},
	state{trans{true,  1, 2}, trans{false,  1, 1}},
	state{trans{true, -1, 0}, trans{false,  1, 3}},
	state{trans{true, -1, 0}, trans{false,  1, 4}},
	state{trans{true,  1, 5}, trans{true,   1, 2}},
}}

// Compute one step of the given machine.
func step(m tm, history *[]tape, s int, t *tape) int {
	c := t.data[t.position + t.shift]
	trans := m.states[s].t0
	if c {
		trans = m.states[s].t1
	}

	// Add the tape to the history if the contents change.
	if trans.flip {
		tapeCopy := append([]bool{}, t.data...)
		*history = append(*history, tape{tapeCopy, t.position, t.shift})
		t.data[t.position + t.shift] = !c
	}

	// Add space to the tape if needed.
	t.position += trans.move
	if t.position + t.shift < 0 {
		t.shift++
		t.data = append([]bool{false}, t.data...)
	} else if t.position + t.shift >= len(t.data) {
		t.data = append(t.data, false)
	}

	return trans.next
}

func main() {
	history := make([]tape, 0)
	i, s, t := 0, 0, tape{[]bool{false}, 0, 0}
	for s != bb5.halt {
		i++
		s = step(bb5, &history, s, &t)
	}

	// Write the history into an Netpbm pixmap.
	last := t
	width := len(last.data)
	history = append(history, last)

	fmt.Println("P1")
	fmt.Println("# 5-state Busy Beaver tape history")
	fmt.Printf("%d %d\n", width, len(history))
	for _, t := range history {
		offset := last.shift - t.shift
		for k := 0; k < width; k++ {
			if k >= offset &&
				k - offset < len(t.data) &&
				t.data[k-offset] {
				fmt.Print("1")
			} else {
				fmt.Print("0")
			}
		}
		fmt.Print("\n")
	}
}