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

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

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

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

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

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

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

Приклади

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

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

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

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

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

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

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

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

Посилання

• Використано матеріали зі статті в англійській Вікіпедії.
• c2.com