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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

Приклади[ред. | ред. код]

Тюрінг-повні[ред. | ред. код]

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

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

Не Тюрінг-повні[ред. | ред. код]

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

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

Посилання[ред. | ред. код]