Saltar al contenido principal
LibreTexts Español

13.7: El problema de la decisión es irresoluble

  1. Última actualización
  2. Guardar como PDF
  • Page ID
    103662

    • \( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Template:MathJaxZach

    Teorema\(\PageIndex{1}\)

    El problema de la decisión es irresoluble.

    Prueba. Supongamos que el problema de decisión era solucionable, es decir, supongamos que había una máquina Turing\(D\) del siguiente tipo. Siempre que\(D\) se inicia en una cinta que contiene una frase\(B\) de lógica de primer orden como entrada,\(D\) finalmente se detiene, y las salidas\(1\) iff\(B\) es válido y de\(0\) otra manera. Entonces podríamos resolver el problema de la detención de la siguiente manera. Construimos una máquina de Turing\(E\) que, dado como entrada el número\(e\) de máquina de Turing\(M_e\) y entrada\(w\), calcula la oración correspondiente\(T(M_e, w) \lif E(M_e, w)\) y se detiene, escaneando el cuadrado más a la izquierda en la cinta. La máquina entonces, dada la entrada\(e\) y\(w\), primero\(E \concat D\) computaría\(T(M_e, w) \lif E(M_e, w)\) y luego ejecutaría la máquina de problemas de decisión\(D\) en esa entrada. \(D\)se detiene con salida\(1\) iff\(T(M_e, w) \lif E(M_e, w)\) es válido y salidas de\(0\) lo contrario. Por Lema 13.6.4 y Lema 13.6.3,\(T(M_e, w) \lif E(M_e, w)\) es válido iff se\(M_e\) detiene en la entrada\(w\). Así,\(E\concat D\), dada la entrada\(e\) y se\(w\) detiene con la salida\(1\) iff\(M_e\) se detiene en la entrada\(w\) y se detiene con la salida de\(0\) lo contrario. En otras palabras,\(E \concat D\) resolvería el problema de la detención. Pero sabemos, por el Teorema 13.3.1, que no puede existir tal máquina de Turing. ◻

    This page titled 13.7: El problema de la decisión es irresoluble is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .