Тьюринг-полнота — различия между версиями
Romanosov (обсуждение | вклад) (Новая страница: «. ===Критерии Тьюринг-полноты=== ===Тьюринг-полнота некоторых языков программирования=== ==...») |
Romanosov (обсуждение | вклад) м (→Тьюринг-полнота некоторых языков программирования) |
||
| Строка 5: | Строка 5: | ||
===Тьюринг-полнота некоторых языков программирования=== | ===Тьюринг-полнота некоторых языков программирования=== | ||
| + | |||
| + | Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке. | ||
===Тьюринговская трясина=== | ===Тьюринговская трясина=== | ||
Версия 17:06, 7 января 2017
.
Содержание
Критерии Тьюринг-полноты
Тьюринг-полнота некоторых языков программирования
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.
Тьюринговская трясина
Тьюринговская трясина — жаргонное общее название для языков программирования, которые Тьюринг-полны, но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования (из-за трудности написания программ и низкой производительности), зато хорошо подходят для некоторых других задач (доказательство невычислимости некоторых функций, иллюстрация базовых принципов программирования и т. д.). Поэтому они интересны для информатики. Многие эзотерические языки программирования также являются «трясинами Тьюринга».
