Presentación de máquinas algorítmicas. máquina de Turing

El desarrollo metodológico de la lección, que será discutido en esta publicación, está destinado a ser estudiado en el grado 10 al considerar el bloque temático " Algoritmo. Ejecutores de algoritmos».

En la lección sobre el tema " »Acompañado de una presentación multimedia, los niños se familiarizarán con su estructura, estudiarán el principio de funcionamiento y aprenderán a construir un programa para una máquina de Turing. El material didáctico permite desarrollar el pensamiento algorítmico de los estudiantes de último año, la capacidad de formalizar.

Por tipo, se combina esta lección, en la que se consolida el estudio de nuevo material en el proceso de resolución de problemas sobre el tema. El autor del desarrollo propone utilizar un método de enseñanza de búsqueda parcial, cuando el proceso de pensamiento se vuelve productivo con la dirección y el control constante del maestro.

Descripción del curso de la lección sobre la máquina de Turing.

En la etapa de organización de la clase, el maestro prepara a los niños para el trabajo, formula el tema de la lección y habla sobre el inglés Alan Turing, quien influyó significativamente en el desarrollo de la informática como ciencia.

Como calentamiento en la siguiente etapa de la lección, los estudiantes deciden tarea lógica seguido de un cheque en el tablero. Es importante prestar atención a la capacidad de elaborar un algoritmo de razonamiento.

Habiendo lidiado con la tarea de calentamiento, actualizamos el pasado previamente. material teórico sobre el algoritmo y los ejecutores de los algoritmos. Para ello, el autor del desarrollo propone realizar una encuesta frontal sobre las siguientes cuestiones:

¿Qué se llama un algoritmo y para quién está destinado?

¿Qué propiedades tiene el algoritmo?

¿Quién puede aparecer como ejecutor del algoritmo?

¿Cuáles son los conceptos básicos de la máquina de Turing?

Demuestre las principales propiedades de los algoritmos utilizando un ejemplo de una máquina de Turing.

Ejemplos de máquinas de Turing - parte teórica

Antes de proceder a la resolución de problemas sobre el tema, en la parte teórica damos una descripción de la máquina de Turing. Llamamos la atención de la clase sobre dos componentes de cualquiera de estas máquinas:

1) la cinta es ilimitada y está dividida en celdas;
2) un cabezal controlado por programa que lee información y llamado autómata.

Reemplazar una letra del alfabeto contenida en la celda de memoria visible por otra;

Desplácese hacia la derecha o hacia la izquierda con un intervalo de una celda, o permanezca en el mismo lugar;

Cambia tu propio estado interior.

Resolver problemas usando máquinas de Turing

La siguiente etapa de la lección implica la inmersión en la parte práctica de la lección y la resolución de problemas sobre el tema. El profesor dice que con la ayuda de una máquina de Turing, es necesario intentar simular un dispositivo similar a una calculadora. En total, se proponen dos tareas, cuyo análisis se realiza acompañado de diapositivas de presentación:

Objetivo 1. La cinta de la máquina de Turing contiene un número decimal. Es necesario agregar a este número 1 ( unidad). En este caso, el autómata examina un cierto dígito correspondiente al número de entrada.

Definición de una máquina de Turing

Una máquina de Turing es un ejecutor abstracto que implementa un proceso algorítmico diseñado para refinar el concepto de un algoritmo. Es un objeto matemático, no una máquina física. Propuesto por Alan Turing en 1936, la Máquina de Turing es una construcción matemática rigurosa, un aparato matemático diseñado para resolver ciertos problemas.

Estructura y descripción de una máquina de Turing Una máquina de Turing consta de: una cinta sin fin dividida en celdas; carro (cabezal de lectura y escritura); máquina programable (programa en forma de tabla). La máquina "ve" sólo una celda cada vez. Dependiendo de la letra que vea, así como de su estado q, el autómata puede realizar las siguientes acciones: escribir una nueva letra en la celda observada; realice un desplazamiento a lo largo de la cinta una celda hacia la derecha / izquierda o permanezca inmóvil; ir a un nuevo estado.

1) Alfabeto externo A = (a 0, a 1, ..., a n) El elemento a 0 se denomina símbolo vacío o letra vacía (una señal de que la celda está vacía). En este alfabeto, el conjunto de datos original y el resultado de la operación del algoritmo están codificados en forma de palabra. Estructura de la máquina de Turing

2) Alfabeto interno Q = (q 0, q 1,…, qm), (P, L, N!) En cualquier momento, la máquina de Turing se encuentra en uno de los estados q 0, q 1,…, qm En este caso: q 1 - estado inicial (la máquina comienza a trabajar) q 0 - estado final (la máquina ha terminado de trabajar) Símbolos (P, L, N!) - símbolos de cambio (derecha, izquierda, en su lugar) Estructura de la máquina de Turing

Tipos de comandos de la máquina de Turing Escribir una nueva letra en la celda observada Desplazarse a lo largo de la cinta una celda hacia la derecha / izquierda o permanecer en su lugar (P, L, N) Ir a un nuevo estado. a 0 a 1… a i… a j q 0 q 1… a k (LPN) q m q i… q j 1 1 1 * 1 1 Indicación de cambio de símbolo Indicación de cambio de carro Indicación de cambio de estado interno

3) Memoria externa (cinta) La máquina tiene una cinta dividida en celdas, cada una de las cuales puede contener solo una letra. Estructura de la máquina de Turing

3) Memoria externa (cinta) Estructura de la máquina de Turing Una celda vacía contiene un 0. En cada momento se graba en la cinta un número finito de letras no vacías, la cinta es finita, pero en cualquier momento se complementa con celdas a izquierda y derecha para registrar nuevos caracteres no vacíos. Esto está en línea con el principio de abstracción de viabilidad potencial

4) Carro (cabezal de control) El carro de la máquina está ubicado sobre una celda determinada de la cinta - percibe el carácter escrito en la celda.En un ciclo de trabajo, el carro se desplaza una celda (derecha, izquierda) o permanece en su lugar. El dispositivo de la máquina de Turing

5) Diagrama funcional (programa) El programa de la máquina consta de instrucciones: Estructura de la máquina de Turing Para cada par (q i, a j), el programa de la máquina debe contener una instrucción (máquina de Turing determinista)

Al comienzo de la operación de la máquina, el conjunto de datos inicial se alimenta a la cinta en forma de la palabra  Descripción de la operación de la máquina de Turing Diremos que una palabra no vacía  en el alfabeto A \ (a 0) es percibido por la máquina en su posición estándar si: - se da en celdas consecutivas de la cinta, - todas las demás celdas están vacías - el automóvil está mirando la celda más a la derecha de las que contienen la palabra 

Descripción del funcionamiento de la máquina de Turing 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 (estado de parada q 0)

Estando en un estado no final, la máquina da un paso, que está determinado por el estado actual q i y el símbolo monitoreado a j Descripción del funcionamiento de la máquina de Turing

Descripción del funcionamiento de la máquina de Turing De acuerdo con el comando qiaj  qkal X, se realizan las siguientes acciones: 1) Se borra el contenido de la celda observada aj y se escribe en ella el símbolo al (que puede coincidir con aj) 2) La máquina entra en un nuevo estado qk (puede coincidir con el estado qi) 3) El carro se mueve de acuerdo con el carácter controlado X  (¡P, L, N!)

Cuando la máquina entra en el estado final q 0, su operación se detiene La cinta contiene el resultado de la operación del algoritmo - la palabra  en el alfabeto A \ (a 0) Descripción de la operación de la máquina de Turing

Una palabra de máquina (configuración) de una máquina de Turing es una palabra de la forma  1 q k a l  2, donde  1 y  2 son palabras del alfabeto A.

La configuración  1 q k a l  2 se interpreta de la siguiente manera: - la máquina está en el estado q k - el carro está observando el símbolo a l en la cinta -  1 y  2 - este es el contenido de la cinta antes y después del símbolo a l

Situaciones de inaplicabilidad de una máquina de Turing Se considera que una máquina de Turing es inaplicable a una palabra de entrada dada si no hay celdas de parada en el programa o la máquina no las golpea durante el funcionamiento. Por ejemplo: Una máquina de Turing es aplicable a una palabra de entrada dada si, habiendo comenzado a trabajar en esta palabra de entrada, tarde o temprano llega a una de las celdas de detención. ¿Cómo ha cambiado el programa de ejemplo? a 0 0 1 q 1 1P q 1 0P q 1 1P q 1 a 0 0 1 q 1 1H q 0 0P q 1 1P q 1

Un ejemplo de máquinas de Turing Se requiere construir una máquina de Turing para resolver el siguiente problema: en la palabra de entrada, reemplace todas las letras "a" por las letras "b" y viceversa. a 0 a b c ... yo q 1 a 0 H! b L q 1 a L q 1 c L q 1 ... i L q 1 y  y segundo  a a  b r  r u b a r a b a  b b  a a b b a

Implementar el algoritmo propuesto Una máquina de Turing agrega uno al número en la cinta. La palabra de entrada consta de dígitos enteros decimal escrito en celdas consecutivas en una cinta. En el momento inicial, el automóvil está ubicado frente al dígito más a la derecha del número. a 0 0 1 2 3 4 ... 7 8 9 q 1 1H q 0 1H q 0 2H q 0 3H q 0 4H q 0 5H q 0 ... 8H q 0 9H q 0 0L q 1

Implementar el algoritmo propuesto La cinta de la máquina de Turing contiene una secuencia de símbolos "+". La máquina de Turing reemplaza cada segundo símbolo "+" con "-". El reemplazo comienza en el extremo derecho de la secuencia. El autómata en el estado q 1 mira uno de los símbolos de la secuencia especificada. una 0 + - q 1 una 0 L q 2 + P q 1 q 2 una 0 H! + Л q 3 q 3 а 0 Н! - Л q 2 q 1 - la máquina está buscando el extremo derecho del número; q 2 - salta el signo "+", al llegar al final de la secuencia - parada; q 3 - el signo "+" se sustituye por "-".

Ejemplo Dada una máquina de Turing con un alfabeto externo A = (a 0, 1, *), un alfabeto de estados internos Q = (q 0, q 1, q 2, q 3) y el siguiente diagrama funcional: Aplicar el Turing máquina a la palabra  = 11 * 1 a partir de la posición inicial estándar

Solución 1) Reemplace el contenido de la celda 1 observada con un 0

Solución 2) La máquina entra en un nuevo estado q 2

Solución 3) El carro se mueve hacia la izquierda

Solución Solución completa y detallada

Solución Solución completa y detallada

Solución Solución escrita con configuraciones (en línea)

 = 1 * 11 Respuesta:  = 111

Literatura Igoshin V.I. Lógica matemática y teoría de algoritmos. - M .: Academy, 2008 .-- 448 p. Likhtarnikov L.M., Sukacheva T.G. Lógica matemática. Curso de conferencias. Libro de problemas prácticos y soluciones. - SPb.: Lan, 1999 .-- 288 p. Ilinykh A.P. Teoría de algoritmos. Tutorial... - Ekaterimburgo, 2006 .-- 149 p.

Las personas pueden comportarse de manera diferente en las mismas situaciones, y en esto son fundamentalmente diferentes de las máquinas.

Alan Turing

Alan Mathison Turing Alan Mathison Turing (inglés Alan Mathison Turing; 23 de junio de 1912 - 7 de junio de 1954) - matemático, lógico, criptógrafo inglés, que tuvo un impacto significativo en el desarrollo de la informática. Comendador de la Orden del Imperio Británico (1945), Miembro de la Royal Society of London (1951). La computación abstracta "Máquina de Turing" propuesta por él en 1936, que puede considerarse un modelo informático de propósito general, permitió formalizar el concepto de algoritmo y todavía se utiliza en muchos estudios teóricos y prácticos. Trabajos científicos A. Turing es una contribución reconocida a los fundamentos de la informática (y, en particular, la teoría de la inteligencia artificial).

Tiempo de guerra Durante la Segunda Guerra Mundial, Alan Turing trabajó en la Escuela de Códigos y Cifras del Gobierno ubicada en Bletchley Park, donde se concentró el trabajo de descifrado de cifrados y códigos del Eje. Lideró el grupo Hut 8, que se encarga del criptoanálisis de los mensajes de la Armada alemana. Turing desarrolló una serie de técnicas de piratería, incluida la base teórica de Bombe, la máquina utilizada para piratear el dispositivo de cifrado alemán Enigma.

