Download code

Jump to: navigation, search

Back to Turing_machine_simulator_(Java)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

example_output.txt

 1 $ java TuringSimulator ab
 2                  v
 3           start: ab###########################################################
 4                   v
 5      scan_right: #b###########################################################
 6                    v
 7      scan_right: #b###########################################################
 8                   v
 9         reverse: #b###########################################################
10                  v
11       scan_left: #############################################################
12                   v
13           start: #############################################################
14                    v
15           check: #############################################################
16                     v
17          finish: #############################################################


hijacker
hijacker
hijacker
hijacker

TuringSimulator.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Turing_machine_simulator_(Java)?oldid=12337
 14 */
 15 
 16 import java.util.Map;
 17 import java.util.HashMap;
 18 import java.util.List;
 19 import java.util.ArrayList;
 20 
 21 enum Direction { LEFT, RIGHT };
 22 
 23 
 24 class ControlState<Symbol> {
 25     public final String name;
 26     public final boolean accepting;
 27     public final Map<Symbol,TransitionResult<Symbol>> transitions
 28         = new HashMap<Symbol,TransitionResult<Symbol>>();
 29 
 30     public ControlState(String n, boolean a) { name = n; accepting = a; }
 31 
 32     public String toString() { return name; }
 33 }
 34 
 35 
 36 class TransitionResult<Symbol> {
 37     public final ControlState<Symbol> controlState;
 38     public final Symbol writeSymbol;
 39     public final Direction dir;
 40 
 41     public TransitionResult(ControlState<Symbol> c, Symbol s, Direction d)
 42     {
 43         controlState = c; writeSymbol = s; dir = d;
 44     }
 45 }
 46 
 47 class TuringMachine<Symbol>
 48 {
 49     public final ControlState<Symbol> initialControlState;
 50     public final Symbol blankSymbol;
 51 
 52     public TuringMachine(ControlState<Symbol> x, Symbol b)
 53     {
 54         initialControlState = x; blankSymbol = b;
 55     }
 56 }
 57 
 58 enum MySymbol
 59 {
 60     A("a"), B("b"), BLANK("#");
 61 
 62     private final String ch;
 63     MySymbol(String s) { ch = s; }
 64     public String toString() { return ch; }
 65     public static List<MySymbol> parseString(String s)
 66     {
 67         List<MySymbol> result = new ArrayList<MySymbol>();
 68         for (int i = 0; i < s.length(); i++) {
 69             switch (s.charAt(i)) {
 70             case 'a': result.add(A); break;
 71             case 'b': result.add(B); break;
 72             default: assert false;
 73             }
 74         }
 75         return result;
 76     }
 77 }
 78 
 79 
 80 public class TuringSimulator<Symbol> {
 81     public static final int TRACE_TAPE_CHARS = 60;
 82 
 83     public final TuringMachine<Symbol> machine;
 84     public ControlState<Symbol> controlState;
 85     public int headPosition = 0; // Initially at left end
 86     public final List<Symbol> tape;
 87 
 88     public TuringSimulator(TuringMachine<Symbol> m, List<Symbol> inputString) {
 89         machine = m;
 90         controlState = machine.initialControlState;
 91         tape = new ArrayList<Symbol>(inputString);
 92     }
 93     public void update(ControlState<Symbol> newControlState, Direction dir, Symbol writeSymbol)
 94     {
 95         controlState = newControlState;
 96         if (headPosition < tape.size())
 97             tape.set(headPosition, writeSymbol);
 98         else if (headPosition == tape.size())
 99             tape.add(writeSymbol);
100         else
101             assert false;
102 
103         switch (dir) {
104         case LEFT:
105             assert headPosition > 0;
106             headPosition--;
107             break;
108         case RIGHT:
109             headPosition++;
110             break;
111         }
112     }
113     public void trace() {
114         for (int i = -17; i < TRACE_TAPE_CHARS; i++) {
115             if (i >= headPosition) {
116                 System.out.print("v"); // points down
117                 break;
118             }
119             System.out.print(" ");
120         }
121         System.out.println();
122 
123         System.out.printf("%15s: ", controlState);
124 
125         for (int i = 0; i < TRACE_TAPE_CHARS; i++) {
126             System.out.print(tapeAt(i));
127         }
128         System.out.println();
129     }
130 
131     public void run() {
132         trace();
133         while (!controlState.accepting) {
134             TransitionResult<Symbol> next = controlState.transitions.get(currentSymbol());
135             if (next == null) {
136                 System.out.println("invalid transition");
137                 break;
138             }
139             update(next.controlState, next.dir, next.writeSymbol);
140             trace();
141         }
142     }
143 
144     public Symbol tapeAt(int pos)
145     {
146         return (pos < tape.size()) ? tape.get(pos) : machine.blankSymbol;
147     }
148 
149     public Symbol currentSymbol() { return tapeAt(headPosition); }
150 
151     public static void main(String[] args) {
152         ControlState<MySymbol> s0 = new ControlState<MySymbol>("start", false);
153 	ControlState<MySymbol> s1 = new ControlState<MySymbol>("scan_right", false);
154 	ControlState<MySymbol> s2 = new ControlState<MySymbol>("reverse", false);
155 	ControlState<MySymbol> s3 = new ControlState<MySymbol>("scan_left", false);
156 	ControlState<MySymbol> s4 = new ControlState<MySymbol>("check", false);
157 	ControlState<MySymbol> s5 = new ControlState<MySymbol>("finish", true);
158 
159 	s0.transitions.put(MySymbol.BLANK, new TransitionResult<MySymbol>(s4, MySymbol.BLANK, Direction.RIGHT));
160 	s0.transitions.put(MySymbol.A,     new TransitionResult<MySymbol>(s1, MySymbol.BLANK, Direction.RIGHT));
161 	s4.transitions.put(MySymbol.BLANK, new TransitionResult<MySymbol>(s5, MySymbol.BLANK, Direction.RIGHT));
162 	s1.transitions.put(MySymbol.A,     new TransitionResult<MySymbol>(s1, MySymbol.A,     Direction.RIGHT));
163 	s1.transitions.put(MySymbol.B,     new TransitionResult<MySymbol>(s1, MySymbol.B,     Direction.RIGHT));
164 	s1.transitions.put(MySymbol.BLANK, new TransitionResult<MySymbol>(s2, MySymbol.BLANK, Direction.LEFT));
165 	s2.transitions.put(MySymbol.B,     new TransitionResult<MySymbol>(s3, MySymbol.BLANK, Direction.LEFT));
166 	s3.transitions.put(MySymbol.A,     new TransitionResult<MySymbol>(s3, MySymbol.A,     Direction.LEFT));
167 	s3.transitions.put(MySymbol.B,     new TransitionResult<MySymbol>(s3, MySymbol.B,     Direction.LEFT));
168 	s3.transitions.put(MySymbol.BLANK, new TransitionResult<MySymbol>(s0, MySymbol.BLANK, Direction.RIGHT));
169 
170 	TuringMachine<MySymbol> machine = new TuringMachine<MySymbol>(s0, MySymbol.BLANK);
171 
172 
173         if (args.length < 1) {
174             System.err.println("Syntax: java TuringSimulator <input string>");
175             System.exit(-1);
176         }
177         List<MySymbol> input = MySymbol.parseString(args[0]);
178         TuringSimulator<MySymbol> sim = new TuringSimulator<MySymbol>(machine, input);
179         sim.run();
180     }
181 }
182 


hijacker
hijacker
hijacker
hijacker