В теории вычислимости система правил манипулирования данными (например, набор команд компьютера , язык программирования или клеточный автомат ) называется полной по Тьюрингу или вычислительно универсальной , если ее можно использовать для моделирования любой машины Тьюринга . Это означает, что эта система способна распознавать или определять другие наборы правил манипулирования данными. Полнота по Тьюрингу используется как способ выразить мощь такого набора правил манипулирования данными. Практически все современные языки программирования являются полными по Тьюрингу. Концепция названа в честь английского математика и ученого-компьютерщика Алана Тьюринга .
Родственная концепция - это эквивалентность по Тьюрингу : два компьютера P и Q называются эквивалентными, если P может имитировать Q, а Q может имитировать P. Тезис Черча-Тьюринга предполагает, что любая функция, значения которой могут быть вычислены алгоритмом, может быть вычислена с помощью Машина Тьюринга, и, следовательно, если какой-либо компьютер реального мира может смоделировать машину Тьюринга, то он эквивалентен машине Тьюринга. Универсальная машина Тьюринга может использоваться для имитации любой машины Тьюринга и, соответственно, вычислительных аспектов любого возможного реального компьютера. [Примечание 1]
Чтобы показать, что что-то является полным по Тьюрингу, достаточно показать, что его можно использовать для моделирования некоторой полной по Тьюрингу системы. Например, императивный язык является полным по Тьюрингу, если он имеет условное ветвление (например, операторы «если» и « перейти » или инструкцию «ветвь, если ноль»; см. объем памяти (например, возможность поддерживать произвольное количество элементов данных). Никакая физическая система не может иметь бесконечную память, но если игнорировать ограничение конечной памяти, большинство языков программирования в остальном являются полными по Тьюрингу.
В разговорной речи термины «полный по Тьюрингу» и «эквивалентный по Тьюрингу» используются для обозначения того, что любой реальный компьютер общего назначения или компьютерный язык может приблизительно имитировать вычислительные аспекты любого другого реального компьютера общего назначения или компьютерный язык.
Реальные компьютеры, построенные до сих пор, могут быть функционально проанализированы как одноленточная машина Тьюринга («лента», соответствующая их памяти); таким образом, связанная математика может применяться, достаточно далеко абстрагируя их работу. Однако реальные компьютеры имеют ограниченные физические ресурсы, поэтому они являются полными только линейными ограниченными автоматами . Напротив, универсальный компьютер определяется как устройство с полным по Тьюрингу набором инструкций, бесконечной памятью и бесконечным доступным временем.
В теории вычислимости для описания вычислительной мощности вычислительной системы (например, абстрактной машины или языка программирования ) используется несколько тесно связанных терминов: