Universal Turing machine: Difference between revisions

Content added Content deleted
m (→‎{{header|Java}}: Generics and foreach started in Java 5, more-correct highlighting, no signatures on examples)
(Fixed a bug in the code - head was placed incorrectly after extending tape to the right.)
Line 587: Line 587:


public class UTM {
public class UTM {
⚫
private LinkedList<String> tape;
private LinkedList<String> tape;
private String blankSymbol;
private String blankSymbol;
Line 699: Line 698:
while (this.transitions.containsKey(tsp)) { // While a matching transition exists.
while (this.transitions.containsKey(tsp)) { // While a matching transition exists.
System.out.println(tape + " --- " + tsp);
System.out.println(this + " --- " + this.transitions.get(tsp));
Transition trans = this.transitions.get(tsp);
Transition trans = this.transitions.get(tsp);
this.head.set(trans.to.tapeSymbol); // Write tape symbol.
this.head.set(trans.to.tapeSymbol); // Write tape symbol.
tsp.state = trans.to.state; // Change state.
tsp.state = trans.to.state; // Change state.
if (trans.direction == -1) { // Go left.
if (trans.direction == -1) { // Go left.
⚫
tsp.tapeSymbol = this.head.previous(); // Memorize tape symbol.
if (!this.head.hasPrevious()) {
if (!this.head.hasPrevious()) {
this.head.add(this.blankSymbol); // Extend tape.
this.head.add(this.blankSymbol); // Extend tape.
⚫
this.head.previous();
⚫
this.head.next();
tsp.tapeSymbol = this.blankSymbol; // Memorize tape symbol.
tsp.tapeSymbol = this.blankSymbol; // Memorize tape symbol.
}
}
⚫
tsp.tapeSymbol = this.head.previous(); // Memorize tape symbol.
} else if (trans.direction == 1) { // Go right.
} else if (trans.direction == 1) { // Go right.
tsp.tapeSymbol = this.head.next(); // Memorize tape symbol.
tsp.tapeSymbol = this.head.next(); // Memorize tape symbol.
Line 716: Line 713:
this.head.add(this.blankSymbol); // Extend tape.
this.head.add(this.blankSymbol); // Extend tape.
this.head.previous();
this.head.previous();
⚫
this.head.next();
tsp.tapeSymbol = this.blankSymbol; // Memorize tape symbol.
tsp.tapeSymbol = this.blankSymbol; // Memorize tape symbol.
}
}
Line 724: Line 720:
}
}
System.out.println(tape + " --- " + tsp);
System.out.println(this + " --- " + tsp);
if (this.terminalStates.contains(tsp.state)) {
if (this.terminalStates.contains(tsp.state)) {
Line 730: Line 726:
} else {
} else {
return null;
return null;
}
⚫
}

@Override
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) + " ";
}

return s + "]";
} catch (Exception e) {
return "";
}
}
}
}
Line 776: Line 794:
{{out}}
{{out}}


<pre>[1, 1, 1] --- (q0,1)
<pre>[ [H] 1 1 1 ] --- (q0,1)=>(q0,1)/1
[1, 1, 1] --- (q0,1)
[ 1 [H] 1 1 ] --- (q0,1)=>(q0,1)/1
[1, 1, 1] --- (q0,1)
[ 1 1 [H] 1 ] --- (q0,1)=>(q0,1)/1
[1, 1, 1, b] --- (q0,b)
[ 1 1 1 [H] b ] --- (q0,b)=>(qf,1)/0
[1, 1, 1, 1] --- (qf,1)
[ 1 1 1 [H] 1 ] --- (qf,1)
Output (si): [1, 1, 1, 1]
Output (si): [1, 1, 1, 1]


[0] --- (a,0)
[ [H] 0 ] --- (a,0)=>(b,1)/1
[1, 0] --- (b,0)
[ 1 [H] 0 ] --- (b,0)=>(a,1)/-1
[1, 1] --- (a,1)
[ [H] 1 1 ] --- (a,1)=>(c,1)/-1
[0, 1, 1] --- (c,0)
[ [H] 0 1 1 ] --- (c,0)=>(b,1)/-1
[0, 1, 1, 1] --- (b,0)
[ [H] 0 1 1 1 ] --- (b,0)=>(a,1)/-1
[0, 1, 1, 1, 1] --- (a,0)
[ [H] 0 1 1 1 1 ] --- (a,0)=>(b,1)/1
[1, 1, 1, 1, 1] --- (b,1)
[ 1 [H] 1 1 1 1 ] --- (b,1)=>(b,1)/1
[1, 1, 1, 1, 1] --- (b,1)
[ 1 1 [H] 1 1 1 ] --- (b,1)=>(b,1)/1
[1, 1, 1, 1, 1] --- (b,1)
[ 1 1 1 [H] 1 1 ] --- (b,1)=>(b,1)/1
[1, 1, 1, 1, 1, 0] --- (b,0)
[ 1 1 1 1 [H] 1 ] --- (b,1)=>(b,1)/1
[1, 1, 1, 1, 1, 1] --- (a,1)
[ 1 1 1 1 1 [H] 0 ] --- (b,0)=>(a,1)/-1
[1, 1, 1, 1, 1, 1] --- (c,1)
[ 1 1 1 1 [H] 1 1 ] --- (a,1)=>(c,1)/-1
[1, 1, 1, 1, 1, 1] --- (halt,1)
[ 1 1 1 [H] 1 1 1 ] --- (c,1)=>(halt,1)/0
[ 1 1 1 [H] 1 1 1 ] --- (halt,1)
Output (bb): [1, 1, 1, 1, 1, 1]</pre>
Output (bb): [1, 1, 1, 1, 1, 1]</pre>


Retrieved from "https://rosettacode.org/wiki/Universal_Turing_machine"