152 lines
3.2 KiB
Text
152 lines
3.2 KiB
Text
module turing;
|
|
|
|
extern printf;
|
|
|
|
struct @Command {
|
|
field @Integer tape {get:tape,set:stape};
|
|
field @Integer move {get:move,set:smove};
|
|
field @Integer next {get:next,set:snext};
|
|
|
|
@Command init(@Integer tape, @Integer move, @Integer next) [
|
|
this.stape(tape);
|
|
this.smove(move);
|
|
this.snext(next);
|
|
return this;
|
|
]
|
|
};
|
|
|
|
doc 2 dimansional array structure;
|
|
|
|
struct @Rules {
|
|
|
|
field @Integer maxstates { get: maxstates, set: smaxstates };
|
|
field @Integer maxvalue { get: maxvalue, set: smaxvalue };
|
|
|
|
field @Array<@Array<@Command> > table {get: t, set: st};
|
|
|
|
@Rules init(@Integer states, @Integer values)
|
|
[
|
|
this.smaxstates(states);
|
|
this.smaxvalue(values);
|
|
this.st(new @Array<@Array<@Command> >.init(states));
|
|
return this;
|
|
]
|
|
|
|
@Void setRule(@Integer state, @Integer tape, @Command command)
|
|
[
|
|
if (null == this::t.get(state)) {
|
|
this::t.set(state, new @Array<@Command>.init(this::maxvalue));
|
|
}
|
|
this::t.get(state).set(tape, command);
|
|
]
|
|
|
|
@Command getRule(@Integer state, @Integer tape)
|
|
[
|
|
return this::t.get(state).get(tape);
|
|
]
|
|
|
|
};
|
|
|
|
@Void emulateTuring(@Rules rules, @Integer start, @Integer stop, @Array<@Integer> tape, @Integer blank) [
|
|
var tapepointer = 0;
|
|
var state = start;
|
|
|
|
doc output;
|
|
printf("Tape\tState\n");
|
|
|
|
while (state != stop) {
|
|
doc add more cells to the tape;
|
|
if (tapepointer == tape::size) tape.add(blank);
|
|
if (tapepointer == 0-1) { tape = (new @Array<@Integer>..blank).addAll(tape); tapepointer = 0; }
|
|
|
|
doc output;
|
|
for (var i = 0; i < tape::size; i=i+1) {
|
|
printf("%i", tape.get(i));
|
|
}
|
|
printf("\t%i\n", state);
|
|
for (var i = 0; i < tapepointer; i=i+1) {
|
|
printf(" ");
|
|
}
|
|
printf("^\n");
|
|
|
|
doc the value of the current cell;
|
|
var tapeval = tape.get(tapepointer);
|
|
|
|
doc the current state;
|
|
var command = rules.getRule(state, tapeval);
|
|
|
|
tape.set(tapepointer, command::tape);
|
|
tapepointer = tapepointer + command::move;
|
|
state = command::next;
|
|
}
|
|
|
|
doc output;
|
|
for (var i = 0; i < tape::size; i=i+1) {
|
|
printf("%i", tape.get(i));
|
|
}
|
|
printf("\t%i\n", state);
|
|
for (var i = 0; i < tapepointer; i=i+1) {
|
|
printf(" ");
|
|
}
|
|
printf("^\n");
|
|
]
|
|
|
|
@Integer main [
|
|
|
|
doc incrementer;
|
|
|
|
doc 2 states, 2 symbols;
|
|
|
|
var rules = new @Rules.init(2, 2);
|
|
|
|
doc q0, 1 -> 1, right, q0;
|
|
doc q0, B -> 1, stay, qf;
|
|
|
|
rules.setRule(0, 1, new @Command.init(1, 1, 0));
|
|
rules.setRule(0, 0, new @Command.init(1, 0, 1));
|
|
|
|
doc tape = [1, 1, 1];
|
|
|
|
var tape = new @Array<@Integer>..1..1..1;
|
|
|
|
doc start turing machine;
|
|
|
|
emulateTuring(rules, 0, 1, tape, 0);
|
|
|
|
doc ---------------------------------------------------;
|
|
|
|
doc three state busy beaver;
|
|
|
|
doc 4 states, 2 symbols;
|
|
|
|
rules = new @Rules.init(4, 2);
|
|
|
|
doc a, 0 -> 1, right, b
|
|
a, 1 -> 1, left, c
|
|
b, 0 -> 1, left, a
|
|
b, 1 -> 1, right, b
|
|
c, 0 -> 1, left, b
|
|
c, 1 -> 1, stay, halt
|
|
;
|
|
|
|
doc a = 0,
|
|
b = 1,
|
|
c = 2,
|
|
halt = 3;
|
|
|
|
rules.setRule(0, 0, new @Command.init(1, 1, 1));
|
|
rules.setRule(0, 1, new @Command.init(1, 0-1, 2));
|
|
rules.setRule(1, 0, new @Command.init(1, 0-1, 0));
|
|
rules.setRule(1, 1, new @Command.init(1, 1, 1));
|
|
rules.setRule(2, 0, new @Command.init(1, 0-1, 1));
|
|
rules.setRule(2, 1, new @Command.init(1, 0, 3));
|
|
|
|
doc tape = [];
|
|
|
|
tape = new @Array<@Integer>;
|
|
|
|
doc start turing machine;
|
|
|
|
emulateTuring(rules, 0, 3, tape, 0);
|
|
return 0;
|
|
]
|