У теорії алгоритмів набір правил маніпуляції даними (набір інструкцій, мова програмування чи клітинний автомат) вважається повним за Тюрінгом тоді і тільки тоді, коли цей набір може моделювати однострічкову машину Тюрінга. Класичними системами, що теж описуються простими правилами та є Тюрінг-повними, є контекстно-залежні граматики, рекурсивні функції та лямбда-числення.
На практиці повнота за Тюрінгом означає, що при застосуванні певної послідовності правил над даними можна отримати результат будь-якого обчислення. Пристрій з Тюрінг-повним набором інструкцій є означенням універсального комп'ютера. Щоб бути повним за Тюрінгом достатньо мати команди переходу як , так і безумовний оператори, та можливість змінювати пам'ять.
Щоб показати, що щось є Тюрінг-повним, достатньо показати, що на ньому можна емулювати найпримітивніший універсальний комп'ютер, оскільки навіть найпростіший універсальний комп'ютер може емулювати найскладніший. Всі мови загального призначення та набори машинних інструкцій є повними за Тюрінгом, доки не постає проблема скінченності пам'яті. Тюрінг-повні машини описані як такі, що мають необмежений обсяг пам'яті, а в той час набори машинних інструкцій складені, щоб працювати з конкретним, обмеженим обсягом оперативної пам'яті.
У теорії алгоритмів існує близький термін:
Тюрінг-еквівалентність — два комп'ютери P та Q називаються Тюрінг-еквівалентними, якщо P може імітувати Q та Q може імітувати P.
Машину Тюрінга може імітувати тільки Тюрінг-повна система, тому цей термін найчастіше застосовується, щоб описати еквівалентну за Тюрінгом до машини Тюрінга. А все тому, що кожен реальний комп'ютер може моделюватись машиною Тюрінга, це спостереження зафіксоване тезою Черча.
Приклади
Тюрінг-повні
Більшість мов програмування є повними за Тюрінгом. Це включає:
- Всі мови загального призначення
- Процедурні як Pascal
- Об'єктно-орієнтовані як Java
- Багатопарадигмові як Python
- А також мови з не такими поширеними парадигмами
- Функціональні, як Haskell та Lisp
- Логічні як Prolog
- Декларативні як XSLT
- Езотеричні мови програмування, як brainfuck
Властивості мови, що використовуються для досягнення Тюрінг-повноти, можуть бути досить різними. Fortran може використовувати цикли, goto чи рекурсію, Haskell, в якому немає циклів, буде використовувати рекурсію. Тюрінг-повнота — це абстрактна властивість, а не домовленість щодо того, які елементи повинна мати мова, щоб реалізувати цю властивість.
Не Тюрінг-повні
Існує багато мов, які не є Тюрінг-повними. Наприклад:
- Регулярні вирази та скінченні автомати, що їх реалізують
- Контекстно-вільні граматики та (магазинні автомати), що їх реалізують
- Послідовності формул в електронних таблицях, що не містять циклів.
Попри те, що в цих мовах можна розв'язувати багато цікавих задач, та все ж вони не є Тюрінг-повними, бо не можуть виконувати циклів.
Посилання
Це незавершена стаття про програмування. Ви можете проєкту, виправивши або дописавши її. |
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет