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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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