Повнота за Тюрінгом
У теорії алгоритмів набір правил маніпуляції даними (набір інструкцій, мова програмування, чи клітинний автомат) вважається повним за Тюрінгом тоді і тільки тоді, коли цей набір може моделювати однострічкову машину Тюрінга. Класичними системами що теж описуються простими правилами, та є Тюрінг-повними є контекстно-залежні граматики, рекурсивні функції, та лямбда-числення.
На практиці, повнота за Тюрінгом означає, що при застосуванні певної послідовності правил над даними можна отримати результат будь-якого обчислення. Пристрій з Тюрінг-повним набором інструкцій є означенням універсального комп'ютера. Щоб бути повним за Тюрінгом достатньо мати команди переходу як умовний, так і безумовний оператори, та можливість змінювати пам'ять.
Щоб показати що щось є Тюрінг-повним, достатньо показати, що на ньому можна емулювати найпримітивніший універсальний комп'ютер, оскільки навіть найпростіший універсальний комп'ютер може емулювати найскладніший. Всі мови загального призначення, та набори машинних інструкцій є повними за Тюрінгом, доки не постає проблема скінченності пам'яті. Тюрінг-повні машини описані як такі, що мають необмежений обсяг пам'яті, а в той час набори машинних інструкцій складені, щоб працювати з конкретним, обмеженим обсягом оперативної пам'яті.
У теорії алгоритмів існує близький термін:
Тюрінг-еквівалентність — два комп'ютери P та Q називаються Тюрінг-еквівалентними, якщо P може імітувати Q та Q може імітувати P.
Машину Тюрінга може імітувати тільки Тюрінг-повна система, тому цей термін найчастіше застосовується, щоб описати еквівалентну за Тюрінгом до машини Тюрінга. А все тому, що кожен реальний комп'ютер може моделюватись машиною Тюрінга, це спостереження зафіксоване тезою Черча.
Приклади
Тюрінг-повні
Більшість мов програмування є повними за Тюрінгом. Це включає:
- Всі мови загального призначення
- Процедурні як Pascal
- Об'єктно-орієнтовані як Java
- Багатопарадигмові як Python
- А також мови з не такими поширеними парадигмами
- Функціональні, як Haskell та Lisp
- Логічні як Prolog.
- Декларативні як XSLT.
- Езотеричні мови програмування, як brainfuck.
Властивості мови, що використовуються для досягнення Тюрінг-повноти можуть бути досить різними. Fortran може використовувати цикли, goto чи рекурсію, Haskell, в якому немає циклів буде використовувати рекурсію. Тюрінг-повнота — це абстрактна властивість, а не домовленість щодо того, які елементи повинна мати мова, щоб реалізувати цю властивість.
Не Тюрінг-повні
Існує багато мов, які не є Тюрінг-повними. Наприклад:
- Регулярні вирази та скінченні автомати що їх реалізують.
- Контекстно-вільні граматики та магазинні автомати що їх реалізують.
- Піксельні шейдери
- Послідовності формул в електронних таблицях, що не містять циклів.
Попри те, що в цих мовах можна розв'язувати багато цікавих задач, та все ж вони не є Тюрінг-повними, бо не можуть виконувати циклів.