UK 
EnglishТипова
Polski🖥️ Машина Тьюринга
Покроковий симулятор машини Тьюринга з анімованою стрічкою, підсвіченою таблицею переходів і п'ятьма програмами: двійковий інкремент, унарне додавання, перевірка паліндрому, копіювання рядка та 3-станний зайнятий бобер.
Про симулятор машини Тьюринга
Алан Тьюринг представив свою абстрактну обчислювальну машину в знаковій статті 1936 року «On Computable Numbers» як інструмент для доведення того, що деякі задачі — найвідоміша з яких проблема зупинки — нерозв'язні жодним алгоритмом. Машина Тьюринга складається з нескінченної стрічки, поділеної на клітини (кожна містить символ зі скінченного алфавіту), головки читання/запису, що рухається по одній клітині за раз, і скінченної множини станів, керованих таблицею переходів: за поточного стану та символу під головкою таблиця визначає новий символ для запису, напрямок руху (ліворуч чи праворуч) і наступний стан. Попри цей мінімалістичний опис, теза Черча-Тьюринга стверджує, що будь-яку функцію, обчислювану будь-яким фізично реалізовним пристроєм, може обчислити й машина Тьюринга.
Цей симулятор надає анімований покроковий перегляд стрічки з підсвіченою головкою, повне відображення таблиці переходів станів і п'ять вбудованих програм: двійковий інкремент, унарне додавання, перевірку паліндрому, копіювання рядка та «зайнятого бобра» для обраної кількості станів. Ви можете призупинити на будь-якому кроці, перевірити стрічку та редагувати таблицю переходів, щоб написати власні програми — це ідеальний спосіб дослідити теорію обчислюваності і межу між «завершується» та «працює вічно».
Часті запитання
Що таке проблема зупинки і чому жодна машина Тьюринга не може її розв'язати?
Проблема зупинки запитує: маючи опис машини Тьюринга M і вхід w, чи зупиниться M врешті-решт на w? Тьюринг довів у 1936 році, що жоден загальний алгоритм не може відповісти на це для всіх пар (M, w). Доведення — це діагональний аргумент: припустимо, що існує детектор зупинки H, тоді побудуємо машину D, яка використовує H, щоб робити протилежне тому, що H передбачає про саму D, — це веде до суперечності.
Що таке проблема «зайнятого бобра»?
Функція «зайнятого бобра» BB(n) — це максимальна кількість символів «1», яку n-станова, 2-символьна машина Тьюринга може записати на порожній стрічці перед зупинкою. Відомі значення: BB(1)=1, BB(2)=4, BB(3)=6, BB(4)=13, BB(5)≥4098. BB(n) зростає швидше за будь-яку обчислювану функцію, що доводить її необчислюваність.
Чи є всі сучасні комп'ютери насправді просто машинами Тьюринга?
У сенсі обчислюваності — які задачі можна розв'язати — так, за тезою Черча-Тьюринга. Будь-яку функцію, яку може обчислити ваш ноутбук чи телефон, може обчислити й достатньо велика машина Тьюринга, і навпаки. Проте реальні комп'ютери суттєво різняться за ефективністю: багатострічкові й недетерміновані машини Тьюринга використовуються в теорії складності для визначення класів P, NP, PSPACE та EXPTIME.
Як виглядає таблиця переходів машини Тьюринга?
Функція переходу δ відображає (поточний_стан, прочитаний_символ) у (новий_символ, напрямок, наступний_стан). Для 3-станової, 2-символьної машини таблиця має 6 записів. Кожен запис зазвичай записується як п'ятірка: (q, s) → (s', D, q'), де q — поточний стан, s — прочитаний символ, s' — символ для запису, D ∈ {L, R} — напрямок руху, а q' — наступний стан.
Що таке універсальна машина Тьюринга?
Універсальна машина Тьюринга (УМТ) отримує на вхід закодований опис будь-якої іншої машини Тьюринга M разом із входом M і покроково симулює обчислення M. УМТ є теоретичною основою комп'ютерів загального призначення: подібно до того, як процесор виконує довільні програми, декодуючи байти інструкцій, УМТ виконує довільні машини, декодуючи їхні таблиці переходів зі стрічки. Мінський (1962) показав, що УМТ можна побудувати лише з 7 станів і 4 символів.