Полнота по Тьюрингу
В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Название пошло от имени Алана Тьюринга, который придумал абстрактный вычислитель — машину Тьюринга и дал определение множества функций, вычислимых посредством машин Тьюринга.
Примеры
Большинство широко используемых языков программирования — тьюринг-полные. Это касается как императивных языков, таких как Паскаль, так и функциональных (Haskell) и языков логического программирования (Prolog). Некоторые языки программирования (Haskell, C++) обладают тьюринг-полнотой времени компиляции.
Полны по Тьюрингу нормальный алгоритм Маркова, 2-теговая система, клеточный автомат с правилом 110, ингибиторная сеть Петри. Полными по Тьюрингу являются также неограниченные грамматики.
Примерами неполных по Тьюрингу формализмов являются конечные автоматы, примитивно рекурсивные функции, контекстно-свободные и регулярные грамматики.
Универсальная система
В каждом Тьюринг-полном классе вычислителей существует универсальный представитель класса, имитирующий выполнение произвольного заданного представителя класса. Так, например, универсальная машина Тьюринга по ленте, содержащей шифр произвольной заданной машины Тьюринга М и её входной цепочки В, имитирует выполнение М над В. В настоящее время построены универсальные машины Тьюринга, содержащие менее 23 инструкций[1] для комбинаций числа состояний-символов 4х6, 5х5. Универсальная ингибиторная сеть Петри содержит 56 вершин.[2]
Библиография
- Brainerd, W.S., Landweber, L.H. Theory of Computation. — Wiley, 1974.
См. также
Напишите отзыв о статье "Полнота по Тьюрингу"
Ссылки
- [c2.com/cgi/wiki?TuringComplete c2.com]
Примечания
- ↑ [www.ini.uzh.ch/~tneary/ T. Neary] and D. Woods. [www.ini.uzh.ch/~tneary/NearyWoods_FI2009.pdf Four small universal Turing machines. Fundamenta Informaticae, 91(1):123-144, 2009.]
- ↑ [daze.ho.ua Zaitsev D.A.] [dx.doi.org/10.1109/TSMC.2012.2237549 Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1- 12.]
|
Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её. |
Отрывок, характеризующий Полнота по Тьюрингу
Наполеон вздернул плечами и, ничего не ответив, продолжал свою прогулку. Бельяр громко и оживленно стал говорить с генералами свиты, окружившими его.– Вы очень пылки, Бельяр, – сказал Наполеон, опять подходя к подъехавшему генералу. – Легко ошибиться в пылу огня. Поезжайте и посмотрите, и тогда приезжайте ко мне.
Не успел еще Бельяр скрыться из вида, как с другой стороны прискакал новый посланный с поля сражения.
– Eh bien, qu'est ce qu'il y a? [Ну, что еще?] – сказал Наполеон тоном человека, раздраженного беспрестанными помехами.
– Sire, le prince… [Государь, герцог…] – начал адъютант.
– Просит подкрепления? – с гневным жестом проговорил Наполеон. Адъютант утвердительно наклонил голову и стал докладывать; но император отвернулся от него, сделав два шага, остановился, вернулся назад и подозвал Бертье. – Надо дать резервы, – сказал он, слегка разводя руками. – Кого послать туда, как вы думаете? – обратился он к Бертье, к этому oison que j'ai fait aigle [гусенку, которого я сделал орлом], как он впоследствии называл его.
– Государь, послать дивизию Клапареда? – сказал Бертье, помнивший наизусть все дивизии, полки и батальоны.
Наполеон утвердительно кивнул головой.
Адъютант поскакал к дивизии Клапареда. И чрез несколько минут молодая гвардия, стоявшая позади кургана, тронулась с своего места. Наполеон молча смотрел по этому направлению.
– Нет, – обратился он вдруг к Бертье, – я не могу послать Клапареда. Пошлите дивизию Фриана, – сказал он.
Хотя не было никакого преимущества в том, чтобы вместо Клапареда посылать дивизию Фриана, и даже было очевидное неудобство и замедление в том, чтобы остановить теперь Клапареда и посылать Фриана, но приказание было с точностью исполнено. Наполеон не видел того, что он в отношении своих войск играл роль доктора, который мешает своими лекарствами, – роль, которую он так верно понимал и осуждал.
Дивизия Фриана, так же как и другие, скрылась в дыму поля сражения. С разных сторон продолжали прискакивать адъютанты, и все, как бы сговорившись, говорили одно и то же. Все просили подкреплений, все говорили, что русские держатся на своих местах и производят un feu d'enfer [адский огонь], от которого тает французское войско.
Наполеон сидел в задумчивости на складном стуле.
Проголодавшийся с утра m r de Beausset, любивший путешествовать, подошел к императору и осмелился почтительно предложить его величеству позавтракать.
– Я надеюсь, что теперь уже я могу поздравить ваше величество с победой, – сказал он.
Наполеон молча отрицательно покачал головой. Полагая, что отрицание относится к победе, а не к завтраку, m r de Beausset позволил себе игриво почтительно заметить, что нет в мире причин, которые могли бы помешать завтракать, когда можно это сделать.
