Saltar al contenido principal
LibreTexts Español

13.4: El problema de la decisión

  • Page ID
    103661
  • \( \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

    Decimos que la lógica de primer orden es decidible si existe un método efectivo para determinar si una oración dada es válida o no. Resulta que no existe tal método: el problema de decidir la validez de las oraciones de primer orden es irresoluble.

    Para establecer este importante resultado negativo, demostramos que el problema de decisión no puede ser resuelto por una máquina Turing. Es decir, demostramos que no existe una máquina de Turing que, cada vez que se inicia en una cinta que contiene una oración de primer orden, eventualmente se detiene y da salida\(1\) o bien o\(0\) dependiendo de si la oración es válida o no. Por la tesis Church-Turing, cada función que es computable es Turing computable. Entonces, si esta “función de validez” fuera efectivamente computable en absoluto, sería Turing computable. Si no es Turing computable, entonces, tampoco puede ser efectivamente computable.

    Nuestra estrategia para demostrar que el problema de decisión es irresoluble es reducir el problema de detención a él. Esto significa lo siguiente: Hemos demostrado que la función\(h(e,w)\) que se detiene con salida\(1\) si la máquina Turing descrita por se\(e\) detiene en entrada\(w\) y salidas de\(0\) lo contrario, no es Turing computable. Mostraremos que si hubiera una máquina de Turing que decida validez de oraciones de primer orden, entonces también está la máquina de Turing que calcula\(h\). Dado que\(h\) no puede ser computada por una máquina de Turing, tampoco puede haber una máquina de Turing que decida la validez.

    El primer paso en esta estrategia es mostrar que para cada entrada\(w\) y una máquina de Turing\(M\), podemos describir efectivamente una oración\(T(M, w)\) que representa el conjunto de instrucciones de\(M\) y la entrada\(w\) y una oración \(E(M, w)\)expresando “\(M\)eventualmente se detiene” de tal manera que:

    \(\Entails T(M, w) \lif E(M,w)\)iff\(M\) se detiene para la entrada\(w\).

    El grueso de nuestra prueba consistirá en describir estas oraciones\(T(M, w)\)\(E(M, w)\) y verificar que\(T(M, w) \lif E(M, w)\) es válido si se\(M\) detiene en la entrada\(w\).


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