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

В теории вычислений, информатике или другой логической системе «машина» называется Тьюринг-полной, если она вычислительно эквивалентна универсальной машине Тьюринга. Другими словами, эта «машина» и универсальная машина Тьюринга могут эмулировать работу друг друга. Термин назван в честь Алана Тьюринга, который придумал универсальную машину.

Примеры

Любой широко используемый язык программирования — Тьюринг-полный. Это касается как императивных языков, таких как C, так и объектных (напр., Java). Языки, разработанные для менее общих целей, включая функциональные языки как Lisp и Haskell, логического программирования как Prolog, тоже Тьюринг-полны.

Cложно найти пример Тьюринг-неполных языков, т. к. эти языки очень ограничены (хотя, можно посмотреть машины, которые всегда останавливаются).

Полными по Тьюрингу бывают также некоторые грамматики, не являющиеся языками программирования (например, конфигурационный файл sendmail).

Библиография

  • Brainerd, W.S., Landweber, L.H. Theory of Computation. — Wiley, 1974.

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home