13.1: Вступ

Last updated

Oct 27, 2022
Save as PDF
- 13: Невизначність
- 13.2: Перерахування машин Тьюринга

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

Може здатися очевидним, що не кожна функція, навіть кожна арифметична функція, може бути обчислюваною. Їх просто занадто багато, чия поведінка занадто складна. Функції, визначені з розпаду радіоактивних частинок, наприклад, або іншої хаотичної або випадкової поведінки. Припустимо, ми починаємо відлік 1-секундних інтервалів з заданого часу і визначаємо функцію $f(n)$ як кількість частинок у Всесвіті, які розпадаються в $n$ -му 1-секундному інтервалі після цього початкового моменту. Це здається кандидатом на функцію, яку ми ніколи не можемо сподіватися обчислити.

Але одна справа - не бути в змозі уявити, як можна було б обчислити такі функції, і зовсім інше, щоб насправді довести, що вони необчислювані. Насправді навіть функції, які здаються безнадійно складними, можуть в абстрактному сенсі бути обчислюваними. Наприклад, припустимо, що Всесвіт скінченний у часі - колись у дуже віддаленому майбутньому Всесвіт скоротиметься в єдину точку, як передбачають деякі космологічні теорії. Тоді залишається лише кінцева (але неймовірно велика) кількість секунд з того початкового моменту, для $f(n)$ якого визначено. І будь-яка функція, яка визначається лише для скінченно багатьох входів є обчислюваною: ми могли б перерахувати виходи в одній великій таблиці, або код його в одному дуже великий Тьюринга стан машини діаграма переходу.

Нас часто цікавлять окремі випадки функцій, значення яких дають відповіді на запитання «так/ні». Наприклад, питання «це $n$ просте число?» пов'язаний з функцією $\fn{isprime}(n) = \begin{cases} 1 & \text{if $n$ is prime}\\ 0 & \text{otherwise.} \end{cases}\nonumber$ Ми говоримо, що питання так/ні може бути ефективно вирішено, якщо $1/0$ асоційована функція -значення ефективно обчислюється.

Щоб математично довести, що існують функції, які неможливо ефективно обчислити, або проблеми, які не можуть ефективно вирішити, важливо виправити конкретну модель обчислень і показати про неї, що є функції, які вона не може обчислити, або проблеми, які вона не може вирішити. Ми можемо показати, наприклад, що не кожна функція може бути обчислена машинами Тьюринга, і не кожна проблема може бути вирішена машинами Тьюринга. Потім ми можемо звернутися до тези Церква-Тьюринга, щоб зробити висновок, що машини Тьюринга не тільки недостатньо потужні для обчислення кожної функції, але жодна ефективна процедура не може.

Ключем до доведення таких негативних результатів є той факт, що ми можемо привласнити номери самим машинам Тьюринга. Найпростіший спосіб зробити це - перерахувати їх, можливо, зафіксувавши певний спосіб запису машин Тьюринга і їх програм, а потім систематично перераховуючи їх. Як тільки ми побачимо, що це можна зробити, то існування Тьюринг-необчислюваних функцій випливає з простих міркувань кардинальності: набір функцій від $\Nat$ до $\Nat$ (насправді, навіть просто від $\Nat$ до $\{0, 1\}$ ) є незліченним, але оскільки ми можемо перерахувати всі машини Тьюринга, набір обчислюваних по Тьюрингу функцій лише незліченно нескінченний.

Ми також можемо визначити конкретні функції та проблеми, які ми можемо виявитися необчислюваними та невирішеними відповідно. Однією з таких проблем є так звана проблема зупинки. Машини Тьюринга можна остаточно описати, перерахувавши їх інструкції. Такий опис машини Тьюринга, тобто програма машини Тьюринга, звичайно, може бути використаний як вхід до іншої машини Тьюринга. Таким чином, ми можемо розглянути машини Тьюринга, які вирішують питання про інші машини Тьюринга. Одне особливо цікаве питання полягає в наступному: «Чи закінчується дана машина Тьюринга, коли вона почалася на вході $n$ ?» Було б непогано, якби була машина Тьюринга, яка могла б вирішити це питання: думайте про це як про машину Тьюринга з контролем якості, яка гарантує, що машини Тьюринга не потрапляють у нескінченні петлі тощо. Цікавий факт, який довів Тьюринг, полягає в тому, що такої машини Тьюринга бути не може. Не може бути жодної машини Тьюринга, яка при запуску на вході, що складається з опису машини Тьюринга $M$ та деякого числа $n$ , завжди зупинятиметься з виходом $1$ або $0$ відповідно до того, чи $M$ машина зупинилася б при запуску на вході $n$ чи ні.

Як тільки у нас є приклади конкретних невирішених проблем, ми можемо використовувати їх, щоб показати, що інші проблеми теж не можна вирішити. Наприклад, однією з визначених невирішених проблем є питання: «Чи $A$ дійсна формула першого порядку?». Не існує машини Тьюринга, яка, надана як вхідна формула першого порядку $A$ , гарантовано зупиняється з виходом $1$ або $0$ відповідно до того, чи $A$ є дійсним чи ні. Історично питання пошуку процедури ефективного вирішення цієї проблеми називалося просто «проблемою» рішення, і тому ми говоримо, що проблема вирішення нерозв'язна. Тьюринг і Черч довели цей результат незалежно приблизно в той же час, тому його також називають теоремою Церква-Тьюринга.