12: Обчислення машин Тьюринга
- Page ID
- 52938
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
- 12.1: Вступ
- Що це означає для функції, скажімо, від\(\mathbb{N}\)\(\mathbb{N}\) до бути обчислюваною? Серед перших відповідей, і найвідоміший, полягає в тому, що функція обчислюється, якщо її можна обчислити машиною Тьюринга.
- 12.2: Представлення машин Тьюринга
- Машини Тьюринга можуть бути представлені візуально діаграмами стану. Діаграми складаються з комірок стану, з'єднаних стрілками.
- 12.3: Машини Тьюринга
- Формальне визначення того, що являє собою машину Тьюринга, виглядає абстрактно, але насправді просто: воно просто упаковує в одну математичну структуру всю інформацію, необхідну для уточнення роботи машини Тьюринга. Це включає в себе (1), в якому стані може бути машина, (2) які символи дозволено бути на стрічці, (3) в якому стані машина повинна запуститися, і (4) який набір інструкцій машини.
- 12.4: Конфігурації та обчислення
- Формально ми можемо визначити обчислення машини Тьюринга на заданому вході як послідовність конфігурацій - і конфігурація, в свою чергу, є послідовністю символів (відповідних вмісту стрічки в заданій точці обчислення), число, що вказує на положення головки читання/запису, і стан.
- 12.5: Унарне представлення чисел
- Машини Тьюринга працюють над послідовностями символів, написаних на їх стрічці. Залежно від алфавіту, який використовує машина Тьюринга, ці послідовності символів можуть представляти різні входи та виходи. Особливий інтерес, звичайно, представляють машини Тьюринга, які обчислюють арифметичні функції, тобто функції натуральних чисел. Простий спосіб представлення позитивних цілих чисел - це кодування їх як послідовності одного символу\(1\).
- 12.6: Припинення держав
- Ідея, що стоїть за станом зупинки, проста: коли машина закінчила операцію (вона готова прийняти вхід або закінчила писати вихід), вона переходить у стан,\(h\) коли він зупиняється. Деякі машини мають два стани зупинки, один, який приймає вхід і той, який відхиляє введення.
- 12.7: Поєднання машин Тьюринга
- Щоб побудувати більш складні машини Тьюринга, важливо переконати себе, що ми можемо їх комбінувати, щоб ми могли будувати машини для вирішення більш складних проблем, розбиваючи процедуру на простіші частини.
- 12.8: Варіанти машин Тьюринга
- Насправді існує багато можливих способів визначення машин Тьюринга, з яких наша лише одна.
- 12.9: Теза Церква-Тьюринга
- Теза Церква-Тьюринга стверджує, що все, що обчислюється за допомогою ефективної процедури Тьюринга обчислюється.