13: Невизначність

Last updated

Oct 27, 2022
Save as PDF
- 12.10: Резюме
- 13.1: Вступ

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

13.1: Вступ
Одна справа - не бути в змозі уявити, як можна було б обчислити складні функції, і зовсім інше, щоб насправді довести, що вони необчислювані.
13.2: Перерахування машин Тьюринга
Ми можемо показати, що набір всіх машин Тьюринга піддається рахунку. Це випливає з того, що кожну машину Тьюринга можна остаточно описати.
13.3: Проблема зупинки
Проблема зупинки є одним із прикладів більшого класу задач виду « $X$ можна виконати за допомогою машин Тьюринга». (Відповідь - ні: проблема зупинки нерозв'язна.)
13.4: Рішення проблеми
Ми говоримо, що логіка першого порядку вирішується, якщо існує ефективний метод визначення того, чи є дане речення дійсним чи ні. Як виявляється, такого методу немає: проблема вирішення обґрунтованості пропозицій першого порядку нерозв'язна.
13.5: Представлення машин Тьюринга
Для того, щоб представити машини Тьюринга та їх поведінку реченням логіки першого порядку, ми повинні визначити відповідну мову. Мова складається з двох частин: присудкових символів для опису конфігурацій машини, і виразів для нумерації кроків виконання («моментів») і позицій на стрічці.
13.6: Перевірка представництва
Для того, щоб переконатися, що наше представництво працює, ми повинні довести дві речі. По-перше, ми повинні показати, що якщо $M$ зупиняється на вході $w$ , то $T(M, w) \rightarrow E(M, w)$ є дійсним. Потім, ми повинні показати зворотне, тобто, що якщо $T(M, w) \rightarrow E(M, w)$ є дійсним, то $M$ насправді в кінцевому підсумку зупинити при запуску на вході $w$ .
13.7: Проблема рішення є нерозв'язною
Якби проблема рішення була розв'язною, ми могли б використовувати її для вирішення проблеми зупинки.
13.8: Резюме