Medidor

Curso de doctorado: Máquinas y mentes: introducción a la teoría de la Turingcomputabilidad
Profesor: Juan José Acero
Curso: 1994/1995

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 yparar
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 delas 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»
Conceptosasociados 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óndel
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 quepueden 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 esilimitada. 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.
ii.
iii.

Está situado entodo momento ante uno de los cuadros de la cinta
Lee lo que hay en ese cuadro.
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:
Q1

Q2 ………………… …..Qn

S1

S1 q1 M

S1 q2 M

S1 qn M

S2

S1

S2 q2 M

S2 qn M

Sm

S1 q2 M

S m q2 M

S m qn M

Sm

Sm q1 M

Smq2 M

Sm qn M

q1 M

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...