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

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

Інші можливі переклади: яма Тюрінга, смоляний колодязь Тюрінга. Дослівно: смоляна яма Тюрінга (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).