13.8: Резюме

Last updated

Oct 27, 2022
Save as PDF
- 13.7: Проблема рішення є нерозв'язною
- Назад Матерія

$\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

Машини Тьюринга визначаються своїми наборами інструкцій, які є кінцевими множинами п'ятикраток (для кожного стану та прочитаного символу вказують новий стан, написаний символ та рух голови). Кінцеві множини п'ятикраток перераховуються, тому існує спосіб пов'язати число з кожним набором інструкцій машини Тьюринга. Індекс машини Тьюринга - це число, пов'язане з його набором інструкцій за фіксованою такою схемою. Таким чином ми можемо «говорити» про машини Тьюринга опосередковано - кажучи про їх індекси.

Однією з важливих проблем щодо поведінки машин Тьюринга є те, чи вони в кінцевому підсумку зупиняються. $h(e, n)$ Дозволяти функція, яка, $= 1$ якщо машина Тьюринга з індексом $e$ зупиняється при запуску на вході $n$ , і в $=0$ іншому випадку. Вона називається функцією зупинки. Питання про те, чи є функція зупинки сама по собі обчислювана Тьюринга, називається проблемою зупинки. Відповідь - ні: проблема зупинки нерозв'язна. Це встановлюється за допомогою діагонального аргументу.

Проблема зупинки є лише одним із прикладів більшого класу задач виду «можуть $X$ бути виконані за допомогою машин Тьюринга». Ще однією центральною проблемою логіки є проблема вирішення логіки першого порядку: чи є машина Тьюринга, яка може вирішити, чи є дане речення дійсним чи ні. Ця відома проблема також вирішувалася негативно: проблема рішення нерозв'язна. Це встановлюється аргументом скорочення: ми можемо зв'язати з кожною машиною Тьюринга $M$ і ввести $w$ речення першого порядку, $T(M, w) \lif E(M, w)$ яке є дійсним, якщо $M$ зупиняється при запуску на вході $w$ . Якби проблема рішення була розв'язною, ми могли б таким чином використовувати її для вирішення проблеми зупинки.