Saltar al contenido principal
LibreTexts Español

13: Indecibilidad

  • Page ID
    103653
  • \( \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}}\)

    • 13.1: Introducción
      Una cosa es no poder imaginar cómo se computarían funciones complicadas, y otra muy distinta demostrar realmente que son incomputables.
    • 13.2: Enumeración de Máquinas Turing
      Podemos demostrar que el conjunto de todas las máquinas Turing es contable. Esto se deduce del hecho de que cada máquina Turing puede describirse finitamente.
    • 13.3: El problema de la detención
      El problema de la detención es un ejemplo de una clase más grande de problemas de la forma “\(X\)se pueden lograr usando máquinas Turing”. (La respuesta es no: el problema de la detención es irresoluble).
    • 13.4: El problema de la decisión
      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.
    • 13.5: Representando Máquinas Turing
      Para representar las máquinas Turing y su comportamiento mediante una frase de lógica de primer orden, tenemos que definir un lenguaje adecuado. El lenguaje consta de dos partes: símbolos predicados para describir configuraciones de la máquina, y expresiones para numerar pasos de ejecución (“momentos”) y posiciones en la cinta.
    • 13.6: Verificación de la Representación
      Para verificar que nuestra representación funcione, tenemos que probar dos cosas. Primero, tenemos que demostrar que si se\(M\) detiene en la entrada\(w\), entonces\(T(M, w) \rightarrow E(M, w)\) es válido. Entonces, tenemos que mostrar lo contrario, es decir, que si\(T(M, w) \rightarrow E(M, w)\) es válido, entonces\(M\) de hecho finalmente se detiene cuando se ejecuta en la entrada\(w\).
    • 13.7: El problema de la decisión es irresoluble
      Si el problema de decisión fuera solucionable, podríamos usarlo para resolver el problema de detención.
    • 13.8: Resumen


    This page titled 13: Indecibilidad is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .