A Golang Turing machine library

Preamble

This is a repost of an old article :)

In 1962, Hungarian mathematician Tibor Radó introduced the Busy Beaver competition for Turing machines: in a class of machines, find one which halts after the greatest number of steps when started on the empty input. Even if it could seem trivial, the Busy Beaver competition has implications in computability theory, the halting problem, and complexity theory.

I decided to use GoLang to implement a Turing machine library and accomplish three goals: first, having a Turing Machine model to play with for learning purpose; second, learning how to use interfaces and the factory pattern, other then testing package to test my code and let it be more flexible for future enhancement (at least I hope!); third, implement some Busy Beaver setup and verify that the model works with well known executions. If you want to discover more about Golang, 60’s math games and beavers, go ahead with reading :D!

Theory first

Before starting, let’s define a Turing machine. A 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, we can image a 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. Everything’s clear?

Implementation

To implement my Turing machine, I choose Golang as language and, to be more flexible, I coded by using the factory pattern. What is a factory pattern?

The factory pattern

The factory pattern is a commonly used pattern in object oriented programming: the main reason you decide to use factory pattern is that it provide to thirds a way to better consume your struct. Instead of initializing instances using something like myStruct := &MyStruct{}, a factory pattern provide a function signature that return your struct, by ensuring that everyone will supply the required attributes.

Now, the cool thing is that in Golang functions can return interfaces instead of structs: interfaces allow you to define behaviour without exposing internal implementation. As in other programming languages, you define method to be implemented inside an interface, and every struct that implement them is considered implementing the interface. This means we can make private structs, while only exposing the interface outside our package, and let user interact with the struct with the only available method inside.

Transactions

The first lines of the package Transaction look like the one shown below:

var ACTIONS = [...]string{"R", "L", "N"}

// Transaction interface
type Transaction interface {
	Validate(m TuringMachine) bool
	Simulate() (state.State, symbol.Symbol, string)
	GetCurrentState() state.State
	GetSymbolScanned() symbol.Symbol
	GetNewState() state.State
	GetSymbolWritten() symbol.Symbol
	GetMoveTape() string
	Print() string
}

// transaction struct
type transaction struct {
	currentState  state.State
	symbolScanned symbol.Symbol
	newState      state.State
	symbolWritten symbol.Symbol
	moveTape      string
}

where state.State and symbol.Symbol refer respectively to the state, symbol packages and the State, Symbol interfaces defined inside them. The Transaction interface defines which methods have to be exposed outside: the transaction struct implements the Transaction interface. Let’s have a look at a couple of methods after that:

// NewTransaction() Create a new Transaction with given
// currentState, symbolScanned, symbolWritten and moveTape action
func NewTransaction(currentState state.State, symbolScanned symbol.Symbol,
    newState state.State, symbolWritten symbol.Symbol, moveTape string) Transaction {

	t := &transaction{}
	t.currentState = currentState
	t.symbolScanned = symbolScanned
	t.newState = newState
	t.symbolWritten = symbolWritten
	t.moveTape = moveTape

	return t

}

The NewTransaction(...) functions solve the problem of exposing the transaction struct, by return a pointer to a struct as the Transaction interface: in fact, since the transaction struct is private we wouldn’t be able to interfact with it. That’s the reason the signature actually returns an interface, that is exposed: this is possible because the pointers can also implement interfaces.

// Validate(m TuringMachine) Validate the transaction t with respect
// to the TuringMachine m. A Transaction to be considered valid
// need to be defined with a valid ACTIONS, the current state of the
// TuringMachine must be equal to the state in which the transaction
// is activated and the head of the TuringMachine must point to the
// the same symbol scanned by the transaction. If all of this three
// condition are verified, Validate(m TuringMachine) over t returns
// true; it returns otherwise
func (t *transaction) Validate(m TuringMachine) bool {

	// check if moveTape action is allowed
	for _, a := range ACTIONS {
		if strings.EqualFold(a, t.moveTape) {
			// check if actual state and scanned
                        // symbol match with transaction
			return t.currentState.Equal(m.GetActualState())
                            && t.symbolScanned.Equal(m.GetActualSymbol())
		}
	}

	return false

}

The Validate function return true if a transaction is valid inside the Turing Machine m. A Transaction is valid if

the action to be execute is a valid action identifier - it’s contained in the set of {“L”,“R”,“N”};
the current state of the Turing machine is equal to the state in which the transaction is activated;
the current head of the Turing machine points to the the same symbol scanned by the transaction;

Similarly, you can implement Symbol, State and TuringMachine. Since Symbol and State packages are pretty easy to implement, let’s have a look the Turing machine definition and the execution method defined inside it.

Turing Machine

The Turing machine interface is defined as shown below:

// TuringMachine interface
type TuringMachine interface {
	Run()
	Step() state.State
	Computed() bool
	GetActualSymbol() symbol.Symbol
	GetActualState() state.State
	MoveHeadPointer(s symbol.Symbol, m string) int
	Print() string
}

// turingMachine struct
type turingMachine struct {
	initialStates set.Set
	finalStates   set.Set
	transactions  set.Set
	actualState   state.State
	headPointer   int
	tape          []symbol.Symbol
}

The key methods are Run(), Step() and Computed(). The Run() method is the simplest one: it runs the Step() function indefinitely until the Turing machine is computed completely.

func (tm *turingMachine) Run() {

	for !tm.Computed() {
		tm.Step()
	}
	return

}

A Turing machine is computed completely when it reaches a Final State, that is exactly what the Computed method said about our Turing machine.

func (tm *turingMachine) Computed() bool {

	return tm.actualState.IsFinal()

}

What about the Step() function?

func (tm *turingMachine) Step() state.State {

	for _, t := range tm.transactions.Iterator() {
		if t.(Transaction).Validate(tm) {
			return tm.Execute(t.(Transaction))
		}
	}
	return tm.actualState

}

For the execute part, you can have a look directly here.

Before going ahead

Testing! I learn how much you gain by testing your code playing with returns, default, pointers and indexes. Fortunately, build testing in Golang is quite easy, specially for simple functions like the one we shown before. For instance, the following test function is defined in a symbol_test.go file - at the same level of the symbol. Then

func TestErase(t *testing.T) {

	// test erase a Symbol
	s := NewSymbol(uint8(1))
	s.Erase()
	if v := s.GetValue(); v != BLANK {
		t.Errorf("Erase was incorrect, got: %d, want: %d.", v, uint8(BLANK))
	}

}

The testing functions are always named like [Test]OriginalFunctionName and always accept only one parameter t *testing.T¹. After that, from inside your project folder run this in a shell:

go test ./...

Just prepend GOCACHE=off if you want to ignore caching. For the entire code, follow the link.

Now it’s time to build our Busy Beaver!!

The Busy Beaver competition

The Busy Beaver game consists of designing a halting, binary-alphabet Turing machine which writes the most 1s on the tape, using only a limited set of states. The rules for the 2-state game are as follows:

The machine must have two states in addition to the halting state, and
The tape starts with 0s only

As the player, you should conceive each state aiming for the maximum output of 1s on the tape while making sure the machine will halt eventually.

The n-th Busy Beaver, BB-n or simply “Busy Beaver” is the Turing machine that wins the n-state Busy Beaver Game. That is, it attains the maximum number of 1s among all other possible n-state competing Turing Machines. The BB-2 Turing machine, for instance, achieves four 1s in six steps.

You can easily build the BB-2 Beaver with 4 simple transaction plus 1 to move from the initial state to the “A” state.

tr0 := transaction.NewTransaction(
	state.NewInitialState(),
	symbol.NewSymbol(uint8(0)),
	state.NewState(uint8(21)),
	symbol.NewSymbol(uint8(0)), "N")

tr1 := transaction.NewTransaction(
	state.NewState(uint8(21)),
	symbol.NewSymbol(uint8(0)),
	state.NewState(uint8(22)),
	symbol.NewSymbol(uint8(1)), "R")

tr2 := transaction.NewTransaction(
	state.NewState(uint8(21)),
	symbol.NewSymbol(uint8(1)),
	state.NewState(uint8(22)),
	symbol.NewSymbol(uint8(1)), "L")

tr3 := transaction.NewTransaction(
	state.NewState(uint8(22)),
	symbol.NewSymbol(uint8(0)),
	state.NewState(uint8(21)),
	symbol.NewSymbol(uint8(1)), "L")

tr4 := transaction.NewTransaction(
	state.NewState(uint8(22)),
	symbol.NewSymbol(uint8(1)),
	state.NewFinalState(),
	symbol.NewSymbol(uint8(1)), "R")

Or, in a more user friendly format:

	21	22
0	1R22	1L21
1	1L22	1RFINAL

with an initial transaction from INITIAL to 21 with symbol 0 scanned, that does nothing and ports to state 21. Let’s have a look at the evolution of the BB-2 Turing machine: first apply first transaction from INITIAL to A - it a sort of 0° Step that just change the state of the machine from INITIAL to 21, in such a way that the init tape looks like this

$$ … 0 0 0 0 0 [0] 0 0 0 0 0 0 0 … $$

BB-2 Beaver Execution

1° Step: apply 1R22 transaction from A in 0 to B by writing 1, evolve in state B and move the cursor one step in the right direction

$$ … 0 0 0 0 0 1 [0] 0 0 0 0 0 0 … $$

2° Step: apply 1L21 transaction from B in 0 to A by writing 1, evolve in state A and move the cursor one step in the left direction

$$ … 0 0 0 0 0 [1] 1 0 0 0 0 0 0 … $$

3° Step: apply 1L22 transaction from A in 1 to B by writing 1 (this will result in an overwrite) and move the cursor one step in the left direction

$$ … 0 0 0 0 [0] 1 1 0 0 0 0 0 0 … $$

4° Step: apply 1L21 transaction from B in 0 to A by writing 1, evolve in state A and move the cursor one step in the left direction

$$ … 0 0 0 [0] 1 1 1 0 0 0 0 0 0 … $$

5° Step: apply 1R22 transaction from A in 0 to B by writing 1, evolve in state B and move the cursor one step in the right direction

$$ … 0 0 0 1 [1] 1 1 0 0 0 0 0 0 … $$

6° Step: finally, apply 1RFINAL transaction from B in 1 to FINAL by writing 1 (this will result in an overwrite), evolve in state B and move the cursor one step in the right direction

$$ … 0 0 0 1 1 [1] 1 0 0 0 0 0 0 … $$

And the execution is finished! Four 1s, six steps, as promised!

To be continued with Non Deterministic experiment…

Conclusion

For the most curious people, the original paper is Tibor Radó - On Non-Computable Functions - here. My Github repo with my implementation of the Busy Beaver game is available here.

Here the code ↩︎

Subscribe to my newsletter to be informed about my new blog posts, talks and activities.

Preamble#

Theory first#

Implementation#

The factory pattern#

Transactions#

Turing Machine#

Before going ahead#

The Busy Beaver competition#

BB-2 Beaver Execution#

Conclusion#