Maquinas de turing

Maquinas de Turing.
Otra forma de caracterizar la clase de las funciones computables se hace mediante las llamadas máquinas de Turing 33. Estas son máquinas formales, es decir sin cables ni componentes físicos. Su finalidad es definir los cálculos a partir de las operaciones más sencillas posibles, y utilizando las cuales calcular efectivamente funciones dadas. Las funciones que así puedenrealizarse se llaman funciones calculables o computables.
Este tipo de máquina consta hipoteticamente de una unidad de control capáz de interpretar las instrucciones que reciba, y de una cabeza lectora que permite leer el contenido de una de las casillas en que esta dividida una memoria lineal, ilimitada en ambas direcciones de sus extremos.

[pic]
La máquina en su funcionamiento pasa pordiferentes estados [pic]en instantes [pic]sucesivos. El argumento de la función que queremos calcular estará almacenado previamente en la memoria, y en el instante inicial, antes de que la máquina comience a funcionar, la cabeza lectora apuntará al símbolo más a la izquierda del argumento. A partir de ese momento la máquina realizará operaciones, que dependerán del estado en que ella se encuentre, y delsímbolo que en ese momento lea la cabeza lectora. Con estas operaciones se podrán realizar las siguientes atreas: sustituir el símbolo leído por otro, pasar a leer el símbolo que esta en memoria a la derecha del símbolo leído, pasar a leer el símbolo que esta en memoria a la izquierda, o saltar directamente a ejecutar otra instrucción si se cumple una condición especificada 34; en todos los casos, yuna vez ejecutada la tarea indicada, se pasaría al estado que tambien se indica en la propia instrucción.
Estas instrucciones, o cuaternas, las podemos representar e interpretar así:
|[pic][pic][pic][pi|si estando en el estado [pic]se lee el |
|c]: |simbolo [pic], entonces [pic]se cambia por |
| |[pic]y se pasa al estado [pic] |
|[pic][pic]R[pic]:|si desde [pic]se lee [pic], entonces se pasa|
| |a leer la casilla situada a su derecha y se |
| |cambia al estado [pic] |
|[pic][pic]L [pic]:|si desde [pic]se lee [pic], entonces se pasa|
| |a leer la casilla a su izquierda y se cambia|
| |al estado [pic] ||[pic][pic][pic][pi|si desde [pic]se lee [pic], entonces se |
|c]: |cambia al estado [pic]o al [pic]según una |
| |cierta condición |

donde: [pic]indica un estado de la máquina tomado del conjunto de estados [pic]; [pic]indica uno de los símbolos que pueden aparecer en la memoria tomado del alfabeto [pic]; [pic]es un símbolo que indica pasara leer la casilla de memoria situada a la derecha; [pic]es un símbolo que indica pasar a leer la casilla de memoria situada a la izquierda.
Se define una máquina de Turing [pic]como un conjunto finito, no vacío, de cuaternas, de forma que no contenga dos cuaternas con los dos primeros símbolos correspondientes iguales.
Indicaremos por [pic]al conjunto de estados de la máquina, por [pic]alalfabeto de símbolos de la memoria.
En [pic]siempre existe un estado particular, que se suele indicar por [pic]y llamarse estado inicial, en el que se supone está la máquina al comenzar a operar. En el alfabeto [pic]siempre figurarán, entre otros posibles, dos símbolos: el blanco ([pic]), y el uno (expresado por un palote [pic]) . A las cadenas formadas por símbolos de este alfabeto se las llamaexpresiones de memoria. Si en una expresión de memoria incluimos un único símbolo [pic](que indique un estado de [pic]) siempre que no le situemos a la derecha de cualquier otro, obtendremos una expresión que llamaremos descripción instantánea de la maquina [pic].
Los números naturales se representan en estas máquinas, de la forma más simple, es decir usando un solo símbolo ( [pic]). Se emplean dos...