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