Т’юрінг-повнота
Зміст
[ правити ]
| Визначення: |
| Обчислювальний пристрій єТьюрінг-еквівалентним(англ.Turing-equivalent), якщо він може емулювати машину Тьюринга. |
| Визначення: |
| Завдання називаєтьсяТ'юрінг-повним(англ.Turing-complete), якщо його можна вирішити, використовуючи тільки машину Тьюринга або будь-яку систему, що є Т'юрінг-еквівалентною. |
Найчастіше Т'юрінг-еквівалентні мови програмування називають Т'юрінг-повними.
Теоретично обчислюваностівиконавець(безліч обчислювальних елементів) називаєтьсяТьюрінг-повним, якщо у ньому можна реалізувати будь-яку обчислювану функцію. Іншими словами, для кожної обчислюваної функції існує елемент, що її обчислює (наприклад, машина Тьюринга) або програма для виконавця, а всі функції, що обчислюються безліччю обчислювачів, є обчислюваними функціями (можливо, при деякому кодуванні вхідних і вихідних даних).
Будь-яка повна за Тьюрингом мова досить універсальна, щоб мати можливість імітувати будь-яку іншу мову (хоча і з потенційним уповільненням у роботі). Такі мови еквівалентні у межах обчислень, які можуть зробити. Повні за Тьюрингом мови настільки поширені, що їх можна виявити навіть у примітивних на перший погляд системах, наприклад, клітинних автоматах або мозаїчних системах.
Насправді повнота по Тьюрингу схожа ідеалізацію. Комп'ютери мають обмежену кількість пам'яті, а необмежена за часом їхня робота може бути перервана фізичним впливом (вимикання, поломка), що обмежує кількість завдань, які вони можуть вирішити. Насправді фізичні обмеження в контекстіТ'юрінг-повноти не беруться до уваги: Т'юрінг-повний виконавець не повинен бути обмежений за часом та пам'яттю лише самим виконавцем.
Критерії Т'юрінг-повноти [ред.
Якщо мовою програмування можна реалізувати машину Тьюринга, то така мова Тьюрінг-повний, і навпаки. Можливість реалізації машини Тьюринга конкретною мовою програмування можнагрубоописати як перелік вимог, яким ця мова має для цього задовольняти:
- Кінцівка (немає нескінченних символьних множин тощо).
- Фіксований опис (формальність [1]).
- Завжди достатній обсяг доступної пам'яті - в ідеалі тут мається на увазі необмежена пам'ять, проте фізичні рамки не дозволяють зробити пам'ять ЕОМ нескінченною, тому вона просто має бути "always big enough".
- Необмеженість часу виконання — будь-яка програма повинна мати можливість працювати доти, доки не завершиться.
- Можливість функціональної композиції (виклик однієї функції з іншої, рекурсія).
- Наявність циклів [math][/math] з перериванням чи еквівалентних їм конструкцій.
- Можливість зупиняти виконання (halt) або якимось чином подавати сигнал про результати виконання.
- Подання безлічі натуральних чисел, поняття нуля та наступного числа. Можливі інші системи.
- Підтримка вхідних та вихідних даних (I/O), причому без формальних обмежень обсягом. Очевидно, що якщо будь-яка програма, написана якоюсь мовою програмування, приймає на вхід не більше фіксованого n біт даних і повертає не більше n біт, ця мова не може бути Т'юрінг-повною.
Т'юрінг-повнота та неповнота деяких мов програмування [ред.]
Довести Т'юрінг-повноту мови програмування можна, запропонувавши спосіб реалізації машини Тьюринга цією мовою. Крім того, можна запропонувати на ньому інтерпретатор Т'юрінг-повної мови.
Assembly language [ред.]
Мова Асемблера досить примітивна щодо мов програмування високого рівня: вона розрахована на архітектуру з кінцевою пам'яттю і працює з кінцевим набором регістрів. Однак, не був би він повним за Тьюрингом, не були б Т'юрінг-повні і будь-які високорівневі мови програмування.
Все необхідне для машини Тьюринга на asm можна зробити приблизно так:
І далі використовувати інструкцію [math]\mathrm[/math] або подібну до неї, щоб виконувати певну послідовність команд при певному поточному значенні, таким чином забезпечивши розгалуження.
Pascal [ред.]
Мова Pascal дозволяє змоделювати стрічку машини Тьюринга за допомогою двонаправленого списку зі змінних, створюваних оператором [math]\mathrm[/math] , семантика якого передбачає відмови у створенні змінної. Також за допомогою списків можна змоделювати скільки завгодно великі числа. Стандарт не накладає жодних обмежень: вказівний тип абстрактний, безліч значень вказівного типу не обмежена. У Паскалі є ще один тип даних з безліччю значень, файловий, також придатний для моделювання стрічки машини Тьюринга і представлення великих чисел. Достатньо тверджень для очевидності Т'юрінг-повноти мови Pascal.
C [ред.]
SQL [ред.]
HTML [ред.]
HTML можна назвати мовою програмування лише у контексті формальної полеміки. Насправді він є мовоюгіпертекстової розмітки та ні чим більше. Т. е. на HTML можна зробити лише деяку обмежену сукупність дій, інтерпретованих браузером, проте ніхто не забороняє зробити мову, ідентичну за синтаксисом з HTML, але інтерпретується зовсім інакше таким чином, щоб він був повним по Тьюрингу.
Деякі інші ЯП [ред.]
Цікаві випадки повноти по Тьюрингу [ред.]
Шаблони C++ [ред.]
Шаблони C++ дозволяють робити складні обчислення ще стадії компіляції програми. Вперше це продемонстровано Ервіном Унрухом, який реалізував рекурсивний алгоритм розпізнавання простих чисел у процесі компіляції. Пізніше у статті Університету Індіана було продемонстровано кодування машини Т'юрінга у шаблонах C++ [4] .
Java Generics [ред.]
Аналогічно C++ Templates, Generics, незважаючи на свої відмінності, теж виявилися повними за Тьюрингом, що було підтверджено Раду Григором в одній із статей Кентського Університету [5] .
URISC [ред.]
URISC(від англ.Ultimate RISC) — граничний випадок процесора типу RISC (буквально: комп'ютер із гранично скороченим набором інструкцій), який вміє виконувати одну-єдину інструкцію. Зазвичай це «відняти і пропустити наступну інструкцію, якщо віднімання було більше зменшуваного» (англ.«reverse-subtract and skip if borrow»). Аналогічна концепція, заснована саме на «відняти і перейти, якщо результат не позитивний» (англ. ), називаєтьсяSUBLEQ.
URISCтакож відомий у сучасній літературі якOISC(англ. One Instruction Set Computer) і є повним за Тьюрингом.
mov [ред.]
Утиліта M/o/Vfuscatorперетворює будь-яку програму мовою C на величезну послідовність з інструкцій [math]\mathrm [/math] [6] .