Here is a Turing Machine implemented in Java as described by the Wikipedia article:
https://en.wikipedia.org/wiki/Turing_machine
With the copy subroutine test taken from:
https://en.wikipedia.org/wiki/Turing_machine_examples
Tape.java
package org.adrianwalker.turingmachine;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.range;
import static java.util.stream.IntStream.rangeClosed;
import java.util.List;
import java.util.TreeMap;
public final class Tape {
private final TreeMap<Integer, String> cells;
private final String blank;
public Tape(final String blank) {
this.cells = new TreeMap<>();
this.blank = blank;
}
public List<String> getCells() {
return rangeClosed(cells.firstKey(), cells.lastKey())
.boxed()
.map(i -> getCell(i))
.collect(toList());
}
public void putCells(final List<String> symbols) {
range(0, symbols.size())
.boxed()
.forEach(i -> putCell(i, symbols.get(i)));
}
public String getCell(final int position) {
return cells.getOrDefault(position, blank);
}
public void putCell(final int position, final String symbol) {
cells.put(position, symbol);
}
}
Head.java
package org.adrianwalker.turingmachine;
public final class Head {
private final Tape tape;
private final String leftSymbol;
private final String rightSymbol;
private final String noOpSymbol;
private int position = 0;
public Head(
final Tape tape,
final String leftSymbol, final String rightSymbol, final String noOpSymbol) {
this.tape = tape;
this.leftSymbol = leftSymbol;
this.rightSymbol = rightSymbol;
this.noOpSymbol = noOpSymbol;
}
public void move(final String symbol) {
if (noOpSymbol.equals(symbol)) {
return;
}
if (leftSymbol.equals(symbol)) {
position -= 1;
} else if (rightSymbol.equals(symbol)) {
position += 1;
}
}
public String read() {
return tape.getCell(position);
}
public void write(final String symbol) {
if (noOpSymbol.equals(symbol)) {
return;
}
tape.putCell(position, symbol);
}
}
StateRegister.java
package org.adrianwalker.turingmachine;
public final class StateRegister {
private final String haltState;
private String state;
public StateRegister(final String haltState, final String startState) {
this.haltState = haltState;
this.state = startState;
}
public boolean isHaltState() {
return state.equals(haltState);
}
public String getState() {
return state;
}
public void setState(final String state) {
this.state = state;
}
}
Table.java
package org.adrianwalker.turingmachine;
import java.util.HashMap;
import java.util.Map;
public final class Table {
public static final class Entry {
private final String state;
private final String symbol;
private final String writeSymbol;
private final String moveTape;
private final String nextState;
public Entry(
final String state, final String symbol,
final String writeSymbol, final String moveTape, final String nextState) {
this.state = state;
this.symbol = symbol;
this.writeSymbol = writeSymbol;
this.moveTape = moveTape;
this.nextState = nextState;
}
public String getState() {
return state;
}
public String getSymbol() {
return symbol;
}
public String getWriteSymbol() {
return writeSymbol;
}
public String getMoveTape() {
return moveTape;
}
public String getNextState() {
return nextState;
}
}
private static final String SEPARATOR = "_";
private final Map<String, Entry> table;
public Table() {
table = new HashMap<>();
}
public void put(
final String state, final String symbol,
final String writeSymbol, final String moveTape, final String nextState) {
table.put(
state + SEPARATOR + symbol,
new Entry(state, symbol, writeSymbol, moveTape, nextState));
}
public Entry get(final String state, final String symbol) {
return table.get(state + SEPARATOR + symbol);
}
}
TuringMachine.java
package org.adrianwalker.turingmachine;
import org.adrianwalker.turingmachine.Table.Entry;
public final class TuringMachine {
private final Head head;
private final StateRegister stateRegister;
private final Table table;
public TuringMachine(final Head head, final StateRegister stateRegister, final Table table) {
this.head = head;
this.stateRegister = stateRegister;
this.table = table;
}
public long execute() {
long steps = 0;
while (!stateRegister.isHaltState()) {
steps++;
String state = stateRegister.getState();
String symbol = head.read();
Entry entry = table.get(state, symbol);
head.write(entry.getWriteSymbol());
head.move(entry.getMoveTape());
stateRegister.setState(entry.getNextState());
}
return steps;
}
}
TuringMachineTest.java
package org.adrianwalker.turingmachine;
import static java.util.Arrays.asList;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public final class TuringMachineTest {
private static final String BLANK = "0";
private static final String MOVE_LEFT = "L";
private static final String MOVE_RIGHT = "R";
private static final String NO_OP = "N";
private static final String HALT_STATE = "H";
private static final String START_STATE = "A";
@Test
public void testBusyBeaver() {
Tape tape = new Tape(BLANK);
Head head = new Head(tape, MOVE_LEFT, MOVE_RIGHT, NO_OP);
StateRegister stateRegister = new StateRegister(HALT_STATE, START_STATE);
Table table = new Table();
table.put("A", "0", "1", "R", "B");
table.put("A", "1", "1", "L", "C");
table.put("B", "0", "1", "L", "A");
table.put("B", "1", "1", "R", "B");
table.put("C", "0", "1", "L", "B");
table.put("C", "1", "1", "N", "H");
TuringMachine machine = new TuringMachine(head, stateRegister, table);
long steps = machine.execute();
assertEquals(13, steps);
assertEquals(asList("1", "1", "1", "1", "1", "1"), tape.getCells());
}
@Test
public void testCopySubroutine() {
Tape tape = new Tape(BLANK);
tape.putCells(asList("1", "1", "1"));
Head head = new Head(tape, MOVE_LEFT, MOVE_RIGHT, NO_OP);
StateRegister stateRegister = new StateRegister(HALT_STATE, START_STATE);
Table table = new Table();
table.put("A", "0", "N", "N", "H");
table.put("A", "1", "0", "R", "B");
table.put("B", "0", "0", "R", "C");
table.put("B", "1", "1", "R", "B");
table.put("C", "0", "1", "L", "D");
table.put("C", "1", "1", "R", "C");
table.put("D", "0", "0", "L", "E");
table.put("D", "1", "1", "L", "D");
table.put("E", "0", "1", "R", "A");
table.put("E", "1", "1", "L", "E");
TuringMachine machine = new TuringMachine(head, stateRegister, table);
long steps = machine.execute();
assertEquals(28, steps);
assertEquals(asList("1", "1", "1", "0", "1", "1", "1"), tape.getCells());
}
}
Source Code
- Code available in GitHub - turing-machine
Build and Test
The project is a standard Maven project which can be built with:
mvn clean install
