403
правки
Изменения
ололо
На основе этого всего уже можно реализовать эмулятор машины тьюринга: с помощью пар, списков чисел можно хранить состояния. С помощью рекурсии можно обрабатывать переходы. Входная строка будет даваться, например, закодированной аналогично списку: пара из длины и числа, характеризующего список степенями простых. Я бы продолжил это писать, но уже на операции <tex>\operatorname{head} [1, 2]</tex> я не дождался окончания выполнения. Скорость лямбда-исчисления как вычислителя печальна.
===Примеры (слабонервным не смотреть)===
====fact====
(\f.(\x.f (x x)) (\x.f (x x))) (\f.\x.(\p.\t.\e.p t e) ((\n.n (\c.\a.\b.b) (\a.\b.a)) (x)) (\s.\z.s z) ((\n.\m.\s.n (m s)) (x) (f ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (x)))))
====head====
\list.(\f.(\x.f (x x)) (\x.f (x x))) (\f.\n.\m.(\p.\t.\e.p t e) ((\n.n (\c.\a.\b.b) (\a.\b.a)) ((\f.(\x.f (x x)) (\x.f (x x))) (\mod.\n.\m.(\p.\t.\e.p t e) ((\n.\m.(\n.\m.(\n.n (\c.\a.\b.b) (\a.\b.a)) ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m)) (n) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (m))) (n) m) n (mod ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m) m)) n m)) ((\n.\s.\z.s (n s z)) (f ((\f.(\x.f (x x)) (\x.f (x x))) (\div.\n.\m.(\p.\t.\e.p t e) ((\n.\m.(\n.\m.(\n.n (\c.\a.\b.b) (\a.\b.a)) ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m)) (n) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (m))) (n) m) (\s.\z.z) ((\n.\s.\z.s (n s z)) (div ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m) m))) n m) m)) (\s.\z.z)) ((\p.p (\a.\b.b)) (list)) ((\i.(\f.(\x.f (x x)) (\x.f (x x))) (\f.\p.\i.(\p.\t.\e.p t e) ((\n.n (\c.\a.\b.b) (\a.\b.a)) (i)) p (f ((\p.(\f.(\x.f (x x)) (\x.f (x x))) (\f.\p.(\p.\t.\e.p t e) ((\p.(\f.(\x.f (x x)) (\x.f (x x))) (\f.\p.\i.(\p.\t.\e.p t e) ((\n.\m.(\n.n (\c.\a.\b.b) (\a.\b.a)) ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m)) (p) i) (\a.\b.a) ((\p.\t.\e.p t e) ((\n.n (\c.\a.\b.b) (\a.\b.a)) ((\f.(\x.f (x x)) (\x.f (x x))) (\mod.\n.\m.(\p.\t.\e.p t e) ((\n.\m.(\n.\m.(\n.n (\c.\a.\b.b) (\a.\b.a)) ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m)) (n) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (m))) (n) m) n (mod ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m) m)) p i)) (\a.\b.b) (f p ((\n.\s.\z.s (n s z)) (i))))) p (\s.\z.s (s z))) (p)) p (f ((\n.\s.\z.s (n s z)) (p)))) ((\n.\s.\z.s (n s z)) (p))) (p)) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (i)))) (\s.\z.s (s z)) i) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) ((\p.p (\a.\b.a)) (list))))
====tail====
\list.(\a.\b.\t.t a b) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) ((\p.p (\a.\b.a)) (list))) ((\f.(\x.f (x x)) (\x.f (x x))) (\f.\n.\m.(\p.\t.\e.p t e) ((\n.n (\c.\a.\b.b) (\a.\b.a)) ((\f.(\x.f (x x)) (\x.f (x x))) (\mod.\n.\m.(\p.\t.\e.p t e) ((\n.\m.(\n.\m.(\n.n (\c.\a.\b.b) (\a.\b.a)) ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m)) (n) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (m))) (n) m) n (mod ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m) m)) n m)) (f ((\f.(\x.f (x x)) (\x.f (x x))) (\div.\n.\m.(\p.\t.\e.p t e) ((\n.\m.(\n.\m.(\n.n (\c.\a.\b.b) (\a.\b.a)) ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m)) (n) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (m))) (n) m) (\s.\z.z) ((\n.\s.\z.s (n s z)) (div ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m) m))) n m) m) n) ((\p.p (\a.\b.b)) (list)) ((\i.(\f.(\x.f (x x)) (\x.f (x x))) (\f.\p.\i.(\p.\t.\e.p t e) ((\n.n (\c.\a.\b.b) (\a.\b.a)) (i)) p (f ((\p.(\f.(\x.f (x x)) (\x.f (x x))) (\f.\p.(\p.\t.\e.p t e) ((\p.(\f.(\x.f (x x)) (\x.f (x x))) (\f.\p.\i.(\p.\t.\e.p t e) ((\n.\m.(\n.n (\c.\a.\b.b) (\a.\b.a)) ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m)) (p) i) (\a.\b.a) ((\p.\t.\e.p t e) ((\n.n (\c.\a.\b.b) (\a.\b.a)) ((\f.(\x.f (x x)) (\x.f (x x))) (\mod.\n.\m.(\p.\t.\e.p t e) ((\n.\m.(\n.\m.(\n.n (\c.\a.\b.b) (\a.\b.a)) ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m)) (n) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (m))) (n) m) n (mod ((\n.\m.m (\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) n) (n) m) m)) p i)) (\a.\b.b) (f p ((\n.\s.\z.s (n s z)) (i))))) p (\s.\z.s (s z))) (p)) p (f ((\n.\s.\z.s (n s z)) (p)))) ((\n.\s.\z.s (n s z)) (p))) (p)) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) (i)))) (\s.\z.s (s z)) i) ((\n.\s.\z.(\p.p (\a.\b.b)) (n (\p.(\a.\b.\t.t a b) (s ((\p.p (\a.\b.a)) (p))) ((\p.p (\a.\b.a)) (p))) ((\a.\b.\t.t a b) (z) z))) ((\p.p (\a.\b.a)) (list)))))
==Ссылки==
[http://rain.ifmo.ru/~komarov/Turing.lhs Тут можно это всё потыкать]
