Saltar al contenido principal
Library homepage
 
LibreTexts Español

12: Computaciones de la máquina de Turing

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

    • 12.1: Introducción
      ¿Qué significa para una función, digamos, de\(\mathbb{N}\)\(\mathbb{N}\) a para ser computable? Entre las primeras respuestas, y la más conocida, está que una función es computable si puede ser computada por una máquina Turing.
    • 12.2: Representando Máquinas Turing
      Las máquinas de Turing se pueden representar visualmente mediante diagramas de estado. Los diagramas están compuestos por celdas de estado conectadas por flechas.
    • 12.3: Máquinas Turing
      La definición formal de lo que constituye una máquina Turing parece abstracta, pero en realidad es simple: simplemente empaqueta en una estructura matemática toda la información necesaria para especificar el funcionamiento de una máquina Turing. Esto incluye (1) que indica que la máquina puede estar en, (2) qué símbolos pueden estar en la cinta, (3) qué estado debe comenzar la máquina, y (4) cuál es el conjunto de instrucciones de la máquina.
    • 12.4: Configuraciones y cómputos
      Formalmente, podemos definir el cálculo de una máquina de Turing en una entrada dada como una secuencia de configuraciones, y una configuración a su vez es una secuencia de símbolos (correspondiente al contenido de la cinta en un punto dado en el cálculo), un número que indica la posición del cabezal de lectura/escritura y un estado.
    • 12.5: Representación Unaria de Números
      Las máquinas Turing trabajan en secuencias de símbolos escritos en su cinta. Dependiendo del alfabeto que utilice una máquina Turing, estas secuencias de símbolos pueden representar varias entradas y salidas. De particular interés, por supuesto, son las máquinas Turing que computan funciones aritméticas, es decir, funciones de números naturales. Una forma sencilla de representar números enteros positivos es codificándolos como secuencias de un solo símbolo\(1\).
    • 12.6: Estados de detención
      La idea detrás de un estado de detención es simple: cuando la máquina ha terminado de funcionar (está lista para aceptar entrada, o ha terminado de escribir la salida), entra en un estado\(h\) donde se detiene. Algunas máquinas tienen dos estados de detención, uno que acepta entrada y otro que rechaza entrada.
    • 12.7: Combinando Máquinas Turing
      Para construir máquinas Turing más complejas, es importante convencernos de que podemos combinarlas, así podemos construir máquinas para resolver problemas más complejos rompiendo el procedimiento en piezas más simples.
    • 12.8: Variantes de Máquinas Turing
      De hecho, hay muchas formas posibles de definir las máquinas Turing, de las cuales la nuestra es solo una.
    • 12.9: La Tesis Iglesia-Turing
      La Tesis Iglesia-Turing establece que cualquier cosa computable a través de un procedimiento efectivo es Turing computable.
    • 12.10: Resumen


    This page titled 12: Computaciones de la máquina de Turing is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .