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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

54. Остерігайтеся трясовин Тюрінга, в яких можна зробити все, але нічого цікавого не можна зробити просто.

Alan Perlis, "Epigrams on Programming" // SIGPLAN Notices. - Vol. 17, No. 9, September 1982. – Р. 7-13(англ.).

Приклади

[ред. | ред. код]

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

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

Література

[ред. | ред. код]

Примітки

[ред. | ред. код]