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.