Тьюринг-полнота

Материал из Викиконспекты
Версия от 01:31, 7 января 2017; Romanosov (обсуждение | вклад) (Новая страница: «. ===Критерии Тьюринг-полноты=== ===Тьюринг-полнота некоторых языков программирования=== ==...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

.


Критерии Тьюринг-полноты

Тьюринг-полнота некоторых языков программирования

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

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

Тезис Чёрча-Тьюринга

См. также

Источники информации