Тьюринговская трясина — жаргонное общее название для языков программирования , которые Тьюринг-полны , но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования (из-за трудности написания программ и низкой производительности), зато хорошо подходят для некоторых других задач (доказательство невычислимости некоторых функций, иллюстрация базовых принципов программирования и т. д.). Поэтому они интересны для информатики . Многие эзотерические языки программирования также являются «трясинами Тьюринга».

Однако ввиду простоты построения и реализации удобны для автоматической генерации кода .

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

54. Остерегайтесь трясин Тьюринга, в которых можно сделать всё, но ничего интересного нельзя сделать просто.

— .

Примеры

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

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

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

Ссылки

Для улучшения этой статьи желательно : Проставить сноски , внести более точные указания на источники. Найти и оформить в виде сносок ссылки на независимые авторитетные источники , подтверждающие написанное . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.