Rosetta Code

Universal Turing machine: Difference between revisions

Page Discussion

Universal Turing machine (view source)

Revision as of 21:04, 17 February 2013

286 bytes removed ,  11 years ago
m
→‎{{header|Java}}
Line 584:
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.List;
import java.util.Set;
import java.util.Map;
 
public class UTM {
private LinkedListList<String> tape;
private String blankSymbol;
private ListIterator<String> head;
private HashMapMap<StateTapeSymbolPair, Transition> transitions = new HashMap<StateTapeSymbolPair, Transition>();
private Set<String> terminalStates;
private String initialState;
public UTM(HashSetSet<Transition> transitions, Set<String> terminalStates, String initialState, String blankSymbol) {
this.blankSymbol = blankSymbol;
this.transitions = new HashMap<StateTapeSymbolPair, Transition>();
for (Transition t : transitions) {
this.transitions.put(t.from, t);
Line 609 ⟶ 610:
 
public StateTapeSymbolPair(String state, String tapeSymbol) {
super();
this.state = state;
this.tapeSymbol = tapeSymbol;
Line 620:
int result = 1;
result = prime * result
+ ((this.state == null) ? 0 : this.state.hashCode());
result = prime
* result
+ ((this.tapeSymbol == null) ? 0 : this.tapeSymbol
.hashCode());
return result;
Line 638:
return false;
StateTapeSymbolPair other = (StateTapeSymbolPair) obj;
if (this.state == null) {
if (other.state != null)
return false;
} else if (!this.state.equals(other.state))
return false;
if (this.tapeSymbol == null) {
if (other.tapeSymbol != null)
return false;
} else if (!this.tapeSymbol.equals(other.tapeSymbol))
return false;
return true;
Line 653:
@Override
public String toString() {
return "(" + this.state + "," + this.tapeSymbol + ")";
}
}
Line 663:
 
public Transition(StateTapeSymbolPair from, StateTapeSymbolPair to, int direction) {
super() this.from = from;
this.from = from;
this.to = to;
this.direction = direction;
Line 671 ⟶ 670:
@Override
public String toString() {
return this.from + "=>" + this.to + "/" + this.direction;
}
}
public void initializeTape(LinkedListList<String> input) { // Arbitrary Strings as symbols.
this.tape = input;
}
public void initializeTape(String input) { // Uses single characters as symbols.
this.tape = new LinkedList<String>();
for (int i = 0; i < input.length(); i++) {
this.tape.add(input.charAt(i) + "");
}
}
public LinkedListList<String> runTM() { // Returns null if not in terminal state.
if (this.tape.size() == 0) {
this.tape.add(this.blankSymbol);
}
this.head = this.tape.listIterator();
this.head.next();
this.head.previous();
StateTapeSymbolPair tsp = new StateTapeSymbolPair(this.initialState, this.tape.get(0));
while (this.transitions.containsKey(tsp)) { // While a matching transition exists.
System.out.println(this + " --- " + this.transitions.get(tsp));
Transition trans = this.transitions.get(tsp);
this.head.set(trans.to.tapeSymbol); // Write tape symbol.
tsp.state = trans.to.state; // Change state.
if (trans.direction == -1) { // Go left.
if (!this.head.hasPrevious()) {
this.head.add(this.blankSymbol); // Extend tape.
}
tsp.tapeSymbol = this.head.previous(); // Memorize tape symbol.
} else if (trans.direction == 1) { // Go right.
this.head.next();
if (!this.head.hasNext()) {
this.head.add(this.blankSymbol); // Extend tape.
this.head.previous();
}
tsp.tapeSymbol = this.head.next(); // Memorize tape symbol.
this.head.previous();
} else {
tsp.tapeSymbol = trans.to.tapeSymbol;
Line 722 ⟶ 721:
System.out.println(this + " --- " + tsp);
if (this.terminalStates.contains(tsp.state)) {
return this.tape;
} else {
return null;
Line 732 ⟶ 731:
public String toString() {
try {
int headPos = this.head.previousIndex();
String s = "[ ";
for (int i = 0; i <= headPos; i++) {
s += this.tape.get(i) + " ";
}
 
s += "[H] ";
for (int i = headPos + 1; i < this.tape.size(); i++) {
s += this.tape.get(i) + " ";
}
 
Line 756 ⟶ 755:
String blank = "b";
HashSetSet<String> term = new HashSet<String>();
term.add("qf");
HashSetSet<Transition> trans = new HashSet<Transition>();
trans.add(new Transition(new StateTapeSymbolPair("q0", "1"), new StateTapeSymbolPair("q0", "1"), 1));
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/224229"