Historia Alain Turing

1. MÁQUINAS DE TURING (TEORÍA)

1.1. Tesis de Turing

1.2. ¿Qué es una máquina de Turing?

1.3. El problema de la indicidibilidad en las máquinas de Turing

2. MÁQUINAS DE TURING (PRÁCTICA)

2.1. Tarea 1. Buscar la primera casilla en blanco y parar

2.2. Tarea 2. Encontrar el primer 2 hacia la derecha y parar

2.3. Tarea 3. Localizar el segundo 2 y parar

2.4. Tarea 4. Parar ante dos 1 consecutivos y parar

2.5. Tarea 5. Buscar el patrón ‘2112’ y parar

2.6. Tarea 6. Recordar una expresión, recordarla y copiarla

2.7. Tarea 7. Computar el siguiente número de uno dado anteriormente

2.8. Tarea 8. Sumar dos números separados por un indicador y parar

2.9. Tarea 9. Multiplicar dos números separados por un indicador y parar

En este trabajo se presentan una serie de cuestiones teóricas y prácticas sobre la

noción de ‘máquina de Turing’. En la primera parte se tratan dos tesis centrales para

comprender qué es una máquina de Turing, así como los conceptos teóricos que

aparecen asociados a ellas. En la segunda parte se realizan algunas de las tareas típicas

que pueden desarrollar las máquinas de Turing. Estas tareas son especialmente útiles

para comprender la noción de computación, y en general para conocer cómo funcionan

las máquinas de Turing.

I. MÁQUINAS DE TURING. (TEORÍA)

I.1. TESIS DE TURING

Tesis 1.

«Todo problema que pueda resolverse algorítmicamente, puede ser resuelto por una

máquina de Turing»

Conceptos asociados a la Tesis 1

Algoritmo: conjunto de reglas que aplicadas de forma mecánica pueden resolver

un problema de una clase dada. Fundamentalmente en contextos matemáticos.

Cálculo: Toda operación que se desarrolle mediante manipulación de símbolos

en un medio de representación dado. Las operaciones simbólicas son atómicas,

esto es, absolutamente simples y se realizan en un computador. La acción del

computador va a depender de los símbolos que tenga el sistema y del estado

interno en el que se encuentra el computador.

Tesis 2.

«Toda función computable puede ser computada por una máquina de Turing. Todo

problema que puede ser resuelto por métodos algorítmicos puede ser resuelto por una

máquina de Turing»

Conceptos asociados a la Tesis 2.

Función computable: Clases de problemas que pueden ser resueltos

algorítmicamente, esto es, si al algoritmo se le dan los argumentos

correspondientes, entonces computará esos valores terminando la tarea en un

número finito de pasos.

I.2.¿Qué es una máquina de Turing?

Una máquina de Turing es una máquina ideal -formalmente hablando se trata de

un algoritmo- en dos aspectos básicos. La primera idealización se debe a que su

memoria es ilimitada. La segunda idealización se produce por el hecho de una máquina

de Turing nunca comete errores. A efectos de representar una máquina de Turing,

podemos imaginarla como una cinta infinita dividida en cuadros sobre la que se realizan

las operaciones de manipulación de símbolos. La máquina dispone de un lector que

realiza las siguientes funciones:

i. Está situado en todo momento ante uno de los cuadros de la cinta

ii. Lee lo que hay en ese cuadro.

iii. Lleva a cabo una instrucción en el momento siguiente.

Una descripción formal de una máquina de Turing la presentaría como una tabla

de la siguiente forma:

M = movimientos del lector de la máquina de Turing [‘L’= izquierda y ‘R’= derecha]

q = estado computacional en el que se encuentra la máquina de Turing

S = símbolo con el que realiza los cómputos la máquina de Turing

Lo que en esta tabla expresa es una función por la cual, a cada par formado por

un símbolo y un estado, la máquina asocia un símbolo, un estado y un movimiento que

se representa mediante el triplo {S1 q1 M}

I.3. El problema de la indecidibilidad en las máquinas de Turing

La idea central de Turing es que allí donde exista un procedimiento de decisión

habrá una máquina de Turing que pueda realizarlo. Ahora bien, la existencia de

problemas indecidibles significaría que para esa clase de problemas no existiría una

máquina de Turing que respondiera ‘si’ o ‘no’ cuando esta máquina se aplicara a una

cinta donde tenemos el problema dado.

En particular, existe un problema indecidible para cualquier máquina

...