Полнота по Тьюрингу
Материал из Википедии — свободной энциклопедии
В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Название пошло от Алана Тьюринга, который придумал абстрактный вычислитель — машину Тьюринга и дал определение множества функций, вычислимых посредством машин Тьюринга .
Содержание |
[править] Примеры
Большинство широко используемых языков программирования — тьюринг-полные. Это касается как императивных языков, таких как Паскаль, так и функциональных (Haskell) и языков логического программирования (Prolog).
Полными по Тьюрингу являются также грамматики общего вида.
Примерами не полных по Тьюрингу формализмов являются конечные автоматы, примитивно рекурсивные функции, контекстно-свободные и регулярные грамматики.
[править] Библиография
- Brainerd, W.S., Landweber, L.H. Theory of Computation. — Wiley, 1974.
[править] См. также
[править] Ссылки
| Это незавершённая статья по информатике. Вы можете помочь проекту, исправив и дополнив её. |