Máquina de Turing A las pocas semanas de llegar a Blatchley Park, Turing escribió especificaciones para una máquina electromecánica que podría ayudar a romper el Enigma de manera más efectiva que la bomba de criptología polaca. La máquina de Turing, con las mejoras propuestas por el matemático Gordon Welchman, se ha convertido en una herramienta imprescindible para descifrar los mensajes de Enigma. El coche se llamaba Bombe. La máquina buscó posibles configuraciones utilizadas para cifrar mensajes (orden del rotor, posición del rotor, conexiones del panel de conexiones) basándose en texto plano conocido. Para cada ajuste posible del rotor (que tenía 1019 estados o 1022 en la modificación utilizada en los submarinos), la máquina hizo una serie de suposiciones lógicas basadas en el texto sin formato (su contenido y estructura). Luego, la máquina identificó la contradicción, descartó el conjunto de parámetros y pasó al siguiente. Por lo tanto, se eliminaron la mayoría de los conjuntos posibles y solo quedaron unas pocas opciones para un análisis cuidadoso. El primer vehículo entró en servicio el 18 de marzo de 1940. La enumeración de teclas se realizó debido a la rotación de tambores mecánicos, acompañada de un sonido similar al tic-tac de un reloj.

Coloso En julio de 1942, Turing participó en el descifrado del código de Lorenz utilizado por los alemanes para transmitir mensajes al alto mando. "Lorenz" era mucho más complejo que "Enigma" y no se podía descifrar con los métodos existentes. Turing sugirió usar tubos de vacío en el diseño del decodificador y trajo al equipo T. Flowers, un experimentado ingeniero electrónico. Como resultado de los esfuerzos conjuntos de matemáticos e ingenieros, se desarrolló "Colossus", una de las primeras computadoras del mundo. En 1944, con la ayuda del Coloso, se había descifrado el código de Lorenz, lo que permitió a los aliados leer toda la correspondencia de los más altos líderes alemanes. Según algunas estimaciones, esto acercó la derrota de Alemania en varios años.

Las primeras computadoras y la prueba de Turing De 1945 a 1947, Turing vivió en Richmond y trabajó en el ACE (Motor de Computación Automática) en el Laboratorio Nacional de Física. El 19 de febrero de 1946 presentó lo que podría llamarse la primera descripción detallada de una computadora con un programa almacenado en la memoria. El trabajo inacabado de Von Neumann "Primer borrador del informe EDVAC" (1945) lo precedió, pero era mucho menos detallado, y según el jefe del departamento de matemáticas del Laboratorio Nacional de Física, John Wurmsley: contiene una serie de ideas que pertenecen al Dr. Turing. Aunque la construcción del ACE fue factible, el secretismo que rodeaba a Blatchley Park provocó retrasos en el inicio de las obras, lo que decepcionó a Turing. Hacia fines de 1947, regresó a Cambridge para pasar un año de licencia durante el cual trabajó productivamente en Intelligent Machinery, que no se había publicado durante su vida. Mientras Alan Turing estaba en Cambridge, el ACE Pilot se construyó en su ausencia. Realizó su primer programa el 10 de mayo de 1950. Aunque versión completa ACE nunca se construyó, algunas computadoras tenían mucho en común con él, por ejemplo, DEUCE y Bendix G-15.

En 1948, Alan Turing recibió el título de Lector del Departamento de Matemáticas de la Universidad de Manchester. Allí, en 1949, se convirtió en director del Laboratorio de Computación, donde se concentraba la programación del Manchester Mark I. Al mismo tiempo, Turing continuaba trabajando en problemas matemáticos más abstractos, y en su obra "Computing Machinery and Intelligence" Mind ", Octubre de 1950) abordó el problema de la inteligencia artificial y propuso un experimento que más tarde se conoció como la prueba de Turing. Su idea era que se puede considerar que una computadora "piensa" si la persona que interactúa con ella no puede distinguir la computadora de otra persona en el proceso de comunicación. En este trabajo, Turing sugirió que en lugar de intentar crear un programa que simule la mente de un adulto, sería mucho más fácil comenzar con la mente de un niño y luego enseñarla. CAPTCHA basado en la prueba de Turing inversa está muy extendido en Internet. En 1948, Alan, junto con su antiguo colega David Champernovn (inglés), comenzó a escribir un programa de ajedrez para una computadora que aún no existía. En 1952, sin un dispositivo adecuado para su ejecución, Turing jugó un juego en el que simulaba las acciones de una máquina, haciendo un movimiento cada media hora. El juego se grabó y, como resultado, el programa perdió ante el colega de Turing, Alec Glini, pero ganó el juego sobre la esposa de Champernovna. Turing también inventó el método de expansión LU en 1948, que se usa hoy para resolver ecuaciones.

Diapositiva 2

Introducción

El concepto de algoritmo. Un algoritmo es una prescripción exacta que determina el proceso computacional que va desde los datos de entrada variables hasta el resultado deseado (Markov A.A.) Propiedades del algoritmo: 1) Discreción. 2) Certeza. 3) Efectividad. 4) Carácter de masas.

