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

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

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

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

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

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

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

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

Приклади

[ред. | ред. код]

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

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

Посилання

[ред. | ред. код]