04-10-2023
В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Название пошло от Алана Тьюринга, который придумал абстрактный вычислитель — машину Тьюринга и дал определение множества функций, вычислимых посредством машин Тьюринга .
Содержание |
Большинство широко используемых языков программирования — тьюринг-полные. Это касается как императивных языков, таких как Паскаль, так и функциональных (Haskell) и языков логического программирования (Prolog). Некоторые языки программирования (Haskell, C++) обладают тьюринг-полнотой времени компиляции.
Полными по Тьюрингу являются также неограниченные грамматики.
Примерами неполных по Тьюрингу формализмов являются конечные автоматы, примитивно рекурсивные функции, контекстно-свободные и регулярные грамматики.
| Это заготовка статьи по информатике. Вы можете помочь проекту, исправив и дополнив её. |
Полнота по Тьюрингу.