Повнота за Тюрінгом

У теорії алгоритмів набір правил маніпуляції даними (набір інструкцій, мова програмування чи клітинний автомат) вважається повним за Тюрінгом тоді і тільки тоді, коли цей набір може моделювати однострічкову машину Тюрінга. Класичними системами, що теж описуються простими правилами та є Тюрінг-повними, є контекстно-залежні граматики, рекурсивні функції та лямбда-числення.

На практиці повнота за Тюрінгом означає, що при застосуванні певної послідовності правил над даними можна отримати результат будь-якого обчислення. Пристрій з Тюрінг-повним набором інструкцій є означенням універсального комп'ютера. Щоб бути повним за Тюрінгом достатньо мати команди переходу як умовний, так і безумовний оператори, та можливість змінювати пам'ять.

Щоб показати, що щось є Тюрінг-повним, достатньо показати, що на ньому можна емулювати найпримітивніший універсальний комп'ютер, оскільки навіть найпростіший універсальний комп'ютер може емулювати найскладніший. Всі мови загального призначення та набори машинних інструкцій є повними за Тюрінгом, доки не постає проблема скінченності пам'яті. Тюрінг-повні машини описані як такі, що мають необмежений обсяг пам'яті, а в той час набори машинних інструкцій складені, щоб працювати з конкретним, обмеженим обсягом оперативної пам'яті.

У теорії алгоритмів існує близький термін:

Тюрінг-еквівалентність — два комп'ютери P та Q називаються Тюрінг-еквівалентними, якщо P може імітувати Q та Q може імітувати P.

Машину Тюрінга може імітувати тільки Тюрінг-повна система, тому цей термін найчастіше застосовується, щоб описати еквівалентну за Тюрінгом до машини Тюрінга. А все тому, що кожен реальний комп'ютер може моделюватись машиною Тюрінга, це спостереження зафіксоване тезою Черча.

Приклади

Тюрінг-повні

Більшість мов програмування є повними за Тюрінгом. Це включає:

• Всі мови загального призначення
  • Процедурні як Pascal
  • Об'єктно-орієнтовані як Java
  • Багатопарадигмові як Python
• А також мови з не такими поширеними парадигмами
  • Функціональні, як Haskell та Lisp
  • Логічні як Prolog
  • Декларативні як XSLT
  • Езотеричні мови програмування, як brainfuck

Властивості мови, що використовуються для досягнення Тюрінг-повноти, можуть бути досить різними. Fortran може використовувати цикли, goto чи рекурсію, Haskell, в якому немає циклів, буде використовувати рекурсію. Тюрінг-повнота — це абстрактна властивість, а не домовленість щодо того, які елементи повинна мати мова, щоб реалізувати цю властивість.

Не Тюрінг-повні

Існує багато мов, які не є Тюрінг-повними. Наприклад:

• Регулярні вирази та скінченні автомати, що їх реалізують
• Контекстно-вільні граматики та магазинні автомати, що їх реалізують
• Піксельні шейдери
• Послідовності формул в електронних таблицях, що не містять циклів.

Попри те, що в цих мовах можна розв'язувати багато цікавих задач, та все ж вони не є Тюрінг-повними, бо не можуть виконувати циклів.

Посилання

• c2.com