Diapositiva 3

Modelo matemático de la máquina de Turing

Una máquina de Turing (MT) es un modelo matemático de una máquina de computación digital idealizada. El dispositivo de la máquina de Turing. Cinta. Cabeza de lectura. Dispositivo de control. Memoria interna.

Diapositiva 4

cinta

Solo un símbolo (letra) del alfabeto externo A = (˄, a1, a2,…, an-1), 2≥n se puede escribir en celdas en un momento discreto en el tiempo. Una celda vacía se indica con el símbolo ˄, y el símbolo ˄ en sí mismo se denomina vacío, mientras que el resto de los caracteres se dice que no están vacíos.

Diapositiva 5

Cabeza de lectura

El jefe puede leer el contenido de una celda y escribir en ella un nuevo carácter del alfabeto A. En un ciclo de trabajo, solo puede moverse una celda a la derecha (P), a la izquierda (L) o permanecer en lugar (H).

Diapositiva 6

Memoria interna

La memoria interna de la máquina es un cierto conjunto finito de estados internos Q = (q0, q1,…, qm), m≥ 1. Suponemos que la cardinalidad | Q | ≥2. Dos estados de la máquina son de particular importancia: q1 es el estado interno inicial (puede haber varios estados internos iniciales), q0 es el estado final o estado de parada (el estado final es siempre uno). En cada momento, el MT se caracteriza por la posición de la cabeza y el estado interno.

Diapositiva 7

Dispositivo de control

Realiza las siguientes acciones: Cambia el carácter ai leído en el tiempo t por un nuevo carácter aj (en particular, lo deja sin cambios, es decir, ai = aj); Mueve la cabeza en una de las siguientes direcciones: N, L, R; Cambia el estado interno de la máquina qi existente en el tiempo t al nuevo qj, en el que la máquina estará en el tiempo t +1. Tales acciones del dispositivo de control se denominan comando, que se puede escribir como: qiaiajDqj

Diapositiva 8

Operación de la máquina de Turing

El funcionamiento de la máquina está completamente determinado por la tarea en el primer momento (inicial): Palabras en la cinta, es decir, la secuencia de caracteres escritos en las celdas de la cinta (una palabra se obtiene leyendo estos caracteres a lo largo de las celdas de la cinta de izquierda a derecha); Posiciones de la cabeza; Estado interno de la máquina.

Diapositiva 9

Si en el momento inicial están escritas en la cinta las palabras a1, a2, ˄, a1, a1, entonces la configuración inicial será la siguiente: El funcionamiento de la máquina de Turing consiste en la aplicación secuencial de comandos, además, el uso de uno o el comando está determinado por la configuración actual. Entonces, en el ejemplo anterior, se debe aplicar el comando con el lado izquierdo q1a1. El resultado del funcionamiento de la máquina es la palabra que quedará grabada en la cinta en la configuración final, es decir, en la configuración en la que el estado interno de la máquina es q0.

Diapositiva 10

Ejemplos de máquinas de Turing

Ejemplo 1. Construya una máquina de Turing T1 que sea aplicable a todas las palabras con un alfabeto externo (a, b) y haga lo siguiente: cualquier palabra x1, x2 ... xn, donde xi = a o xi = b (i = 1 , 2 ... n) se transforma en una palabra x2, ... xn, x1, es decir, comenzando a trabajar con la palabra x1, x2 ... xn en la cinta en la configuración inicial, la máquina se detendrá, y en la configuración final, en alguna sección de la cinta, se escribirá la palabra x2, ... xn, x1, y todas las demás celdas de la cinta (si las hay) estarán vacías.

Diapositiva 11

Solución: Para el alfabeto exterior de la máquina T1 tomamos el conjunto A = (˄, a, b), y para el alfabeto interior - Q = (q0, q1, q2, q3). Los comandos se definen de la siguiente manera: q1a ˄Пq2, q1b ˄Пq3, qiy ˄PPi, donde yϵ (a, b), i = 2, 3; q2˄ aHq0, q3˄ bHq0 Considere la operación de la máquina T1 en la palabra ba. En el funcionamiento de la máquina en la palabra ba, la configuración inicial es la siguiente:

Un registro más breve de esta secuencia de configuraciones, es decir, el proceso de funcionamiento de la máquina, será: Así, la palabra bbabb es transformada por la máquina en la palabra babbb.

Ver todas las diapositivas