factorial.tm

;; Turing Machine that calculates the Factorial of a number in  unary notation.

Initial     = II
Blank       = .

Rules =

(IN x x -> IN)
(IN 1 1 -> IN)
(IN . # <- B)

(B 1 1 <- B)
(B x x <- B)
(B . . -> Q)

(Q 1 . -> A)
(Q x x >< CI)

(A 1 1 -> A)
(A x x -> C)

(C . . -> C)
(C # # <- FILL)
(C 1 . -> F)

(FILL . 1 <- FILL)
(FILL x x <- B)

(F 1 1 -> F)
(F # # -> P)

(P 1 1 -> P)
(P . 1 <- BF)

(BF . . <- BF)
(BF 1 1 <- BF)
(BF # # <- BF)
(BF x x -> C)

(CI x . -> Cx)

(Cx # # -> Cx)
(Cx 1 1 -> Cx)
(Cx . x <- CB)

(CB 1 1 <- CB)
(CB # # <- CB)
(CB x x <- CB)
(CB . . -> Ca)

(Ca # . -> C#)
(Ca 1 . -> C1)

(C1 # # -> C1)
(C1 x x -> C1)
(C1 1 1 -> C1)
(C1 . 1 <- CB)

(C# 1 1 -> C#)
(C# x x -> C#)
(C# . . <- Cm)

(Cm 1 . <- Cr)

(Cr 1 1 <- Cr)
(Cr x x <- Cr)
(Cr . . -> EI)

(EI 1 1 -> EI)
(EI x x -> EN)

(EN . . <- Ea)
(EN 1 1 <- EB)

(EB x x <- EB)
(EB 1 1 <- EB)
(EB . . -> IN)

(Ea x . <- FIa)

(II 1 1 -> II)
(II . x <- IB)

(IB 1 1 <- IB)
(IB . . -> IC)

(IC 1 _ -> I1)

(I1 1 1 -> I1)
(I1 x x -> I1)
(I1 . 1 <- IB')

(IB' 1 1 <- IB')
(IB' x x <- IB')
(IB' _ _ -> I?)

(I? x x <- I_)
(I? 1 _ -> I1)

(I_ _ 1 <- I_)
(I_ . . -> IM)

(IM 1 1 -> IM)
(IM x x -> IM)
(IM . . <- IM')

(IM' 1 . <- IB'')

(IB'' 1 1 <- IB'')
(IB'' x x <- IB'')
(IB'' . . -> IN)

(FIa 1 1 <- FIa)
(FIa . . -> FI)