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

.

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

Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.

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

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

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

• Cunningham & Cunningham, Inc. — Turing Complete

• Stackexchange — What makes a language Turing-complete?

• Википедия — Тьюринговская трясина

• Википедия — Полнота по Тьюрингу

• А. А. Вылиток. Об алгоритмической полноте некоторых языков программирования