maquina de turing

Máquinas de Turing (resumen de Computability and Logic, caps. 3 y 4).

Capítulo 3
Definición de computabilidad efectiva
Una función f (de enteros positivos a enteros positivos) es efectivamente computable si en
principio es posible dar una lista de instrucciones completamente definidas y explícitas que
determine el valor f(n) para cualquier argumento n.

1

Definición informal demáquina de Turing
Una máquina de Turing es un tipo específico de máquina idealizada para llevar a cabo
computaciones, especialmente computaciones sobre los números enteros positivos expresados en
notación monádica (tally notation). La computación se lleva a cabo en una cinta que es infinita en
ambas direcciones y que está compuesta por casilleros. Cada casillero está en blanco (el blanco
serárepresentado por alguno de los símbolos ´0`, ´S0` o ´B`) o tiene una barra (stroke) escrita en él
(la barra será representada por alguno de los símbolos ´1`, ´S1` o ´|`). En todo momento (tanto en
el momento inicial como en las computaciones subsiguientes) hay solamente un número finito de
casilleros con una barra escrita (los infinitos casilleros restantes están en blanco). En cada etapa
de lacomputación, la máquina (en realidad, el cabezal o la lectora de la máquina) escanea
exactamente un casillero de la cinta. La máquina es capaz de borrar una barra en el casillero
escaneado, si hay una barra escrita allí, y también es capaz es escribir una barra en el casillero
escaneado, si el casillero está en blanco. La máquina también es capaz de moverse un casillero a
la derecha o un casilleroa la izquierda (siempre, uno por vez).
La máquina está diseñada de modo tal que en cada etapa de computación se encuentra en
un cierto estado qi (que es uno de los estados q1,…,qm) y, además, tiene una lista de m
instrucciones que ejecuta la instrucción número i cuando está en el estado qi.
Acciones posibles de una máquina de Turing
(1) Borrar: escribir 0 en lugar de lo que sea que haya enel casillero escaneado.
2

(2) Escribir: escribir 1 en lugar de lo que sea que haya en el casillero escaneado .
(3) Moverse un casillero a la derecha.
(4) Moverse un casillero a la izquierda.
(5) Para la computación.

1

La definición se extiende obviamente a funciones de cualquier aridad n.
Si hay un 0 en el casillero escaneado, la instrucción (1) es redundante y similarmente, si hay un1 en el
casillero escaneado, la instrucción (2) es redundante.
2

Modos de representar una máquina de Turing
El conjunto de instrucciones correspondiente a una máquina de Turing puede especificarse
de tres maneras distintas: por medio de un tabla (machine table), por medio de un flow chart
(también flow graph), y por medio de un conjunto de “cuádruplos”.

La definición oficial defunción computable por una máquina de Turing:
(a) los argumentos m1,…,mk de la función serán representados en la notación monádica por
bloques de 1s. Cada bloque está separado de los otros por un 0 y, dejando de lado estos
bloques la cinta está completamente blanca (i.e. contiene solamente 0s).
(b) Al comienzo, la máquina está escaneando el 1 que está más a la izquierda en la cinta, y
estará en elestado número 1.

3

(c) Si la función computada le asigna el valor n al argumento representado inicialmente en la
cinta, la máquina eventualmente para (halts) con la cinta conteniendo un bloque de n 1s. El
resto de la cinta, por supuesto, queda vacío (i.e. contiene solamente 0s).
4

(d) La máquina para leyendo el 1 que está más a la izquierda en el bloque resultante .
(e) Si la funciónpresuntamente computada no arroja ningún valor para los argumentos que
están representados inicialmente en la cinta, la máquina o bien nunca para, o para en
alguna configuración no estándar.

Una función numérica de k argumentos (de enteros positivos a enteros positivos) es computable
por una máquina de Turing si existe alguna máquina de Turing que la computa en el sentido
especificado en...