12.10: Резюме

Last updated
Save as PDF

Page ID: 52974

\( \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}}\)

Template:MathJaxZach

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

Числа можна дуже легко представити у вигляді послідовностей штрихів на стрічці машини Тьюринга. Ми говоримо, що функція\(\Nat \to \Nat\) Тьюринга обчислюється, якщо є машина Тьюринга, яка, коли вона запускається на унарному поданні\(n\) як вхід, врешті-решт зупиняється зі своєю стрічкою, що містить унарне представлення\(f(n)\) як вихід. Багато знайомих арифметичних функцій легко (або не так легко) показано, що вони обчислюються Тьюрингом. Було запропоновано багато інших моделей обчислень, крім машин Тьюринга; і завжди з'ясовувалося, що обчислювані арифметичні функції також є обчислювальними Тьюрингом. Це розглядається як підтримка тези Церква-Тьюринга, що кожна арифметична функція, яку можна ефективно обчислити, є обчислювальною Тьюрингом.