Anonymous user
Universal Turing machine: Difference between revisions
D entry: added third TM, changed output formatting a little
(→{{header|D}}: added third test; some small changes) |
(D entry: added third TM, changed output formatting a little) |
||
Line 303:
This is typed less strongly than the Ada entry. The constructor of UTM contains many run-time tests that in a strongly static typed version are (implicitly) done at compile-time.
<lang d>import std.stdio, std.algorithm, std.string, std.conv, std.array,
std.exception;
struct UTM {
Line 329:
static struct TapeHead {
const Symbol[] symbols;
immutable Symbol blank;
Symbol[] tape;
Line 334 ⟶ 335:
this(in ref TuringMachine t) pure /*nothrow*/ {
this.symbols = t.symbols;
this.blank = t.blank;
this.tape = t.input.dup; // Not nothrow.
Line 365 ⟶ 367:
else
this.position--;
}
void stay() const pure nothrow {
// Do nothing.
}
Line 371 ⟶ 377:
case Direction.left: left(); break;
case Direction.right: right(); break;
case Direction.stay:
}
}
string toString() const {
return format("...%(%)...", this.tape)
~ '\n'
~ format("%" ~ text(this.position +
~ '\n';
}
Line 384 ⟶ 390:
this(const ref TuringMachine tm_) {
immutable 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);
const allStates = tm_.runningStates ~ tm_.haltStates;
foreach (const s; tm_.rules.keys.to!(dchar[])().sort())
enforce(tm_.runningStates.canFind(s), errMsg);
foreach (const aa; tm_.rules.byValue)
foreach (/*const*/ s, const rule; aa) {
enforce(tm_.symbols.canFind(s), errMsg);
enforce(tm_.symbols.canFind(rule.toWrite), errMsg);
enforce(allStates.canFind(rule.nextState), errMsg);
}
this.tm = tm_;
this.head = TapeHead(this.tm);
Line 393 ⟶ 416:
if (!tm.runningStates.canFind(state))
throw new Exception("Unknown state.");
this.head.write(rule.toWrite);
this.head.move(rule.direction);
Line 405 ⟶ 428:
void main() {
with (UTM) {
alias R = Rule;
writeln("Incrementer:");
TuringMachine tm1;
Line 413 ⟶ 437:
tm1.runningStates = ['A'];
with (Direction)
tm1.rules = ['A': [0:
1:
tm1.input = [1, 1, 1];
UTM(tm1);
Line 425 ⟶ 449:
tm2.initialState = 'A';
tm2.haltStates = ['H'];
tm2.runningStates = ['A', 'B', 'C'];
with (Direction)
tm2.rules = ['A': [0:
1:
'B': [0:
1:
'C': [0:
1:
UTM(tm2);
writeln("\nSorting stress test (12212212121212):");
TuringMachine tm3;
Line 443 ⟶ 467:
tm3.runningStates = ['A', 'B', 'C', 'D', 'E'];
with (Direction)
tm3.rules = ['A'
'B'
'C'
'D'
'E'
tm3.input = [1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 1,
UTM(tm3
}
}</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...
^
Sorting stress test (12212212121212):
...12212212121212...
^
...12212212121212...
^
[...]
^
...0111111222222220...
^
...0111111222222220...
^</pre>
=={{header|Erlang}}==
| |||