13.3: Проблема зупинки

Last updated
Save as PDF

Page ID: 52966

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

Припустимо, ми виправили деякі кінцеві описи машин Тьюринга. Використовуючи їх, ми можемо перерахувати машини Тьюринга через їх описи, скажімо, упорядковані лексикографічним упорядкуванням. Кожна машина Тьюринга таким чином отримує індекс: його місце в перерахуванні$M_1$,,,$M_2$$M_3$,... описів машин Тьюринга.

Ми знаємо, що повинні бути функції, що не обчислюються по Тьюрингу: набір описів машин Тьюринга - і, отже, набір машин Тьюринга - перераховується, але набір всіх функцій від$\Nat$ до$\Nat$ - ні. Але ми можемо знайти конкретні приклади не обчислюваних функцій, а також. Однією з таких функцій є функція зупинки.

Визначення$\PageIndex{1}$: Halting function

Функція зупинки$h$ визначається як\[h(e,n) = \begin{cases} \text{0} & \text{if machine $M_e$ does not halt for input $n$} \\ \text{1} & \text{if machine $M_e$ halts for input $n$} \end{cases}\nonumber\]

Визначення$\PageIndex{2}$: Halting problem

Проблема зупинки - це проблема визначення (для будь-якого$n$)$e$, чи$M_e$ зупиняється машина Тьюринга для введення$n$ ударів.

Ми показуємо, що не$h$ є Turing-computable, показуючи, що пов'язана функція$s$, не є Turing-computable. Цей доказ спирається на те, що все, що можна обчислити машиною Тьюринга, можна обчислити, використовуючи лише два символи:$\TMblank$ і той факт$\TMstroke$, що дві машини Тьюринга можуть бути підключені разом, щоб створити одну машину.

Визначення$\PageIndex{3}$

Функція$s$ визначається як\[s(e) = \begin{cases} \text{0} & \text{if machine $M_e$ does not halt for input $e$} \\ \text{1} & \text{if machine $M_e$ halts for input $e$} \end{cases}\nonumber\]

Лемма$\PageIndex{1}$

Функція не$s$ є обчислювальною Тьюрингом.

Доказ. Ми припускаємо, для протиріччя, що функція$s$ Тьюринга обчислюється. Тоді була б машина Тьюринга$S$, яка обчислює$s$. Ми можемо припустити, без втрати спільності, що коли$S$ зупиняється, він робить це під час сканування першого квадрата. Ця машина може бути «підключена» до іншої машини$J$, яка зупиняється, якщо вона запускається на порожній стрічці (тобто, якщо вона читає$\TMblank$ в початковому стані під час сканування квадрата праворуч від символу кінця стрічки), а в іншому випадку блукає вправо, ніколи не зупиняючись. $S \concat J$, машина, створена шляхом підключення$S$ до$J$, є машиною Тьюринга, так що це$M_e$ для деяких$e$ (тобто вона з'являється десь у перерахуванні). Почати$M_e$ на вході$e$$\TMstroke$ s. Існує дві можливості: або$M_e$ зупиняється, або він не зупиняється.

Припустимо,$M_e$ зупиняється для введення$e$$\TMstroke$ s$s(e) = 1$. Отже$S$, коли почався$e$, зупиняється з єдиним$\TMstroke$ виходом на стрічку. Потім$J$ починається з$\TMstroke$ на стрічці. В такому випадку$J$ не зупиняється. Але$M_e$ це машина$S \concat J$, тому вона повинна робити саме те, що$S$ далі$J$ буде робити. Таким чином,$M_e$ не може зупинитися для введення з$e$$\TMstroke$.
Тепер припустимо, що$M_e$ не зупиняється для введення$e$$\TMstroke$ s Потім$s(e) = 0$, і$S$, при запуску на вході$e$, зупиняється з порожньою стрічкою. $J$, При запуску на порожній стрічці, відразу ж зупиняється. Знову ж таки,$M_e$ робить те, що$S$ слідувало$J$ б робити, так що$M_e$ повинні зупинитися для введення з$e$$\TMstroke$.

Це показує, що не може бути машини Тьюринга$S$: не$s$ піддається обчисленню Тьюринга. ◻

Теорема$\PageIndex{1}$: Unsolvability of the Halting Problem

Проблема зупинки є нерозв'язною, тобто функція Тьюринга не$h$ піддається обчисленню.

Доказ. $h$Припустимо, що Тьюринг обчислюється, скажімо, машиною Тьюринга$H$. Ми могли б$H$ використати для побудови машини Тьюринга, яка обчислює$s$: По-перше, зробіть копію вхідних даних (розділених порожнім). Потім поверніться до початку, і біжіть$H$. Ми можемо чітко зробити машину, яка робить першу, і якщо б$H$ існувала, ми могли б «підключити його» до такої модифікованої машини подвоєння, щоб отримати нову машину, яка б визначала, якщо$M_e$ зупиняється на вході$e$, тобто обчислює $s$. Але ми вже показали, що такої машини не може існувати. Отже, також не$h$ є обчислювальним Тьюрингом. ◻

Проблема$\PageIndex{1}$

Проблема «Три зупинки» (3-Halt) - це проблема надання процедури рішення, щоб визначити, чи зупиняється довільно вибрана машина Тьюринга для введення трьох штрихів на інакше порожній стрічці. Доведіть, що проблема 3-Halt нерозв'язна.

Проблема$\PageIndex{2}$

Показати, що якщо проблема зупинки вирішується для машини Тьюринга і вхідних пар$M_e$ і$n$ де$e \neq n$, то вона також вирішується для випадків, коли$e = n$.

Проблема$\PageIndex{3}$

Доведено, що проблема зупинки є нерозв'язною, якщо входом є число$e$, яке ідентифікує машину Тьюринга$M_e$ за допомогою перерахування всіх машин Тьюринга. Що робити, якщо ми дозволимо опис машин Тьюринга з розділу 13.2 безпосередньо як вхід? (Звичайно, це вимагатиме більшого алфавіту.) Чи може бути машина Тьюринга, яка вирішує проблему зупинки, але приймає як вхідні описи машин Тьюринга, а не індекси? Поясніть, чому чи чому ні.