Тюрінгівська трясовина

Тюрінгівська трясовина — жаргонна загальна назва для мов програмування, які Тюрінг-повні, але мають украй примітивний синтаксис і семантику. Вони незручні для практичного програмування (через складність написання програм і низьку продуктивність), зате добре підходять для деяких інших завдань (доказ необчислюваності деяких функцій, ілюстрація базових принципів програмування і т. д.). Тому вони цікаві для інформатики. Багато езотеричних мов програмування також є «трясовинами Тюрінга». Проте зважаючи на простоту побудови і реалізації зручні для автоматичної генерації коду.

Інші можливі переклади: яма Тюрінга, смоляний колодязь Тюрінга. Дослівно: смоляна яма Тюрінга (Turing tar-pit).

54. Остерігайтеся трясовин Тюрінга, в яких можна зробити все, але нічого цікавого не можна зробити просто.
— Alan Perlis, "Epigrams on Programming" // SIGPLAN Notices. - Vol. 17, No. 9, September 1982. – Р. 7-13(англ.).

Приклади

Комбінаторна логіка, особливо бінарна комбінаторна логіка
INTERCAL
Лямбда-числення, що не типізується
OISC (машина, набір інструкцій якої містить лише одну команду ніби «відняти і перейти, якщо результат менше нуля»).
Машина Тюрінга
Unlambda
MISC — Minimal Instruction Set Computing, мікропроцесори з мінімальним набором команд

Існує дві тенденції розробки «трясовин Тюрінга»: скорочення числа інструкцій і скорочення числа символів. Результати:

Бінарна комбінаторна логіка: 2 правила переписування термів, 2 символи
Brainfuck: 8 інструкцій, 8 символів
Iota and Jot: 2 операції, 2 символи
OISC: 1 інструкція, 3 символи (signed unary with a separator)
Thue: 1 інструкція, 128+ символів

Література

G. Fischer, A.C. Lemke, «Constrained Design Processes: Steps Toward Convivial Computing», Technical Report CU-CS-369-87, Colorado University, USA.
E.L. Hutchins, J.D. Hollan, D.A. Norman, «Direct Manipulation Interfaces». In User Centered System Design. New Perspectives on Human–Computer Interaction (1986).