Тьюринг-полнота — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Тьюринг-полнота некоторых языков программирования)
Строка 1: Строка 1:
.
+
Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной.
 +
 
 +
 
 +
 
 +
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
  
  
 
===Критерии Тьюринг-полноты===
 
===Критерии Тьюринг-полноты===
 +
 +
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
 +
 +
* Конечность (нет бесконечных символьных множеств и пр.)
 +
 +
* Фиксированное описание
 +
 +
* Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть "always big enough".
 +
 +
* Неограниченность времени выполнения
 +
 +
* Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
 +
 +
* Циклы while с прерыванием или им эквивалентные
 +
 +
* Возможность останавливать выполнение или каким-то образом подавать сигнал о результатах выполнения
 +
 +
* Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.
 +
 +
* Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным.
  
 
===Тьюринг-полнота некоторых языков программирования===
 
===Тьюринг-полнота некоторых языков программирования===

Версия 17:46, 7 января 2017

Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной.


Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.


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

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

  • Конечность (нет бесконечных символьных множеств и пр.)
  • Фиксированное описание
  • Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть "always big enough".
  • Неограниченность времени выполнения
  • Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
  • Циклы while с прерыванием или им эквивалентные
  • Возможность останавливать выполнение или каким-то образом подавать сигнал о результатах выполнения
  • Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.
  • Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным.

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

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

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

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

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

См. также

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