239 lines
8.9 KiB
Java
239 lines
8.9 KiB
Java
import java.util.HashMap;
|
|
import java.util.HashSet;
|
|
import java.util.LinkedList;
|
|
import java.util.ListIterator;
|
|
import java.util.List;
|
|
import java.util.Set;
|
|
import java.util.Map;
|
|
|
|
public class UTM {
|
|
private List<String> tape;
|
|
private String blankSymbol;
|
|
private ListIterator<String> head;
|
|
private Map<StateTapeSymbolPair, Transition> transitions = new HashMap<StateTapeSymbolPair, Transition>();
|
|
private Set<String> terminalStates;
|
|
private String initialState;
|
|
|
|
public UTM(Set<Transition> transitions, Set<String> terminalStates, String initialState, String blankSymbol) {
|
|
this.blankSymbol = blankSymbol;
|
|
for (Transition t : transitions) {
|
|
this.transitions.put(t.from, t);
|
|
}
|
|
this.terminalStates = terminalStates;
|
|
this.initialState = initialState;
|
|
}
|
|
|
|
public static class StateTapeSymbolPair {
|
|
private String state;
|
|
private String tapeSymbol;
|
|
|
|
public StateTapeSymbolPair(String state, String tapeSymbol) {
|
|
this.state = state;
|
|
this.tapeSymbol = tapeSymbol;
|
|
}
|
|
|
|
// These methods can be auto-generated by Eclipse.
|
|
@Override
|
|
public int hashCode() {
|
|
final int prime = 31;
|
|
int result = 1;
|
|
result = prime * result
|
|
+ ((state == null) ? 0 : state.hashCode());
|
|
result = prime
|
|
* result
|
|
+ ((tapeSymbol == null) ? 0 : tapeSymbol
|
|
.hashCode());
|
|
return result;
|
|
}
|
|
|
|
// These methods can be auto-generated by Eclipse.
|
|
@Override
|
|
public boolean equals(Object obj) {
|
|
if (this == obj)
|
|
return true;
|
|
if (obj == null)
|
|
return false;
|
|
if (getClass() != obj.getClass())
|
|
return false;
|
|
StateTapeSymbolPair other = (StateTapeSymbolPair) obj;
|
|
if (state == null) {
|
|
if (other.state != null)
|
|
return false;
|
|
} else if (!state.equals(other.state))
|
|
return false;
|
|
if (tapeSymbol == null) {
|
|
if (other.tapeSymbol != null)
|
|
return false;
|
|
} else if (!tapeSymbol.equals(other.tapeSymbol))
|
|
return false;
|
|
return true;
|
|
}
|
|
|
|
@Override
|
|
public String toString() {
|
|
return "(" + state + "," + tapeSymbol + ")";
|
|
}
|
|
}
|
|
|
|
public static class Transition {
|
|
private StateTapeSymbolPair from;
|
|
private StateTapeSymbolPair to;
|
|
private int direction; // -1 left, 0 neutral, 1 right.
|
|
|
|
public Transition(StateTapeSymbolPair from, StateTapeSymbolPair to, int direction) {
|
|
this.from = from;
|
|
this.to = to;
|
|
this.direction = direction;
|
|
}
|
|
|
|
@Override
|
|
public String toString() {
|
|
return from + "=>" + to + "/" + direction;
|
|
}
|
|
}
|
|
|
|
public void initializeTape(List<String> input) { // Arbitrary Strings as symbols.
|
|
tape = input;
|
|
}
|
|
|
|
public void initializeTape(String input) { // Uses single characters as symbols.
|
|
tape = new LinkedList<String>();
|
|
for (int i = 0; i < input.length(); i++) {
|
|
tape.add(input.charAt(i) + "");
|
|
}
|
|
}
|
|
|
|
public List<String> runTM() { // Returns null if not in terminal state.
|
|
if (tape.size() == 0) {
|
|
tape.add(blankSymbol);
|
|
}
|
|
|
|
head = tape.listIterator();
|
|
head.next();
|
|
head.previous();
|
|
|
|
StateTapeSymbolPair tsp = new StateTapeSymbolPair(initialState, tape.get(0));
|
|
|
|
while (transitions.containsKey(tsp)) { // While a matching transition exists.
|
|
System.out.println(this + " --- " + transitions.get(tsp));
|
|
Transition trans = transitions.get(tsp);
|
|
head.set(trans.to.tapeSymbol); // Write tape symbol.
|
|
tsp.state = trans.to.state; // Change state.
|
|
if (trans.direction == -1) { // Go left.
|
|
if (!head.hasPrevious()) {
|
|
head.add(blankSymbol); // Extend tape.
|
|
}
|
|
tsp.tapeSymbol = head.previous(); // Memorize tape symbol.
|
|
} else if (trans.direction == 1) { // Go right.
|
|
head.next();
|
|
if (!head.hasNext()) {
|
|
head.add(blankSymbol); // Extend tape.
|
|
head.previous();
|
|
}
|
|
tsp.tapeSymbol = head.next(); // Memorize tape symbol.
|
|
head.previous();
|
|
} else {
|
|
tsp.tapeSymbol = trans.to.tapeSymbol;
|
|
}
|
|
}
|
|
|
|
System.out.println(this + " --- " + tsp);
|
|
|
|
if (terminalStates.contains(tsp.state)) {
|
|
return tape;
|
|
} else {
|
|
return null;
|
|
}
|
|
}
|
|
|
|
@Override
|
|
public String toString() {
|
|
try {
|
|
int headPos = head.previousIndex();
|
|
String s = "[ ";
|
|
|
|
for (int i = 0; i <= headPos; i++) {
|
|
s += tape.get(i) + " ";
|
|
}
|
|
|
|
s += "[H] ";
|
|
|
|
for (int i = headPos + 1; i < tape.size(); i++) {
|
|
s += tape.get(i) + " ";
|
|
}
|
|
|
|
return s + "]";
|
|
} catch (Exception e) {
|
|
return "";
|
|
}
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
// Simple incrementer.
|
|
String init = "q0";
|
|
String blank = "b";
|
|
|
|
Set<String> term = new HashSet<String>();
|
|
term.add("qf");
|
|
|
|
Set<Transition> trans = new HashSet<Transition>();
|
|
|
|
trans.add(new Transition(new StateTapeSymbolPair("q0", "1"), new StateTapeSymbolPair("q0", "1"), 1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("q0", "b"), new StateTapeSymbolPair("qf", "1"), 0));
|
|
|
|
UTM machine = new UTM(trans, term, init, blank);
|
|
machine.initializeTape("111");
|
|
System.out.println("Output (si): " + machine.runTM() + "\n");
|
|
|
|
// Busy Beaver (overwrite variables from above).
|
|
init = "a";
|
|
|
|
term.clear();
|
|
term.add("halt");
|
|
|
|
blank = "0";
|
|
|
|
trans.clear();
|
|
|
|
// Change state from "a" to "b" if "0" is read on tape, write "1" and go to the right. (-1 left, 0 nothing, 1 right.)
|
|
trans.add(new Transition(new StateTapeSymbolPair("a", "0"), new StateTapeSymbolPair("b", "1"), 1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("a", "1"), new StateTapeSymbolPair("c", "1"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("b", "0"), new StateTapeSymbolPair("a", "1"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("b", "1"), new StateTapeSymbolPair("b", "1"), 1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("c", "0"), new StateTapeSymbolPair("b", "1"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("c", "1"), new StateTapeSymbolPair("halt", "1"), 0));
|
|
|
|
machine = new UTM(trans, term, init, blank);
|
|
machine.initializeTape("");
|
|
System.out.println("Output (bb): " + machine.runTM());
|
|
|
|
// Sorting test (overwrite variables from above).
|
|
init = "s0";
|
|
blank = "*";
|
|
|
|
term = new HashSet<String>();
|
|
term.add("see");
|
|
|
|
trans = new HashSet<Transition>();
|
|
|
|
trans.add(new Transition(new StateTapeSymbolPair("s0", "a"), new StateTapeSymbolPair("s0", "a"), 1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s0", "b"), new StateTapeSymbolPair("s1", "B"), 1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s0", "*"), new StateTapeSymbolPair("se", "*"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s1", "a"), new StateTapeSymbolPair("s1", "a"), 1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s1", "b"), new StateTapeSymbolPair("s1", "b"), 1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s1", "*"), new StateTapeSymbolPair("s2", "*"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s2", "a"), new StateTapeSymbolPair("s3", "b"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s2", "b"), new StateTapeSymbolPair("s2", "b"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s2", "B"), new StateTapeSymbolPair("se", "b"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s3", "a"), new StateTapeSymbolPair("s3", "a"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s3", "b"), new StateTapeSymbolPair("s3", "b"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("s3", "B"), new StateTapeSymbolPair("s0", "a"), 1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("se", "a"), new StateTapeSymbolPair("se", "a"), -1));
|
|
trans.add(new Transition(new StateTapeSymbolPair("se", "*"), new StateTapeSymbolPair("see", "*"), 1));
|
|
|
|
machine = new UTM(trans, term, init, blank);
|
|
machine.initializeTape("babbababaa");
|
|
System.out.println("Output (sort): " + machine.runTM() + "\n");
|
|
}
|
|
}
|