mirror of
https://github.com/kennethreitz/elizagen.org.git
synced 2026-06-05 23:00:16 +00:00
jeffshrager
101 lines
2.8 KiB
Plaintext
101 lines
2.8 KiB
Plaintext
; "II. As a slightly more difficult example we can construct a machine
|
|
; to compute the sequence 001011011101111011111... ."
|
|
; Turing's Example II, On Computable Numbers, Nov. 12, 1936, page 234
|
|
|
|
|
|
(TYPE EX2)
|
|
|
|
(EX2
|
|
((0)
|
|
(PRE (E E * O * _ O) (=QO))))
|
|
|
|
|
|
; Q=current state
|
|
; R=read this symbol at head
|
|
; W=write this symbol at head (blank means don't write anything)
|
|
; M=move head left (L) or right (R), or blank for don't move head
|
|
; Q'=new state
|
|
;
|
|
; In state Q, when the symbol at the head is R, then write W, move M
|
|
; and set the new state to Q'
|
|
|
|
; Q R W M Q'
|
|
(QO
|
|
((* 0) (PRE (_ * 2) (=QO)))
|
|
((0 *) (PRE (1 * _) (=QO)))
|
|
((0 1 * O * 1 0) (=QQ)) ; QO O QQ
|
|
((0 1 * I * 1 0) (PRE (1 2 I * 6 * 7) (=QO1)))) ; QO I R QO1
|
|
|
|
(QO1
|
|
((* 0) (PRE (_ * 2) (=QO1)))
|
|
((0 *) (PRE (1 * _) (=QO1)))
|
|
((0 1 * 1 * 1 0) (PRE (1 * 2 * X 6 7) (=QO2)))) ; QO1 ? X L QO2
|
|
|
|
(QO2
|
|
((* 0) (PRE (_ * 2) (=QO2)))
|
|
((0 *) (PRE (1 * _) (=QO2)))
|
|
((0 1 * 1 * 1 0) (PRE (1 * 2 * 4 6 7) (=QO3)))) ; QO2 ? L QO3
|
|
|
|
(QO3
|
|
((* 0) (PRE (_ * 2) (=QO3)))
|
|
((0 *) (PRE (1 * _) (=QO3)))
|
|
((0 1 * 1 * 1 0) (PRE (1 * 2 * 4 6 7) (=QO)))) ; QO3 ? L QO
|
|
|
|
|
|
(QQ
|
|
((* 0) (PRE (_ * 2) (=QQ)))
|
|
((0 *) (PRE (1 * _) (=QQ)))
|
|
((0 1 * _ * 1 0) (PRE (1 * 2 * I 6 7) (=QP))) ; QQ _ I L QP
|
|
((0 1 * 1 * 1 0) (PRE (1 2 4 * 6 * 7) (=QQ1)))) ; QQ ? R QQ1
|
|
|
|
(QQ1
|
|
((* 0) (PRE (_ * 2) (=QQ1)))
|
|
((0 *) (PRE (1 * _) (=QQ1)))
|
|
((0 1 * 1 * 1 0) (PRE (1 2 4 * 6 * 7) (=QQ)))) ; QQ1 ? R QQ
|
|
|
|
|
|
(QP
|
|
((* 0) (PRE (_ * 2) (=QP)))
|
|
((0 *) (PRE (1 * _) (=QP)))
|
|
((0 1 * X * 1 0) (PRE (1 2 _ * 6 * 7) (=QQ))) ; QP X _ R QQ
|
|
((0 1 * E * 1 0) (PRE (1 2 E * 6 * 7) (=QF))) ; QP E _ R QF
|
|
((0 1 * _ * 1 0) (PRE (1 * 2 * _ 6 7) (=QP1)))) ; QP _ L QP1
|
|
|
|
(QP1
|
|
((* 0) (PRE (_ * 2) (=QP1)))
|
|
((0 *) (PRE (1 * _) (=QP1)))
|
|
((0 1 * 1 * 1 0) (PRE (1 * 2 * 4 6 7) (=QP)))) ; QP1 ? L QP
|
|
|
|
|
|
(QF
|
|
((* 0) (PRE (_ * 2) (=QF)))
|
|
((0 *) (PRE (1 * _) (=QF)))
|
|
((0 1 * _ * 1 0) (PRE (1 * 2 * O 6 7) (=QF1))) ; QF _ O L QF1
|
|
((0 1 * 1 * 1 0) (PRE (1 2 4 * 6 * 7) (=QF2)))) ; QF ? R QF2
|
|
|
|
(QF1
|
|
((* 0) (PRE (_ * 2) (=QF1)))
|
|
((0 *) (PRE (1 * _) (=QF1)))
|
|
((0 1 * 1 * 1 0) (PRE (1 * 2 * 4 6 7) (=QO)))) ; QP1 ? L QO
|
|
|
|
(QF2
|
|
((* 0) (PRE (_ * 2) (=QF2)))
|
|
((0 *) (PRE (1 * _) (=QF2)))
|
|
((0 1 * 1 * 1 0) (PRE (1 2 4 * 6 * 7) (=QF)))) ; QF2 ? R QF
|
|
|
|
|
|
|
|
(NONE
|
|
((0)
|
|
(TRY TYPING EX2)))
|
|
|
|
(TURING
|
|
((0)
|
|
(MACHINE)))
|
|
|
|
(MEMORY TURING
|
|
(0 = TURING MACHINE)
|
|
(0 = TURING MACHINE)
|
|
(0 = TURING MACHINE)
|
|
(0 = TURING MACHINE))
|