diff options
Diffstat (limited to 'fib/tm/fib.txt')
-rw-r--r-- | fib/tm/fib.txt | 144 |
1 files changed, 144 insertions, 0 deletions
diff --git a/fib/tm/fib.txt b/fib/tm/fib.txt new file mode 100644 index 0000000..402db15 --- /dev/null +++ b/fib/tm/fib.txt @@ -0,0 +1,144 @@ +The following is a low-level description of a Turing machine that will write +the Fibonacci sequence (represented in binary, separated by $) without halting. + +A Turing machine is a 7-tuple T = (Q,Σ,Γ,δ,qI,qA,qR) where: +- Q is the set of states; non-empty and finite +- Σ is the input alphabet; non-empty and finite +- Γ is the tape alphabet; non-empty and finite +- δ is the transition function: δ(Q, Γ) -> (Q, Γ, {L, R}) +- qI ∈ Q is the initial state +- qA ∈ Q is the accept state +- qR ∈ Q is the reject state + +- Q: { + ca, cb, cc, cd, ce, cf, cg, ch, ci, + sa, sb, sc, sd, + aa, ab, ac, + aaa, aab, aac, aad, aae, aaf, + aba, abb, abc, abd, abe, abf, + ba, bb, bc, + baa, bab, bac, bad, bae, baf, + bba, bbb, bbc, bbd, bbe, bbf, + za, zb, zc, zd +} +- Σ: not relevant as we entirely disregard the input to begin with. +- Γ: {_, $, X, 0, 1, 0*, 1*} (_ means the blank symbol) +- δ: described below. a note on syntax: + - no entry in the output parameter means do not write a character to the tape. + - similarly, no entry in the position parameter means do not move the tape head. + - numerous "possible" transition functions are not stated. those are thought by the author to be inaccessible in normal operation of this machine (and if they are, it is probably a bug). +- qI: the initial state is ca. +- qA: the machine does not accept. +- qR: the machine does not reject. + +δ(ca, Γ) -> (cb, $, R) +δ(cb, Γ) -> (cc, 0, R) +δ(cc, Γ) -> (cd, $, R) +δ(cd, Γ) -> (ce, 1*, R) +δ(ce, Γ) -> (cf, $, R) +δ(cf, Γ) -> (cg, 1, R) +δ(cg, Γ) -> (ch, $, R) +δ(ch, Γ \ _) -> (ci, _, R) +δ(ch, _) -> (sa, , ) + +δ(sa, {_,X}) -> (sa, , L) +δ(sa, $) -> (sb, , L) +δ(sb, {0*,1*}) -> (sb, , L) +δ(sb, 0) -> (sc, 0*, R) +δ(sb, 1) -> (sc, 1*, R) +δ(sb, $) -> (sd, , R) +δ(sc, Γ \ _) -> (sc, , R) +δ(sc, _) -> (sa, X, L) +δ(sd, {$,X}) -> (sd, , R) +δ(sd, 0*) -> (sd, 0, R) +δ(sd, 1*) -> (sd, 1, R) +δ(sd, _) -> (aa, , L) + +δ(aa, {X,0,1}) -> (aa, , L) +δ(aa, $) -> (ab, , L) +δ(ab, {0*,1*}) -> (ab, , L) +δ(ab, 0) -> (aaa, 0*, L) +δ(ab, 1) -> (aba, 1*, L) +δ(ab, $) -> (ac, , R) +δ(ac, Γ \ _) -> (ac, , R) +δ(ac, _) -> (sa, $, R) + +δ(aaa, {0,1}) -> (aaa, , L) +δ(aaa, $) -> (aab, , L) +δ(aab, 0*) -> (aac, 0, R) +δ(aac, Γ \ _) -> (aac, , R) +δ(aac, _) -> (aad, , L) +δ(aad, {0,1}) -> (aad, , L) +δ(aad, X) -> (aa, 0, L) +δ(aab, 1*) -> (aae, 1, R) +δ(aae, Γ \ _) -> (aae, , R) +δ(aae, _) -> (aaf, , L) +δ(aaf, {0,1}) -> (aaf, , L) +δ(aaf, X) -> (aa, 1, L) +δ(aab, {0,1}) -> (aab, , L) + +δ(aba, {0,1}) -> (aba, , L) +δ(aba, $) -> (abb, , L) +δ(abb, 0*) -> (abc, 0, R) +δ(abc, Γ \ _) -> (abc, , R) +δ(abc, _) -> (abd, , L) +δ(abd, {0,1}) -> (abd, , L) +δ(abd, X) -> (aa, 1, L) +δ(abb, 1*) -> (abe, 1, R) +δ(abe, Γ \ _) -> (abe, , R) +δ(abe, _) -> (abf, , L) +δ(abf, {0,1}) -> (abf, , L) +δ(abf, X) -> (ba, 0, L) +δ(abb, $) -> (abc, , R) +δ(abb, {0,1}) -> (abb, , L) + +δ(ba, {X,0,1}) -> (ba, , L) +δ(ba, $) -> (bb, , L) +δ(bb, {0*,1*}) -> (bb, , L) +δ(bb, 0) -> (baa, 0*, L) +δ(bb, 1) -> (bba, 1*, L) +δ(bb, $) -> (bc, , R) +δ(bc, Γ \ _) -> (bc, , R) +δ(bc, _) -> (za, , L) + +δ(baa, {0,1}) -> (baa, , L) +δ(baa, $) -> (bab, , L) +δ(bab, 0*) -> (bac, 0, R) +δ(bac, Γ \ _) -> (bac, , R) +δ(bac, _) -> (bad, , L) +δ(bad, {0,1}) -> (bad, , L) +δ(bad, X) -> (aa, 1, L) +δ(bab, 1*) -> (bae, 1, R) +δ(bae, Γ \ _) -> (bae, , R) +δ(bae, _) -> (baf, , L) +δ(baf, {0,1}) -> (baf, , L) +δ(baf, X) -> (ba, 0, L) +δ(bab, {0,1}) -> (bab, , L) + +δ(bba, {0,1}) -> (bba, , L) +δ(bba, $) -> (bbb, , L) +δ(bbb, 0*) -> (bbc, 0, R) +δ(bbc, Γ \ _) -> (bbc, , R) +δ(bbc, _) -> (bbd, , L) +δ(bbd, {0,1}) -> (bbd, , L) +δ(bbd, X) -> (ba, 0, L) +δ(bbb, 1*) -> (bbe, 1, R) +δ(bbe, Γ \ _) -> (bbe, , R) +δ(bbe, _) -> (bbf, , L) +δ(bbf, {0,1}) -> (bbf, , L) +δ(bbf, X) -> (ba, 1, L) +δ(bbb, $) -> (bbc, , R) +δ(bbb, {0,1}) -> (bbb, , L) + +δ(za, {0,1}) -> (za, , L) +δ(za, $) -> (zb, , R) + +δ(zb, 0) -> (zc, 1, R) +δ(zb, 1) -> (zb, 1, R) +δ(zb, _) -> (zd, 1, R) + +δ(zc, 0) -> (zc, 0, R) +δ(zc, 1) -> (zb, 0, R) +δ(zc, _) -> (zd, 0, R) + +δ(zd, _) -> (sa, $, R) |