Skip to main content
LibreTexts - Ukrayinska

13.7: Проблема рішення є нерозв'язною

  1. Last updated
  2. Save as PDF
  • Page ID
    52950

    • \( \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

    Теорема\(\PageIndex{1}\)

    Проблема вирішення нерозв'язна.

    Доказ. Припустимо, завдання рішення була розв'язною, тобто припустимо, що існувала машина\(D\) Тьюринга наступного роду. Всякий раз, коли\(D\) запускається на стрічці, яка містить\(B\) речення логіки першого порядку як вхід,\(D\) врешті-решт\(1\) зупиняється і виводить, якщо\(B\) є дійсним і\(0\) іншим чином. Тоді ми могли б вирішити проблему зупинки наступним чином. Побудовано машину Тьюринга,\(E\) яка, задана як вхідне\(e\) число машини Тьюринга\(M_e\) та введення\(w\), обчислює відповідне речення\(T(M_e, w) \lif E(M_e, w)\) та зупиняє, скануючи крайній лівий квадрат на стрічці. Потім машина\(E \concat D\) буде, з урахуванням вхідних даних\(e\) і\(w\), спочатку обчислити,\(T(M_e, w) \lif E(M_e, w)\) а потім запустити машину рішення проблеми\(D\) на цьому вході. \(D\)зупиняється з виходом\(1\) iff\(T(M_e, w) \lif E(M_e, w)\) є дійсним і виводить\(0\) інакше. За Lemma 13.6.4 і Lemma 13.6.3,\(T(M_e, w) \lif E(M_e, w)\) є дійсним, якщо\(M_e\) зупиняється на вході\(w\). Таким чином\(E\concat D\), заданий вхід\(e\) і\(w\) зупинки з виходом\(1\) iff\(M_e\) зупиняється на вході\(w\) і зупиняється з виходом\(0\) інакше. Іншими словами,\(E \concat D\) вирішить проблему зупинки. Але ми знаємо, за теоремою 13.3.1, що такої машини Тьюринга не може існувати. ◻