13: Невизначність
- Page ID
- 52937
\( \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: Проблема рішення є нерозв'язною
- Якби проблема рішення була розв'язною, ми могли б використовувати її для вирішення проблеми зупинки.