Expresión posterior a la década de 1920 Maquina calculadora se refiere a cualquier máquina que realizó un trabajo computadora humana, especialmente a aquellos que han sido desarrollados de acuerdo con métodos efectivos la Iglesia - tesis de Turing. Esta tesis se formula como: "Cualquier algoritmo puede especificarse en la forma de una máquina de Turing correspondiente o una definición parcialmente recursiva, y la clase de funciones computables coincide con la clase de funciones parcialmente recursivas y con la clase de funciones computables en máquinas de Turing . " En otras palabras, la tesis de Church-Turing se define como una hipótesis sobre la naturaleza de los dispositivos informáticos mecánicos, como las computadoras electrónicas. Cualquier cálculo que sea posible se puede realizar en una computadora, siempre que haya suficiente tiempo y espacio de almacenamiento.
Los mecanismos que trabajan en la computación con infinitos se conocieron como el tipo analógico. Los valores en tales mecanismos se representaron mediante valores numéricos continuos, por ejemplo, el ángulo de rotación de un eje o la diferencia en el potencial eléctrico.
A diferencia de las máquinas analógicas, las máquinas digitales tenían la capacidad de representar el estado de un valor numérico y almacenar cada dígito por separado. Las máquinas digitales usaban una variedad de procesadores o relés antes de la invención del dispositivo RAM.
Nombre Maquina calculadora desde la década de 1940, comenzó a ser suplantado por el concepto un ordenador... Esas computadoras pudieron hacer los cálculos que solían hacer los empleados. Desde que los valores ya no dependían de las características físicas (como en las máquinas analógicas), una computadora lógica basada en hardware digital fue capaz de hacer todo lo que se pudiera describir. sistema puramente mecánico .
Las máquinas de Turing fueron diseñadas para definir formalmente matemáticamente lo que se puede calcular dadas las limitaciones de la potencia computacional. Si una máquina de Turing puede completar una tarea, entonces la tarea se considera computable de Turing. Turing se centró principalmente en diseñar una máquina que pudiera determinar qué se podía calcular. Turing concluyó que mientras haya una máquina de Turing que pueda calcular la aproximación de un número, ese valor es contable. Además, la máquina de Turing puede interpretar operadores lógicos como AND, OR, XOR, NOT y If-Then-Else para determinar si
A menudo resolvemos problemas de diversa complejidad: cotidianos, matemáticos, etc. Algunos son fáciles de resolver, otros tenemos que pensar mucho, para otros nunca encontramos una solución.
En el caso general, la forma de resolver el problema (si existe) se puede describir utilizando un número finito de acciones elementales.
Por ejemplo, resolviendo una ecuación cuadrática:
- Lleva la ecuación a la forma canónica \ (a x ^ 2 + b x + c = 0 \)
- Si \ (a = 0 \), entonces esto ecuación lineal con la solución \ (x = \ frac (-c) (b) \). El problema ha sido resuelto. De lo contrario, vaya al paso 3.
- Calcule el discriminante \ (D = b ^ 2-4 a c \)
- Calcula las soluciones de la ecuación \ (x_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \)... El problema ha sido resuelto.
Puede introducir el siguiente concepto intuitivo del algoritmo:
El algoritmo es un conjunto de instrucciones que describen el orden de acciones del ejecutor para lograr el resultado de resolver el problema en un número finito de acciones, para cualquier conjunto de datos iniciales.
Esto, por supuesto, no es una definición estricta, pero describe la esencia del concepto de algoritmo.
Los algoritmos se compilan en función de un ejecutante y, en consecuencia, debe redactarse en un idioma que el intérprete pueda comprender.
El ejecutor del algoritmo puede ser una persona, o puede ser una computadora, o alguna otra máquina, por ejemplo, un telar.
Se destacan las siguientes propiedades de los algoritmos:
La discreción del algoritmo debe ser una cierta secuencia de pasos (acciones) separados y claramente definidos. Cada una de estas acciones debe ser finita en el tiempo. Determinismo en cada paso del algoritmo, el siguiente paso está determinado de forma única por el estado actual del sistema. Como consecuencia, sobre los mismos datos iniciales, el algoritmo devuelve los mismos resultados cada vez, sin importar cuántas veces se ejecute. Comprensibilidad El algoritmo debe formularse en un lenguaje comprensible para el intérprete. Si Viene en una computadora, el algoritmo debe usar solo aquellos comandos que son conocidos por la computadora y cuyo resultado está estrictamente definido. La finitud del algoritmo debe completarse en un número finito de pasos. La masividad del algoritmo debería ser aplicable a diferentes conjuntos de datos de entrada. En otras palabras, el algoritmo debe ser adecuado para resolver clase Tareas. Volviendo al ejemplo cuadrático, el algoritmo es adecuado para resolver de todo ecuaciones cuadráticas, no solo uno o más. La efectividad del algoritmo debe terminar con un resultado determinado. Digamos, resolviendo un problema o descubriendo que no hay soluciones. Si el algoritmo no conduce a un resultado, no está claro por qué es necesario.
No todas las formas de resolver un problema son un algoritmo. Digamos que el algoritmo no implica elección. Por ejemplo, la mayoría de las recetas no son algoritmos porque usan frases como “sal al gusto”. Como consecuencia, se viola el requisito del determinismo.
No para todos los problemas para los que existe una solución, también existe un algoritmo de solución. Por ejemplo, el problema del reconocimiento de imágenes aún está en gran parte sin resolver y, ciertamente, no se utiliza un algoritmo riguroso. Sin embargo, el uso de redes neuronales da muy buenos resultados.
Por lo general, hay conjuntos para el algoritmo. permisible los datos de entrada. Sería extraño intentar usar un algoritmo de resolución de ecuaciones para cocinar la cena, o viceversa.
Además, el conjunto de posibles acciones del ejecutante también es limitado, ya que si se permitiera alguna acción, entonces entre ellas tendría que haber también “inaceptable”.
Definición estricta del algoritmo
La definición del algoritmo anterior no es estricta. Esto crea algunas dificultades. En particular, con tal definición, es imposible probar rigurosamente si una determinada clase de problemas se puede resolver mediante un algoritmo.
Resulta que hay una clase problemas sin solución algorítmica- problemas para los que es imposible componer un algoritmo de solución. Pero para probar rigurosamente la indecidibilidad algorítmica, primero debe tener una definición rigurosa del algoritmo.
En los años 20-30 del siglo XX, varios matemáticos trabajaron en el problema de una definición estricta del algoritmo, en particular Alan Turing, Emil Leon Post, Andrei Andreevich Markov, Andrei Nikolaevich Kolmogorov, Alonzo Church y otros. Su trabajo finalmente condujo al surgimiento y desarrollo de la teoría de algoritmos, la teoría del cálculo y varios enfoques del cálculo y, por cierto, la programación en general. Uno de los resultados de su trabajo fue la aparición de varias definiciones estrictas del algoritmo, introducidas de diferentes formas, pero equivalentes entre sí.
Nos detendremos en detalle en la definición de Turing y analizaremos superficialmente las definiciones equivalentes de Post, Church y Markov.
máquina de Turing
Para introducir una definición formal de un algoritmo, Turing ideó y describió una máquina de computación abstracta llamada máquina de computación de Turing, o simplemente una máquina de Turing.
Alan Turing (1912-1954)
Un matemático, lógico, criptógrafo inglés, posiblemente el primer “hacker” del mundo, estuvo a la vanguardia de la informática y la teoría de la inteligencia artificial. Hizo una contribución significativa a la victoria de las fuerzas aliadas en la Segunda Guerra Mundial.
Los datos de entrada para la máquina de Turing son las palabras compilado con la ayuda de un cierto alfabeto, es decir, el conjunto caracteres.
El resultado del trabajo de la máquina de Turing son también palabras.
La palabra a la que se aplica el algoritmo se llama aporte... La palabra que viene del trabajo fin de semana.
El conjunto de palabras al que se aplica el algoritmo se llama el alcance del algoritmo.
Estrictamente hablando, es imposible probar que cualquier objeto pueda ser representado en forma de palabras compuestas en algún alfabeto; para esto necesitaríamos una definición estricta del objeto. Sin embargo, puede comprobar que cualquier algoritmo aleatorio que funcione con objetos se pueda transformar para que funcione con palabras sin cambiar la esencia del algoritmo.
Descripción de la máquina de Turing
La máquina de Turing incluye una cinta que es ilimitada en ambas direcciones, dividida en celdas, y un dispositivo de control (también llamado cabeza de lectura-escritura, o simplemente máquina), capaz de estar en uno de los muchos estados. El número de estados posibles del dispositivo de control es finito y se especifica con precisión.
El dispositivo de control puede moverse hacia la izquierda y hacia la derecha a lo largo de la cinta, leer y escribir caracteres de algún alfabeto finito en celdas. Se asigna un carácter vacío especial, denotado \ (a_0 \) o \ (\ Lambda \), que llena todas las celdas de la cinta, excepto aquellas de ellas (número finito) en las que se escriben los datos de entrada.
El controlador opera de acuerdo con reglas de transición, que representan el algoritmo implementado por una máquina de Turing determinada. Cada regla de transición indica a la máquina, según el estado actual y el símbolo observado en la celda actual, que escriba un nuevo símbolo en esta celda, cambie a un nuevo estado y mueva una celda hacia la izquierda o hacia la derecha. Algunos estados de la máquina de Turing se pueden marcar como terminales, y la transición a cualquiera de ellos significa el final del trabajo, la parada del algoritmo.
Aunque la máquina de Turing es un concepto abstracto, basta con imaginar una máquina similar (aunque con una cinta finita), e incluso hay máquinas de demostración como esta:
Es conveniente representar el algoritmo para una máquina de Turing en forma de tabla: las columnas de la tabla corresponden al símbolo actual (observado) en la cinta, las filas corresponden al estado actual de la máquina y las celdas contienen el comando que ejecutará la máquina.
El comando, a su vez, puede tener la siguiente estructura:
\ [a_k \ left \ lbrace \ begin (matrix) L \\ N \\ R \ end (matrix) \ right \ rbrace q_m \]
Primero viene el símbolo del alfabeto, que debe estar escrito en la celda actual \ (a_k \), luego se indica el movimiento de la máquina hacia la izquierda (L), hacia la derecha (P) o en ninguna parte (permanecer en el lugar, H) . Al final, se indica un nuevo estado, al que debe ir el autómata \ (q_m \).
La celda de la tabla está claramente definida por el símbolo actual \ (a_i \) y el estado actual de la máquina \ (q_j \).
Acordemos que al comienzo del trabajo, la máquina de Turing está en estado inicial, denotado por \ (q_1 \), y tras la transición a estado de parada\ (q_0 \) el algoritmo se completa y la máquina se detiene.
Ejemplo
Compongamos un algoritmo para una máquina de Turing que agregue 1 a la palabra de entrada, que es un número decimal.
Luego, de manera descriptiva, el algoritmo se puede formular de la siguiente manera:
- Moviéndose hacia la derecha, busque el comienzo de la palabra de entrada
- Moviéndose hacia la derecha, busque el final de la palabra de entrada
- Agregue uno al bit actual de la palabra de entrada. Si hay un número del 0 al 8, salga. De lo contrario, escriba 0, muévase a la izquierda y vuelva al paso 3.
Escribamos este algoritmo en forma de tabla. El alfabeto consta de números del 0 al 9 y un carácter en blanco \ (\ Lambda \). También necesitamos 4 estados del autómata, contando el estado de parada, correspondientes a los pasos en la descripción del algoritmo.
Aceptemos que el estado inicial \ (1 \) es la búsqueda del principio de la palabra de entrada, \ (2 \) es la búsqueda del final de la palabra de entrada, \ (3 \) es la suma de 1.
| \ (_ (q_j) \ barra invertida ^ (a_i) \) | Λ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | ΛП1 | 0H2 | 1H2 | 2H2 | 3H2 | 4H2 | 5H2 | 6H2 | 7H2 | 8H2 | 9H2 |
| 2 | ΛЛ3 | 0P2 | 1P2 | 2P2 | 3P2 | 4P2 | 5P2 | 6P2 | 7P2 | 8P2 | 9P2 |
| 3 | 1S0 | 1S0 | 2H0 | 3H0 | 4H0 | 5H0 | 6H0 | 7H0 | 8H0 | 9H0 | 0L3 |
Rastreemos el funcionamiento de este algoritmo usando un ejemplo. La primera línea corresponde a la cinta, la segunda indica la posición de la máquina y su estado actual.
| 1 | 9 | 9 | ||
| 1 |
En el estado 1, la máquina expendedora está encima de una celda vacía. El comando correspondiente de la tabla “ΛП1”, es decir, dejar la celda vacía, moverse hacia la derecha y permanecer en el estado 1:
| 1 | 9 | 9 | ||
| 1 |
Ahora la máquina observa el valor “1”. Comando correspondiente "1H2", es decir, deje "1" en la celda, no se mueva, y vaya al estado "2":
| 1 | 9 | 9 | ||
| 2 |
En el estado "2", la máquina observa el valor "1". El comando correspondiente "1P2", es decir, dejar "1", moverse hacia la derecha y permanecer en el estado "2":
La situación se repite:
Ahora, en el estado 3 y observando el símbolo “9”, la máquina ejecuta el comando “0L3”:
| 1 | 9 | 0 | ||
| 3 |
La situación se repite:
Estado "0" - estado de parada. El algoritmo se ha completado.
Descripción formal
Matemáticamente, una máquina de Turing se puede describir de la siguiente manera:
Máquina de Turing (MT)
este es un sistema de la forma \ (\ (A, a_0, Q, q_1, q_0, T, \ tau \) \), dónde
- \ (A \) - un conjunto finito de símbolos del alfabeto MT
- \ (a_0 \ in A \) - carácter del alfabeto vacío
- \ (Q \) es un conjunto finito de estados de MT
- \ (q_1 \ in Q \) - estado inicial de MT
- \ (q_0 \ in Q \) - estado final de MT (estado de parada)
- \ (T = \ (A, P, H \) \) es el conjunto de cambios MT
- \ (\ tau \) - Programa MT, es decir, una función que especifica el mapeo \ (\ tau: A \ times Q \ backslash \ (q_0 \) \ rightarrow A \ times T \ times Q \)
La clave en la teoría de los algoritmos es Tesis de Turing.
En términos generales, la tesis de Turing se formula de la siguiente manera:
La tesis de Turing para cualquier problema con solución algorítmica, existe una máquina de Turing que resuelve este problema. de lo contrario, para cualquier algoritmo existe una máquina de Turing equivalente.
La tesis de Turing nos permite hablar de algoritmos utilizando un aparato matemático bastante simple. Además, la propia máquina de Turing es actuador universal, y la mera posibilidad de crear una máquina tan imaginaria se ha convertido en un motivo para hablar sobre la creación de la tecnología informática universal.
Definiciones de algoritmos alternativos
Además de la máquina de Turing, existen varias definiciones independientes que son equivalentes a la definición de Turing.
En particular, la definición a través de la máquina Post, a través del cálculo lambda de Church, el algoritmo de Markov normal.
Consideremos estos métodos.
Máquina de correos
Un año después de Turing, el matemático estadounidense Emile Leon Post propuso de forma independiente otra máquina de computación universal abstracta, algo simplificada en comparación con la máquina de Turing.
La máquina de Post funciona con un alfabeto de dos dígitos y el estado interno de la máquina se reemplaza por línea de programa.
De lo contrario, la máquina de correos es similar a la máquina de Turing: hay un autómata y hay una cinta sin fin con celdas.
La Post Machine puede ejecutar los siguientes comandos:
- Escribe 1, ve a la i-ésima línea del programa
- Escribe 0, ve a la i-ésima línea del programa
- Cambie a la izquierda, vaya a la i-ésima línea del programa
- Cambie a la derecha, vaya a la i-ésima línea del programa
- Salto condicional: si hay 0 en la celda observada, vaya a la línea i-ésima del programa, de lo contrario, vaya a la línea j-ésima del programa.
- Parada.
La máquina de correos también tiene varios comandos prohibidos:
- Escribiendo en la celda 1 cuando ya hay 1.
- Escribiendo en la celda 0 cuando ya hay 0.
Tales eventos conducen a un accidente.
Para escribir programas para la máquina de correos, puede usar la siguiente notación:
- ∨ i - escribe 1, ve a la i-ésima línea del programa
- × i - escribe 0, ve a la i-ésima línea del programa
- ← i - realizar desplazamiento a la izquierda, ir a la línea i-ésima del programa
- → i - realice un cambio a la derecha, vaya a la i-ésima línea del programa
- ? I; j - salto condicional: si hay 0 en la celda observada, vaya a la línea i-ésima del programa, de lo contrario, vaya a la línea j-ésima del programa.
- ! - parada.
Programa de muestra:
1. → 2 2.? 1; 3 3. × 4 4. ← 5 5.!
Este programa borrará la primera etiqueta (1) ubicada a la derecha de la posición de inicio de la máquina y detendrá la máquina en la celda a la izquierda de la misma.
En general, el coche de Post es el predecesor. imperativo lenguajes de programación, por ejemplo, C, Fortran, etc.
La máquina de correos es equivalente a la máquina de Turing. En otras palabras, para cualquier programa de una máquina de Turing, puede escribir un programa equivalente para una máquina de correos y viceversa.
Una de las consecuencias importantes de esta equivalencia es que cualquier alfabeto se puede reducir a código binario.
Similar a la tesis de Turing, también existe la tesis de Post.
En la tesis de Post, cualquier algoritmo se puede representar en forma de máquina Post.
Algoritmo de Markov normal
Los algoritmos normales de Markov están diseñados para aplicarse a palabras en diferentes alfabetos.
La definición de cualquier algoritmo normal consta de dos partes:
- Alfabeto algoritmo
- Esquemas algoritmo
El algoritmo en sí se aplica a palabras, es decir, secuencias de caracteres alfabeto.
El esquema de un algoritmo normal se denomina conjunto ordenado finito de los llamados fórmulas de sustitución, cada uno de los cuales puede ser sencillo o el final... Las expresiones de la forma \ (L \ a D \) se denominan fórmulas de sustitución simple, donde \ (L \) y \ (D \) son dos palabras arbitrarias compuestas del alfabeto del algoritmo (llamadas, respectivamente, izquierda y derecha lados de la fórmula de sustitución). De manera similar, las fórmulas de sustitución final son expresiones de la forma \ (L \ a \ cdot D \), donde \ (L \) y \ (D \) son dos palabras arbitrarias compuestas del alfabeto del algoritmo.
Se supone que los caracteres auxiliares \ (\ to \) y \ (\ to \ cdot \) no pertenecen al alfabeto del algoritmo.
El proceso de aplicar el algoritmo normal a una palabra arbitraria \ (V \) es la siguiente secuencia de acciones:
- Sea \ (V "\) la palabra obtenida en el paso anterior del algoritmo (o la palabra original si el paso actual es el primero).
- Si no hay sustitución entre las fórmulas de sustitución, cuyo lado izquierdo se incluiría en \ (V "\), entonces el trabajo del algoritmo se considera completo y el resultado de este trabajo es la palabra \ (V" \ ).
- De lo contrario, entre las fórmulas de sustitución, cuyo lado izquierdo está incluido en \ (V "\), se selecciona la primera.
- De todas las representaciones posibles de la palabra \ (V "\) en la forma \ (RLS \) (donde \ (R \) es un prefijo y \ (L \) es un sufijo), se elige una tal que \ ( R \) es el más corto seguido de la sustitución \ (V "= RDS \).
- Si la fórmula de sustitución era finita, entonces el algoritmo se completa con el resultado \ (V "\). De lo contrario, vaya al paso 1 (el siguiente paso).
Cualquier algoritmo normal es equivalente a alguna máquina de Turing y viceversa; cualquier máquina de Turing es equivalente a algún algoritmo normal.
Un análogo de la tesis de Turing para los algoritmos normales se suele llamar el principio de normalización.
Ejemplo
Este algoritmo convierte números binarios en "unos" (en los que el registro de un entero no negativo N es una cadena de N barras). Por ejemplo, el número binario 101 se convierte en 5 palos: |||||.
Alfabeto: (0, 1, |) Reglas:
- 1 → 0|
- |0 → 0||
- 0 -> (cadena vacía)
- 0|00|
- 00||0|
- 00|0|||
- 000|||||
- 00|||||
- 0|||||
- |||||
Funciones recursivas
Se puede construir un sistema equivalente a una máquina de Turing sobre la base de funciones matemáticas. Para ello, necesitamos introducir las siguientes clases de funciones:
- funciones recursivas primitivas
- funciones recursivas generales
- funciones parcialmente recursivas
La última clase coincidirá con la clase de funciones computables de Turing (es decir, funciones para cuyo cálculo se puede construir un algoritmo para una máquina de Turing).
La definición de un algoritmo a través de funciones recursivas está de hecho en el corazón del cálculo lambda, y sobre esta base se construye el enfoque programación funcional.
Funciones recursivas primitivas
La clase de funciones recursivas primitivas contiene funciones básicas y todas las funciones derivadas de las base mediante los operadores sustituciones y recursividad primitiva.
Las funciones básicas incluyen:
- La función nula \ (O () = 0 \) es una función sin argumentos que siempre devuelve \ (0 \).
- La función de sucesión \ (S (x) = x + 1 \) es una función que cualquier número natural\ (x \) coincide con el siguiente número \ (x + 1 \)
- Funciones \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), donde \ (0
Para construir el resto de funciones de clase, se utilizan los operadores:
- Sustituciones. Para la función \ (f \) de \ (m \) variables y \ (m \) funciones \ (g_1, \ ldots, g_m \) de \ (n \) variables cada una, el resultado de la sustitución \ (g_k \) en \ (f \) es la función \ (h (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \) de \ (n \) variables.
- Recursión primitiva. Sea \ (f (x_1, \ ldots, x_n) \) una función de \ (n \) variables, y \ (g (x_1, \ ldots, x_ (n + 2)) \) una función de \ (n + 2 \) variables. Entonces, el resultado de aplicar el operador de recursividad primitivo a las funciones \ (f \) y \ (g \) es una función \ (h \) de \ (n + 1 \) variable de la forma: \ [h (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [h (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]
Funciones parcialmente recursivas
La clase de funciones parcialmente recursivas incluye funciones recursivas primitivas y, además, todas las funciones que se obtienen de funciones recursivas primitivas utilizando el operador de minimización de argumentos:
Operador de minimización de argumentos
Sea \ (f \) una función de \ (n \) variables \ (x_i \ in \ mathbb (N) \). Entonces, el resultado de aplicar el operador de minimización de argumentos a la función \ (f \) es la función \ (h \) del argumento \ (n-1 \), definida como:
\ [h (x_1, \ ldots, x_ (n-1)) = \ min y, \] dónde \ Es decir, \ (h \) devuelve el valor mínimo del último argumento a la función \ (f \) en la que \ (f \) es cero.
Si bien las funciones primitivamente recursivas siempre son computables, es posible que las funciones parcialmente recursivas no estén definidas para algunos valores de argumento.
Más estrictamente, las funciones parcialmente recursivas deberían llamarse "funciones recursivas parcialmente definidas", ya que se definen sólo en una fracción de los posibles valores de los argumentos.
Funciones recursivas generales
Las funciones recursivas generales son una subclase de todas las funciones parcialmente recursivas que se definen para cualquier valor de argumento. El problema de determinar si una función parcialmente recursiva dada es recursiva general es algorítmicamente indecidible... Esto nos lleva al tema de la teoría de la computabilidad y el problema de la detención.
La teoría de la computabilidad y el problema de la detención
Nuestra imaginación generalmente permite la existencia de problemas irresolubles, es decir, problemas para los que es imposible componer un algoritmo.
La teoría de la computabilidad se ocupa de estos problemas.
Ejemplos de problemas sin solución algorítmica son detener el problema y problema de reconocimiento de incubabilidad... Considérelos con más detalle.
Problema de parada Con base en la descripción del algoritmo A y los datos de entrada \ (x \), es necesario averiguar si el algoritmo \ (A \) se detiene en los datos de entrada \ (x \).
El problema de la detención no tiene solución algorítmica. Vamos a demostrarlo.
\ (\ Delta \)Sea un algoritmo universal que resuelva el problema de la detención. Considere entonces una clase de algoritmos que procesa textos que describen algoritmos.
Debido a la existencia de un algoritmo universal para resolver el problema de detención, existe un algoritmo que determina si un algoritmo de la clase mencionada se detendrá en su propio texto o no. Denotemos tal algoritmo por \ (B \).
Construyamos el algoritmo \ (C \), cuyos datos de entrada son el texto del algoritmo \ (A \), que procesa su propio texto:
- Ejecute el algoritmo \ (B \) sobre \ (A \).
- Si el algoritmo \ (B \) determina que \ (A \) se detendrá en su texto, vaya al paso 1. De lo contrario, vaya al paso 3.
- Fin del algoritmo \ (C \).
Habiendo intentado aplicar el algoritmo \ (C \) al algoritmo \ (C \), llegamos a una contradicción obvia: si \ (C \) se detiene en su propio texto, entonces no puede detenerse, y viceversa. Por lo tanto, no existe un algoritmo \ (B \). \ (\ no \ Delta \)
Una formulación más general del problema de la detención es el problema de definir la incubabilidad.
Problema de reconocimiento de incubabilidad
Deje que se defina un determinado alfabeto, palabras (fórmulas) de este alfabeto y un sistema de transformaciones formales sobre las palabras de este alfabeto (es decir, se construye un cálculo lógico)
¿Existe para dos palabras \ (R \) y \ (S \) una cadena deductiva que vaya de \ (R \) a \ (S \) dentro del marco de este cálculo lógico?
En 1936, Alonzo Church demostró el teorema de Church.
Teorema de Church El problema de reconocer la deducibilidad no tiene solución algorítmica.
Church usó el formalismo del cálculo lambda para probarlo. En 1937, independientemente de él, Turing demostró el mismo teorema utilizando el formalismo de la máquina de Turing.
Dado que todas las definiciones de algoritmos son equivalentes entre sí, existe un sistema de conceptos que no está asociado con una definición específica de un algoritmo y opera con el concepto función computable.
Función computable Una función que puede ser calculada por un algoritmo.
Existen problemas en los que la relación entre los datos de entrada y salida no se puede describir mediante un algoritmo. Tales funciones son incontestable.
Un ejemplo de una función incuestionable
Tome la función \ (h (n) \) definida para \ (\ forall n \ in \ mathbb (N) \) de la siguiente manera:
\ [h (n) = \ begin (cases) 1, & \ text (si en) \ pi \ text (hay una secuencia de exactamente) n \ text (9-k) \\ 0, & \ text (de lo contrario ) \ end (casos) \]
Podemos obtener el valor \ (1 \) para esta función, sin embargo, para obtener el valor \ (0 \), necesitamos verificar la expansión decimal infinita del número \ (\ pi \), lo cual es obviamente imposible en un tiempo finito. Por tanto, esta función no es computable.
Una de las cuestiones más importantes de la informática moderna es si existe un ejecutor formal con la ayuda del cual se pueda imitar a cualquier ejecutor formal. la respuesta a esta pregunta la obtuvieron casi simultáneamente dos científicos destacados: A. Turing y E. Post. Los intérpretes que proponían diferían entre sí, pero resultó que podían imitarse entre sí y, lo más importante, imitar el trabajo de cualquier intérprete formal.
¿Qué es un contratista formal? ¿Qué significa: un intérprete formal imita el trabajo de otro intérprete formal? Si jugó juegos de computadora, los objetos en la pantalla obedecen los comandos del jugador sin duda. Cada objeto tiene un conjunto de comandos válidos. Al mismo tiempo, la propia computadora es ejecutora, y no virtual, sino real. Entonces resulta que un actor formal imita el trabajo de otro actor formal.
Considere cómo funciona una máquina de Turing.
Una máquina de Turing es una cinta sin fin dividida en celdas y un carro (lector e impresora) que se mueve a lo largo de la cinta.
Por lo tanto, la Máquina de Turing se describe formalmente mediante un conjunto de dos alfabetos:
A = (a1, a2, a3, ..., an) - alfabeto externo, utilizado para registrar los datos iniciales
Q = (q1, q2, q3,…, qm) - alfabeto interno, describe un conjunto de estados del lector y del dispositivo de impresión.
Cada celda de la cinta puede contener un símbolo del alfabeto externo A = (a0, a1, ..., an) (En nuestro caso, A = (0, 1))
Las acciones válidas de la Máquina de Turing son las siguientes:
1) escriba cualquier carácter del alfabeto externo en la celda de la cinta (se sobrescribe el carácter que estaba allí antes)
2) muévete a una celda adyacente
3) cambiar el estado a uno de los indicados por el símbolo del alfabeto interno Q
Una máquina de Turing es una máquina de mesa.
Las filas de la tabla corresponden a los símbolos del alfabeto A seleccionado, y las columnas corresponden a los estados del autómata Q = (q0, q1,…, qm). Al comienzo de la operación, la máquina de Turing se encuentra en el estado q1. El estado q0 es el estado final, una vez que entra en él, el autómata termina su trabajo.
Cada celda de la tabla correspondiente a algún símbolo ai y algún estado qj contiene un comando que consta de tres partes
Un personaje del alfabeto A
· Dirección de movimiento: ">" (a la derecha), "<» (влево) или «.» (на месте)
Nuevo estado de la máquina
En la tabla anterior, el alfabeto A = (0, 1, _) (contiene 3 caracteres) y el alfabeto interior Q = (q1, q2, q3, q4, q0), q0 es el estado que hace que el carro se detenga.
Consideremos varias tareas resolviendo. Puede descargar la máquina de Turing en el sitio web en la sección.
Problema 1. Sea A = (0, 1, _). En la cinta, las celdas contienen caracteres del alfabeto en el siguiente orden: 0011011. El signo de intercalación está encima del primer carácter. Es necesario escribir un programa que reemplace 0 por 1, 1 por 0 y devuelva el carro a su posición original.
Ahora definamos los estados del carro. Yo los llamo "carruaje desea hacer algo".
q1) El carro debe ir hacia la derecha: si ve 0, lo cambia a 1 y permanece en el estado q1, si ve 1 lo cambia a 0 y permanece en el estado q1, si ve _, devuelve 1 celda "quiere algo más", es decir, pasa al estado q2. Escribamos nuestro razonamiento en la tabla del intérprete. Consulte la ayuda del programa para conocer la sintaxis)
q2) Ahora describimos el "deseo de carro" q2. Debemos volver a nuestra posición original. Para hacer esto: si vemos 1, lo dejamos y permanecemos en el estado q2 (con el mismo deseo de llegar al final de la fila de símbolos); si vemos 0, lo dejamos y seguimos moviéndonos hacia la izquierda en el estado q2; vemos que _ - se desplaza 1 celda hacia la derecha. Aquí está donde se requiere en el enunciado del problema. pasamos al estado q0.
Puedes ver el trabajo del programa en el video:
Problema 2. Dado: la secuencia final de 0 y 1 (001101011101). Es necesario escribirlos después de esta secuencia, a través de una celda vacía, y en esta secuencia reemplazarlos con 0. Por ejemplo:
De 001101011101 obtenemos 000000000000 1111111.
Como puede ver, se escriben siete unos después de esta secuencia y en sus lugares hay ceros.
Pongamos manos a la obra. Determine qué estados se necesitan para el transporte y cuántos.
q1) sierra 1 - fíjelo a cero y vaya a otro estado q2 (se introduce un nuevo estado para que el carro no cambie todos los unos a ceros en una pasada)
q2) no cambie nada, vaya al final de la secuencia
q3) tan pronto como el símbolo de intercalación ve una celda vacía, da un paso hacia la derecha y dibuja una, si ve una, luego avanza para firmar el personaje al final. Tan pronto como hayamos dibujado la unidad, pasamos al estado q4
q4) revisamos las unidades escritas sin cambiar nada. Tan pronto como llegamos a la celda vacía que separa la secuencia de unas, pasamos del nuevo estado q5
q5) en este estado vamos al principio de la secuencia sin cambiar nada. Llegamos a una celda vacía, damos la vuelta y vamos al estado q1
El carro asumirá el estado q0 cuando pase en el estado q1 al final de esta secuencia y encuentre una celda vacía.
Obtenemos el siguiente programa:
Puede ver el trabajo de la máquina de Turing en el video a continuación.
Una máquina de Turing es una colección de los siguientes objetos
- 1) alfabeto exterior A = (a 0, a 1,…, a n);
- 2) el alfabeto interno Q = (q 1, q 2,…, q m) es un conjunto de estados;
- 3) un conjunto de caracteres de control (P, L, S)
- 4) una cinta infinita en ambas direcciones, dividida en celdas, en cada una de las cuales en cualquier momento discreto sólo se puede escribir un carácter del alfabeto A;
- 5) un dispositivo de control capaz de estar en uno de muchos estados
El símbolo de una celda vacía es la letra del alfabeto exterior a 0.
Entre los estados, se distingue el q 1 inicial, en el que la máquina comienza a funcionar, y el q 0 final (o estado de parada), en el que la máquina se detiene.
El dispositivo de control puede moverse hacia la izquierda y hacia la derecha a lo largo de la cinta, leer y escribir las letras del alfabeto A en las celdas de la cinta. El dispositivo de control funciona de acuerdo con comandos que se ven así
q yo una j> una p X q k
La entrada significa lo siguiente: si el dispositivo de control está en el estado qi, y la letra aj está escrita en la celda observada, entonces (1) ap se escribe en la celda en lugar de aj, (2) la máquina pasa a la siguiente celda derecha de la que se acaba de ver, si X = P, o para ver la siguiente celda izquierda, si X = L, o continúa examinando la misma celda de la cinta, si X = C, (3) el dispositivo de control entra en el estado q k.
Dado que el funcionamiento de la máquina, por condición, está completamente determinado por su estado q, en este momento y el contenido de la celda que se está viendo en este momento, entonces para cada configuración posible q i a j hay exactamente una regla. No hay reglas solo para el estado final, en el que el automóvil se detiene. Por lo tanto, un programa de máquina de Turing con alfabeto externo A = (a0, a1,…, an) e interno Q = (q1, q2,…, qm) contiene como máximo m (n + 1) instrucciones.
Una palabra en el alfabeto A o en el alfabeto Q, o en el alfabeto A Q es cualquier secuencia de letras del alfabeto correspondiente. Por k-ésima configuración nos referimos a la imagen de la cinta de la máquina con la información formada en ella al comienzo del k-ésimo paso (o una palabra del alfabeto A escrita en la cinta al comienzo de la k-ésima) th paso), que indica qué celda se está viendo en este paso y en qué estado se encuentra el automóvil. Solo las configuraciones finales tienen sentido, es decir aquellos en los que todas las celdas de la cinta, con la posible excepción de un número finito, están vacías. Una configuración se llama final si el estado en el que se encuentra la máquina es definitivo.
Si elegimos alguna configuración no final de la máquina de Turing como inicial, entonces el trabajo de la máquina será transformar secuencialmente (paso a paso) la configuración inicial de acuerdo con el programa de la máquina hasta alcanzar la configuración final. . Después de eso, el trabajo de la máquina de Turing se considera completado y el resultado del trabajo es la configuración final lograda.
Diremos que una palabra b no vacía en el alfabeto A (a 0) = (a 1, ..., an) es percibida por la máquina en la posición estándar, si se escribe en celdas sucesivas de la cinta, todas las demás celdas están vacías y la máquina mira la celda más a la izquierda o la más a la derecha de aquellas en las que está escrita la palabra b. La posición estándar se denomina posición inicial (final) si la máquina, que percibe la palabra en la posición estándar, se encuentra en el estado inicial q 1 (respectivamente, en el estado de parada q 0).
Si el procesamiento de la palabra b transfiere la máquina de Turing al estado final, entonces se dice que es aplicable a b, de lo contrario no es aplicable a b (la máquina funciona indefinidamente)
Consideremos un ejemplo:
Dada una máquina de Turing con un alfabeto externo A = (0, 1) (aquí 0 es el símbolo de una celda vacía), un alfabeto de estados internos Q = (q 0, q 1, q 2) y con el siguiente diagrama funcional (programa):
q 1 0> 1 L q 2;
q 1 1> 0 C q 2;
q 2 0> 0 P q 0;
q 2 1> 1 C q 1;
Este programa se puede escribir usando una tabla
En el primer paso, opera el siguiente comando: q 1 0> 1 Л q 2 (el dispositivo de control está en el estado q1, y la letra 0 está escrita en la celda observada, 1 está escrita en la celda en lugar de 0, la el cabezal se desplaza hacia la izquierda, el dispositivo de control pasa al estado q2), en Como resultado, se crea la siguiente configuración en la máquina:
Finalmente, luego de ejecutar el comando q 2 0> 0 P q 0, se crea la configuración
Esta configuración es definitiva, porque la máquina estaba en estado de parada q 0.
Por tanto, la máquina procesa la palabra original 110 en la palabra 101.
La secuencia resultante de configuraciones se puede escribir de una manera más corta (el contenido de la celda observada se escribe a la derecha del estado en el que se encuentra actualmente la máquina):
11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1
Una máquina de Turing no es más que una regla (algoritmo) para transformar palabras del alfabeto A Q, es decir, configuraciones. Por lo tanto, para definir una máquina de Turing, debe especificar sus alfabetos externos e internos, un programa e indicar cuál de los símbolos denota una celda vacía y el estado final.
Máquina de Turing (MT)- ejecutor abstracto (máquina de computación abstracta). Alan Turing lo propuso en 1936 para formalizar el concepto de algoritmo.
Una máquina de Turing es una extensión de una máquina de estados finitos y, según la tesis de Church-Turing, capaz de imitar a todos los intérpretes(especificando reglas de transición) que de alguna manera implementan el proceso de cálculo paso a paso, en el que cada paso del cálculo es bastante elemental.
Es decir, cualquier algoritmo intuitivo se puede implementar usando alguna máquina de Turing.
YouTube colegiado
1 / 5
✪ 09 - Introducción a los algoritmos. máquina de Turing
✪ Máquina de Turing - Alexander Shen
✪ Clase 20: Máquina de Turing
✪ Máquina de Turing. Ejemplo de trabajo
✪ 16 - Computabilidad. Máquinas de Turing. Motivación y ejemplos
Subtítulos
Estructura de la máquina de Turing
La máquina de Turing incluye un ilimitado en ambas direcciones cinta(Son posibles las máquinas de Turing, que tienen varias cintas infinitas), divididas en celdas, y dispositivo de control(también llamado cabeza de lectura-escritura (GZCH)), capaz de estar en uno de conjunto de estados... El número de estados posibles del dispositivo de control es finito y se especifica con precisión.
El dispositivo de control puede moverse hacia la izquierda y hacia la derecha a lo largo de la cinta, leer y escribir caracteres de algún alfabeto finito en celdas. Destaca especial vacío un carácter que llena todas las celdas de la cinta, excepto aquellas de ellas (número finito), en las que se escriben los datos de entrada.
El dispositivo de control opera de acuerdo con reglas de transición que representan el algoritmo, realizable esta máquina de Turing. Cada regla de transición indica a la máquina, según el estado actual y el símbolo observado en la celda actual, que escriba un nuevo símbolo en esta celda, cambie a un nuevo estado y mueva una celda hacia la izquierda o hacia la derecha. Algunos estados de la máquina de Turing pueden etiquetarse como Terminal, y la transición a cualquiera de ellos significa el final del trabajo, la parada del algoritmo.
La máquina de Turing se llama determinista si como máximo una regla corresponde a cada combinación de estado y símbolo de franja en la tabla. Si hay un par "símbolo rayado - estado" para el que hay 2 o más instrucciones, dicha máquina de Turing se llama no determinista.
Descripción de la máquina de Turing
Una máquina de Turing específica se especifica enumerando los elementos del conjunto de letras del alfabeto A, el conjunto de estados Q y un conjunto de reglas según las cuales opera la máquina. Tienen la forma: qiaj → q i1 a j1 dk (si la cabeza está en el estado qi, y la letra aj está escrita en la celda observada, entonces la cabeza entra en el estado q i1, una j1 está escrita en la celda en lugar de aj, la cabeza hace un movimiento dk, que tiene tres opciones: una celda a la izquierda (L), una celda a la derecha (R), permanecer en su lugar (N)). Para cada configuración posible hay exactamente una regla (para una máquina de Turing no determinista, puede haber gran cantidad normas). No hay reglas solo para el estado final, en el que el automóvil se detiene. Además, debe especificar los estados de inicio y finalización, la configuración inicial en la banda y la ubicación del cabezal de la máquina.
Un ejemplo de una máquina de Turing
Demos un ejemplo de MT para multiplicar números en el sistema numérico unario. El registro de la regla "qiaj → q i1 a j1 R / L / N" debe entenderse de la siguiente manera: qi es el estado en el que se ejecuta esta regla, aj son los datos de la celda en la que se encuentra el cabezal, q i1 es el estado al que es necesario ir, un j1 - lo que debe escribirse en la celda, R / L / N - comando de movimiento.
La máquina funciona de acuerdo con el siguiente conjunto de reglas:
| q 0 | q 1 | q 2 | q 3 | q 4 | q 5 | q 6 | q 7 | q 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 1 | q 0 1 → q 0 1R | q 1 1 → q 2 aR | q 2 1 → q 2 1L | q 3 1 → q 4 aR | q 4 1 → q 4 1R | q 7 1 → q 2 aR | |||
| × | q 0 × → q 1 × R | q 2 × → q 3 × L | q 4 × → q 4 × R | q 6 × → q 7 × R | q 8 × → q 9 × N | ||||
| = | q 2 = → q 2 = L | q 4 = → q 4 = R | q 7 = → q 8 = L | ||||||
| a | q 2 a → q 2 aL | q 3 a → q 3 aL | q 4 a → q 4 aR | q 6 a → q 6 1R | q 7 a → q 7 aR | q 8 a → q 8 1L | |||
| * | q 0 * → q 0 * R | q 3 * → q 6 * R | q 4 * → q 5 1R | ||||||
| q 5 → q 2 * L |
Descripción de estados:
| Comienzo | |
| q 0 | estado inicial. Buscamos la "x" a la derecha. Cuando se encuentra, vamos al estado q1 |
|---|---|
| q 1 | reemplace "1" con "a" y vaya al estado q2 |
| Transferir todos los "1" del primer número al resultado | |
| q 2 | buscando "x" a la izquierda. Cuando se encuentra, vamos al estado q3 |
| q 3 | buscamos "1" a la izquierda, lo reemplazamos con "a" y vamos al estado q4. Si "1" ha terminado, buscamos "*" y vamos al estado q6 |
| q 4 | vaya al final (buscando "*" a la derecha), reemplace "*" con "1" y vaya al estado q5 |
| q 5 | agregue "*" al final y vaya al estado q2 |
| Procesamos cada dígito del segundo número | |
| q 6 | busque "x" a la derecha y vaya al estado q7. Mientras miramos, reemplazamos "a" con "1" |
| q 7 | buscando "1" o "=" a la derecha al encontrar "1" lo reemplazamos con "a" y vamos al estado q2 cuando se encuentra "=", pasamos al estado q8 |
| Fin | |
| q 8 | buscando "x" a la izquierda. Cuando se encuentra, pasamos al estado q9. Mientras miramos, reemplazamos "a" con "1" |
| q 9 | estado terminal (algoritmo de parada) |
Multiplica 3 por 2 con la ayuda de MT en el sistema de unidades. El protocolo indica los estados inicial y final del MT, la configuración inicial en la correa y la ubicación del cabezal de la máquina (símbolo subrayado).
Comienzo. Estamos en el estado q 0, ingresamos los datos en la máquina: * 111x11 = *, el cabezal de la máquina se encuentra en el primer carácter *.
1er paso. Veamos la tabla de reglas de lo que hará la máquina cuando esté en el estado q 0 y encima del símbolo "*". Esta es una regla de la primera columna de la quinta fila: q 0 * → q 0 * R. Esto quiere decir que pasamos al estado q 0 (es decir, no lo cambiamos), el símbolo pasa a ser "*" (es decir, no cambia) y nos movemos a lo largo del texto que ingresamos "* 111x11 = *" a la derecha una posición (R), luego está en el 1er carácter 1. A su vez, el estado q 0 1 (1ª columna 1ª fila) es procesado por la regla q 0 1 → q 0 1R. Es decir, nuevamente hay simplemente una transición hacia la derecha en 1 posición. Esto sucede hasta que nos encontramos en el símbolo "x". Y así sucesivamente: tomamos el estado (índice en q), tomamos el símbolo en el que estamos (símbolo subrayado), los conectamos y observamos el procesamiento de la combinación resultante de acuerdo con la tabla de reglas.
En palabras simples, el algoritmo de multiplicación es el siguiente: marque la primera unidad del segundo factor, reemplácela con la letra "a" y transfiera todo el primer factor detrás del signo igual. La transferencia se lleva a cabo reemplazando alternativamente las unidades del primer factor con "a" y agregando el mismo número de unidades al final de la línea (a la izquierda del "*" más a la derecha). Luego cambiamos toda la "a" al signo de multiplicación "x" de nuevo a unidades. Y el ciclo se repite. De hecho, después de todo, A multiplicado por B se puede representar como A + A + A B veces. Ahora marcamos la 2ª unidad del 2º factor con la letra "a" y volvemos a transferir las unidades. Cuando no hay unidades antes del signo "=", la multiplicación está completa.
Completitud de Turing
Podemos decir que una máquina de Turing es la máquina de computación más simple con memoria lineal que, de acuerdo con reglas formales, transforma los datos de entrada usando la secuencia acciones elementales.
La naturaleza elemental de las acciones radica en el hecho de que la acción cambia solo una pequeña parte de los datos en la memoria (en el caso de una máquina de Turing, solo una celda), y el número de acciones posibles es finito. A pesar de la simplicidad de la máquina de Turing, se puede utilizar para calcular todo lo que se puede calcular en cualquier otra máquina que realice cálculos utilizando una secuencia de acciones elementales. Esta propiedad se llama lo completo.
Una de las formas naturales de demostrar que los algoritmos computacionales que se pueden implementar en una máquina se pueden implementar en otra es imitar la primera máquina en la segunda.
La imitación es la siguiente. Se proporciona una descripción del programa (reglas de funcionamiento) de la primera máquina a la entrada de la segunda máquina. D (\ Displaystyle D) y datos de entrada X (\ Displaystyle X), que se suponía que llegarían a la entrada del primer coche. Es necesario describir dicho programa (las reglas para el funcionamiento de la segunda máquina) para que, como resultado de los cálculos, la salida resulte ser la misma que devolvería la primera máquina si recibiera datos como entrada. X (\ Displaystyle X).
Como se dijo, en una máquina de Turing es posible simular (estableciendo reglas de transición) todos los demás ejecutores que de alguna manera implementan el proceso de cálculo paso a paso, en el que cada paso del cálculo es bastante elemental.
En una máquina de Turing, puede imitar una máquina Post, los algoritmos normales de Markov y cualquier programa para computadoras ordinarias que convierta los datos de entrada en salidas utilizando algún algoritmo. A su vez, la Máquina de Turing se puede imitar en varios artistas abstractos. Los artistas intérpretes o ejecutantes para quienes esto es posible se llaman Turing completo(Turing completo).
Existen programas para computadoras ordinarias que simulan el funcionamiento de una máquina de Turing. Pero cabe señalar que esta imitación es incompleta, ya que hay una cinta infinita abstracta en la máquina de Turing. Una cinta sin fin con datos no se puede simular completamente en una computadora con memoria finita (la memoria total de la computadora es RAM, discos duros, varios medios de almacenamiento externos, registros y caché del procesador, etc. - pueden ser muy grandes, pero siempre finitos).
Variantes de la máquina de Turing
El modelo de la máquina de Turing es extensible. Podemos considerar máquinas de Turing con un número arbitrario de cintas y cintas multidimensionales con varias restricciones. Sin embargo, todas estas máquinas son Turing completas y están modeladas por una máquina Turing convencional.
Máquina de Turing que se ejecuta en un cinturón semi-infinito
Como ejemplo de tal reducción, considere el siguiente teorema: Para cualquier máquina de Turing, existe una máquina de Turing equivalente que opera en una cinta semi-infinita (es decir, en una cinta que es infinita en una dirección).
Considere la prueba dada por Yu. G. Karpov en el libro "Teoría de los Autómatas". La demostración de este teorema es constructiva, es decir, daremos un algoritmo mediante el cual se puede construir una máquina de Turing equivalente con la propiedad declarada para cualquier máquina de Turing. Primero, numeramos arbitrariamente las celdas de la cinta de trabajo MT, es decir, definimos la nueva ubicación de la información en la cinta:
Luego volveremos a numerar las celdas y asumiremos que el símbolo "*" no está contenido en el diccionario MT:
Finalmente, cambiamos la máquina de Turing duplicando el número de sus estados y cambiamos el desplazamiento del cabezal de lectura-escritura para que en un grupo de estados la operación de la máquina sea equivalente a su operación en el área sombreada y en el otro grupo de estados la máquina funcionaría como lo hace la máquina original en el área no sombreada. Si durante la operación de MT se encuentra el símbolo '*', entonces el cabezal de lectura-escritura ha alcanzado el límite de la zona:
El estado inicial de la nueva máquina de Turing se establece en una u otra zona, dependiendo de qué parte de la cinta original era el cabezal de lectura y escritura en la configuración original. Obviamente, a la izquierda de los marcadores delimitadores "*", la cinta no se utiliza en la máquina de Turing equivalente.
Máquinas de Turing bidimensionales
- Hormiga de Langton
ver también
- Simulador de programa multiplataforma JFLAP de autómatas, máquinas de Turing, gramáticas, dibuja un gráfico de autómatas