codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
import std.stdio, std.algorithm, std.conv, std.range, std.typecons, std.string, std.array; struct UTM { enum : char {right, left, stay} private TapeHead head; private const TuringMachine tm; static struct TuringMachine { char[] symbols; char blank; char initialState; char[] haltStates, runningStates; char[][string] rules; char[] input; } static struct TapeHead { const char[] symbols; const char blank; char[] tape; size_t index; this(in ref TuringMachine t) { this.symbols = t.symbols; this.blank = t.blank; this.tape = t.input.dup; if (tape.empty) tape = [blank]; this.index = 0; } auto read() const pure nothrow { return this.tape[this.index]; } void write(in char symbol) { .write(this); this.tape[this.index] = symbol; } void right() pure nothrow { this.index++; if (index == tape.length) tape ~= blank; } void left() pure nothrow { if (this.index == 0) this.tape = this.blank ~ this.tape; else this.index--; } void stay() const pure nothrow { // Do nothing. } void move(in char dir) { switch (dir) { case UTM.left: left(); break; case UTM.right: right(); break; case UTM.stay: stay(); break; default: assert(0); } } string toString() const { return text(tape) ~ '\n' ~ format("%" ~ text(index + 1) ~ "s", "^") ~ '\n'; } } this(const ref TuringMachine tm_) { this.tm = tm_; this.head = TapeHead(this.tm); char 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[0]); this.head.move(rule[1]); state = rule[2]; } } } void main() { writeln("Incrementer:"); immutable UTM.TuringMachine tm1 = { symbols: ['0', '1'], blank: '0', initialState: 'A', haltStates: ['H'], runningStates: ['A'], rules: ["A1": ['1', UTM.right, 'A'], "A0": ['1', UTM.left, 'H']], input: ['1', '1', '1'] }; UTM(tm1); writeln("\nBusy beaver machine:"); immutable UTM.TuringMachine tm2 = { symbols: ['0', '1'], blank: '0', initialState: 'A', haltStates: ['H'], runningStates: ['A', 'B', 'C'], rules: ["A0": ['1', UTM.right, 'B'], "A1": ['1', UTM.left, 'C'], "B0": ['1', UTM.left, 'A'], "B1": ['1', UTM.right, 'B'], "C0": ['1', UTM.left, 'B'], "C1": ['1', UTM.stay, 'H']] }; UTM(tm2); }
Private
[
?
]
Run code
Submit