Anonymous user
Universal Turing machine: Difference between revisions
→{{header|D}}: added D
(→{{header|D}}: added D) |
|||
Line 297:
^
111111 STOP
^</pre>
=={{header|D}}==
<lang d>import std.stdio, std.algorithm, std.string, std.conv, std.array,
std.exception;
struct UTM {
alias Symbol = uint;
alias State = char; // Typedef?
enum Direction { right, left, stay }
private TapeHead head;
private const TuringMachine tm;
static struct Rule {
Symbol toWrite;
Direction direction;
State nextState;
}
static struct TuringMachine {
Symbol[] symbols;
Symbol blank;
State initialState;
State[] haltStates, runningStates;
Rule[Symbol][State] rules;
Symbol[] input;
}
static struct TapeHead {
const Symbol[] symbols;
immutable Symbol blank;
Symbol[] tape;
size_t position;
this(in ref TuringMachine t) pure /*nothrow*/ {
this.symbols = t.symbols;
this.blank = t.blank;
this.tape = t.input.dup; // Not nothrow.
if (this.tape.empty)
this.tape = [this.blank];
this.position = 0;
}
pure nothrow invariant() {
assert(this.position < this.tape.length);
}
Symbol read() const pure nothrow {
return this.tape[this.position];
}
void write(in Symbol symbol) {
.write(this);
this.tape[this.position] = symbol;
}
void right() pure nothrow {
this.position++;
if (this.position == this.tape.length)
this.tape ~= this.blank;
}
void left() pure nothrow {
if (this.position == 0)
this.tape = this.blank ~ this.tape;
else
this.position--;
}
void stay() const pure nothrow {
// Do nothing.
}
void move(in Direction dir) {
final switch (dir) {
case Direction.left: left(); break;
case Direction.right: right(); break;
case Direction.stay: stay(); break;
}
}
string toString() const {
return format("%(%)", this.tape)
~ '\n'
~ format("%" ~ text(this.position + 1) ~ "s", "^")
~ '\n';
}
}
this(const ref TuringMachine tm_) {
auto errmsg = "Invalid input.";
enforce(!tm_.runningStates.empty, errmsg);
enforce(!tm_.haltStates.empty, errmsg);
enforce(!tm_.symbols.empty, errmsg);
enforce(tm_.rules.length, errmsg);
enforce(tm_.runningStates.canFind(tm_.initialState), errmsg);
enforce(tm_.symbols.canFind(tm_.blank), errmsg);
this.tm = tm_;
this.head = TapeHead(this.tm);
State state = this.tm.initialState;
while (true) {
if (tm.haltStates.canFind(state))
break;
if (!tm.runningStates.canFind(state))
throw new Exception("Unknown state.");
auto symbol = this.head.read();
auto rule = this.tm.rules[state][symbol];
this.head.write(rule.toWrite);
this.head.move(rule.direction);
state = rule.nextState;
}
write(head);
}
}
void main() {
with (UTM) {
writeln("Incrementer:");
TuringMachine tm1;
tm1.symbols = [0, 1];
tm1.blank = 0;
tm1.initialState = 'A';
tm1.haltStates = ['H'];
tm1.runningStates = ['A'];
with (Direction)
tm1.rules = ['A': [0: Rule(1, left, 'H'),
1: Rule(1, right, 'A')]];
tm1.input = [1, 1, 1];
UTM(tm1);
// http://en.wikipedia.org/wiki/Busy_beaver
writeln("\nBusy beaver machine (3-state, 2-symbol):");
TuringMachine tm2;
tm2.symbols = [0, 1];
tm2.blank = 0;
tm2.initialState = 'A';
tm2.haltStates = ['H'];
tm2.runningStates = ['A','B', 'C'];
with (Direction)
tm2.rules = ['A': [0: Rule(1, right, 'B'),
1: Rule(1, left, 'C')],
'B': [0: Rule(1, left, 'A'),
1: Rule(1, right, 'B')],
'C': [0: Rule(1, left, 'B'),
1: Rule(1, stay, 'H')]];
UTM(tm2);
}
}</lang>
<pre>Incrementer:
111
^
111
^
111
^
1110
^
1111
^
Busy beaver machine (3-state, 2-symbol):
0
^
10
^
11
^
011
^
0111
^
01111
^
11111
^
11111
^
11111
^
11111
^
111110
^
111111
^
111111
^
111111
^</pre>
| |||