LOS PROBLEMAS DE HILBERT

El 8 de Agosto de 1900, en París, un profesor de la

Universidad de Göttingen dio una

conferencia que capturaría la imaginación de los matemáticos

del siglo XX. El profesor era David Hilbert y su plática se

tituló simplemente “Problemas Matemáticos”.

Hilbert era uno de los matemáticos más prominentes

de su generación. Poco tiempo después de haberse

doctorado, se interesó en la teoría de invariantes algebraicos. (Por ejemplo, dada una

forma cuadrática, el determinante de la matriz correspondiente es invariante bajo

rotaciones). En 1888, a los 26 años, Hilbert demostró que, dada una forma algebraica,

existe un número finito de invariantes que generan a todos los demás. (Una especie de

base). Con este resultado y con su trabajo posterior, Hilbert prácticamente resolvió

todos los problemas interesantes que había sobre invariantes.

Habiendo agotado ese tema, se dedico a la Teoría de Números. Rápidamente

descubrió unas demostraciones de la trascendencia de ð y de e más simples y directas

que las demostraciones originales. Su principal contribución fue una generalización de la

Ley de Reciprocidad Cuadrática (publicada en 1898), que les permitió a él y a matemáticos

posteriores extender la Teoría de Números a campos más abstractos y generales.

Entonces, volvió a cambiar de tema. En 1899 publicó el libro “Fundamentos de la

Geometría”. Una exposición axiomática de la Geometría (Euclidiana y No Euclidiana)

que se sujeta a los requisitos más estrictos del rigor matemático que se estaban desarrollando

en el momento y que son la norma hoy en día. A partir de entonces, Hilbert estuvo muy

interesado en los Fundamentos de las Matemáticas. En particular, se preocupó por la

existencia de una colección de axiomas que fuera consistente y completa.

Para la solución de ciertas ecuaciones que aparecen en la Física, un método muy

común es encontrar una función que minimice cierta integral (El Principio de Dirichlet).

Roberto Murillo

Departamento Académico de Matemáticas, ITAM

rmurillo@itam.mx

David Hilbert

epístola de la ciencia

478352735098142689345637282964856758595973342092863453039485761232534775650393761234567890987654321342564399384756575751198096454685959

25

Como el problema proviene de una situación física, la gente simplemente asumía la

existencia de dicha función minimizadora. Pero a mediados del siglo XIX, Weierstrass dio

ejemplos donde no existía tal función. Sin embargo, el Principio de Dirichlet parece tan

simple y natural que Hilbert decidió tratar de rescatarlo. Y en Septiembre de 1899 publicó

un artículo donde demostró que, bajo ciertas condiciones, el Principio de Dirichlet es

válido. Dichas condiciones son satisfechas por los problemas que aparecen más

comúnmente en la Física, pero excluyen los ejemplos puramente matemáticos de

Weierstrass.

Es claro que Hilbert estaba interesado en varias áreas de las Matemáticas. Su

método de trabajo consistía en concentrarse en algún problema y tratar de simplificarlo,

de hacerlo más claro. Para él, el rigor matemático era una herramienta en este proceso. A

través del rigor, uno puede evitar las falsas suposiciones que pueden llevar al error y a la

confusión.

Con su prestigio en aumento, Hilbert recibió una invitación

para dar una conferencia plenaria en el Segundo Congreso

Internacional de Matemáticas en 1900. Esta fue la

conferencia “Problemas Matemáticos”. En ella habló de la

importancia de un buen problema para el impulso de las

Matemáticas y de su convicción filosófica de que dado

cualquier problema matemático, tarde ó temprano se le

encontrará una solución.

Fue así que propuso una lista de 23 problemas, no

como un reto, sino como un incentivo para los matemáticos

del nuevo siglo. Esta lista es conocida como “Los Problemas

de Hilbert” y consta de problemas importantes en Teoría de

Números, Álgebra, Geometría, Análisis, Teoría de Conjuntos

y Fundamentos Axiomáticos.

La lista incluye problemas tan famosos como la Hipótesis del Continuo. Al intentar

la solución de los problemas, el objetivo de Hilbert de estimular el crecimiento de las

Matemáticas se ha cumplido con creces. Aún hoy, el sueño de muchos matemáticos es

contribuir a la solución de alguno de ellos e ingresar así a la elite que se conoce no

oficialmente como “The Honors Class”.

laberintos e infinitos

478352735098142689345637282964856758595973342092863453039485761232534775650393761234567890987654321342564399384756575751198096454685959

26

En este momento, de los 23 problemas, 16 se consideran básicamente resueltos, 4

son más programas de trabajo que problemas concretos, y 3 permanecen sin resolver (a

esta categoría pertenece el problema #8; La Hipótesis de Riemann). En futuros artículos

iremos comentando con mayor detalle algunos de los problemas.

Las Matemáticas han cambiado mucho en un siglo. Con la tremenda expansión y

especialización que han sufrido las diferentes áreas, hoy es prácticamente imposible para

una sola persona tener la visión panorámica que tenía Hilbert. Aun así, en 1998, Stephen

Smale propuso una lista de problemas para el siglo XXI. (Su primer problema es,

nuevamente, La Hipótesis de Riemann). Otro intento de indicar los problemas importantes

para este siglo es el libro [1], que es un trabajo de 30 autores diferentes bajo la dirección

de 4 editores. Pero no parece que estos esfuerzos tengan el mismo atractivo global que

tienen los Problemas de Hilbert.

Bibliografía;

[1] Arnold, V.I. et. al. Mathematics: Frontiers and Perspectives. IMU and AMS (2000).

[2] Hilbert, David. “Mathematical Problems”. Bulletin AMS 8 (1902), 437-479.

[3] Reid, Constance. Hilbert. Springer-Verlag (1970).

[4] Smale, S. “Mathematical Problems for the Next Century”. Mathematical Intelligencer.

20:2 (1998), 7-15.

[5] Yandell, B. H. The Honors Class. A. K. Peters, Ltd. (2002).

Máquina de Turing

Como se ha dicho antes, actualmente, el autómata más general es una máquina de Turing y cualquier modelo de computación es equivalente a una MT. Como muchas cosas de gran utilidad práctica y profundidad conceptual, los elementos que forman una MT son simples; aparte de los elementos comunes a cualquier autómata se añaden los siguientes:

·        ·         Una cinta (quizá infinita) dividida en espacios rectangulares.

·        ·         Cabeza de lectura y escritura.

Las cadenas de símbolos están escritos en la cinta, uno y sólo uno en cada espacio rectangular; un símbolo es el espacio en blanco y los símbolos especiales, I y D, indican  movimiento a la izquierda y derecha, respectivamente, de la cabeza lectora sobre la cinta. En el caso que la cinta sea infinita, se extiende hacia la derecha y se asume que en el extremo izquierdo de la cinta se tiene un tope más allá del cual la cabeza lectora no puede moverse. La infinitud de la cinta quiere decir que se puede leer o escribir tanto como se quiera, lo cual corresponde, teóricamente, a una capacidad de memoria ilimitada.

La cabeza de lectura y escritura es la que se encarga de leer o escribir los símbolos en la cinta conforme a la función de transición (mecanismo de control). Puede leer un símbolo y cambiarlo por otro, ó borrarlo y dejar ese espacio en blanco; ó habiendo leído un espacio en blanco, escribir un símbolo distinto del blanco. Si los símbolos que lee son I o D, la cabeza lectora se mueve a la izquierda o derecha, respectivamente.

La memoria de un autómata de Turing es la propia cinta. En el caso del lenguaje {aⁿ bⁿ cⁿ : n Î N} la MT es la de la figura X y funciona conforme la función de transición descrita en la Tabla X: la cabeza lectora lee las cadenas de a’s y sin borrarlas avanza hacia la derecha hasta leer la última a;  conforme empieza a leer un símbolo b lo sustituye por un espacio en blanco, y cambia de dirección moviéndose hacia la izquierda hasta encontrar una a, la cual sustituye por una b; entonces se mueve de nuevo hacia la derecha tantas b’s como ha escrito, lee el espacio en blanco y lee la siguiente b (de la cadena original) si la hay, completando un ciclo. Sucesivamente repite el ciclo hasta encontrar un símbolo c distinto de b. Si el autómata lee y borra tantas b’s como a’s que sustituye, significa que hubo el mismo número de a’s y b’s en la cadena que se está leyendo. Entonces se opera el ciclo de la misma manera con las c’s y las b’s. Si son tantas c’s que lee y borra como b’s que sustituye, el autómata logra un estado final y reconoce a la cadena como parte del lenguaje. En caso contrario, no son iguales el número de ocurrencias de a, b y c, por lo que la cadena es rechazada por la MT y no forma parte del lenguaje.

Obsérvese como en el ejemplo la cinta funciona como memoria al mantener guardadas durante la operación, primero las a’s luego las b’es y luego las c’s.  Conforme necesita lo escrito en memoria (la cinta) para operar, lo saca (lo lee) y lo utiliza –a veces lo borra, otras lo sustituye, etc. Sin embargo, la cinta ofrece posibilidades de manejo de memoria mucho más poderosas que la pila. En el ejemplo, la MT empila (lee sin borrar de izquierda a derecha) las a’s y luego, desempila cada una y empila en su lugar una b (lee de derecha a izquierda una a, la borra y escribe en su lugar una b); el punto es que para desempilar las a’s la MT lee no solo en la cima de la pila, sino también puede leer las posiciones interiores de la pila (puede recorrer la cinta todas los cuadros a la izquierda hasta llegar al tope, el cual representaría el fondo de la pila). A diferencia, un AP solo puede leer de la cima de la pila.  Por este manejo limitado de memoria es que un AP no puede reconocer el lenguaje {aⁿ bⁿ cⁿ : n Î N} pese a poder reconocer al lenguaje {aⁿ bⁿ : n Î N}.

En general puede decirse que un autómata de pila es una MT tal que la pila esta sobre la cinta y tiene la restricción de moverse hacia la izquierda solamente una posición. Es claro que en una MT los movimientos hacia derecha e izquierda de la cinta, así como la capacidad de leer y escribir cualesquiera símbolos y espacios blanco sobre la cinta, es lo que permite un manejo dinámico de la memoria, versatilidad de la cual carece un autómata de pila al no contar con una cinta ni una cabeza de lectura – escritura, ni la capacidad de ir hacia delante o atrás. 

Es posible que con el ejemplo anterior, el lector empiece a creer que pese a que una MT es un dispositivo simple, es capaz,  sin embargo,  de realizar cualquier procedimiento computable. Al fin y al cabo un proceso computable no requiere si no

Ø     Ø       Un almacén de datos (cinta tan larga como se requiera),

Ø     Ø       Un dispositivo para leer y/o escribir datos en el almacén (cabeza de lectura/escritura),  y

Ø     Ø       Capacidad para moverse a través de los datos en el almacén (movimientos de la cabeza a lo largo de la cinta, coordinados por el control de estados).

Como se ve, todos ellos son elementos que posee una MT. Una computadora no es sino una gran y compleja Máquina de Turing formada a partir de máquinas de Turing más simples. El disco duro corresponde a la cinta, la cabeza a los dispositivos de lectura y escritura del y sobre el disco, y el control de la cabeza (matemáticamente, la función de transición) a los comandos de los distintos programas que se ejecutan con la computadora^[1][8]. Pasaremos ahora a la precisar lo que es un algoritmo o secuencias de instrucciones que una computadora ejecuta en tiempo finito.

Máquina de Turing

De Wikipedia

Saltar a navegación, búsqueda

La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo.

Diagrama artístico de una máquina de Turing.

Descripción

La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

• avanzar el cabezal lector/escritor para la derecha;
• avanzar el cabezal lector/escritor para la izquierda.

El cómputo es determinado a partir de una tabla de estados de la forma:

(estado,valor) (\nuevo estado, \nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.

Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.

De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.

La idea subyacente en el concepto de máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. La memoria se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, “si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a la leer la celda siguiente, bien a la izquierda o bien a la derecha. La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.

[editar]

Definición

Una máquina de Turing con una sola cinta puede ser definida como una 6-tupla M = (Q,Γ,s,b,F,δ), donde

• Q es un conjunto finito de estados
• Γ es un conjunto finito de símbolos de cinta, el alfabeto de cinta
• es el estado inicial
• es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces
• es el conjunto de estados finales de aceptación
• es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.

Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo S como símbolo de "no movimiento" en un paso de cómputo.

Ejemplo

Definimos una máquina de Turing sobre el alfabeto {'0', '1'}, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo "1" de una serie. La máquina de Turing copiará el número de símbolos "1" que encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir, situada sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada "111" devolverá "1110111", con "1111" devolverá "111101111", y sucesivamente.

El conjunto de estados es {s1, s2, s3, s4, s5} y el estado inicial es s1. La tabla que describe la función de transición es la siguiente:

 Estado Símbolo Símbolo   Mov.  Estado           Estado Símbolo Símbolo   Mov.  Estado

       
                                    leido   escrito        
                                    sig.                   
                                    leido   escrito         sig.

 - - - - - - - - - - - - - - - - - - - -          
                                    - - - - - - - - - - - - - - - - - - - -

  s1     
                                    1   ->    0      R     
                                    s2              
                                    s4      1  
                                    ->   1      
                                    L     s4

  s2      1   ->    1      R      s2              
                                    s4      0  
                                    ->   0      
                                    L     s5

  s2      0   ->    0      R      s3              
                                    s5      1  
                                    ->   1      
                                    L     s5

  s3      0   ->    1      L      s4              
                                    s5      0  
                                    ->   1      
                                    R     s1

  s3      1  
                                    ->    1     
                                    R      s3

El funcionamiento de una computación de esta máquina se puede mostrar con el siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora):

 Paso Estado  Cinta      Paso Estado   Cinta

 - - -
                                    - - - - - - - -   - - - - - - - - - - - -

    1  s1     11           9  s2       1001

    2  s2     01          10  s3       1001

    3  s2     010         11 
                                    s3       10010

    4  s3     0100        12  s4       10011

    5  s4     0101        13  s4       10011

    6  s5     0101        14  s5       10011

    7  s5     0101        15  s1       11011

    8  s1     1101          -- Parada --

La máquina realiza su proceso por medio de un bucle, en el estado inicial s1, reemplaza el primer 1 con un 0, y pasa al estado s2, con el que avanza hasta la derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuandolo encuentra pasa a ser s3, con este estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habría ningún 1). Una vez en el extremo derecho, añade un 1. Después comienza elproceso de retorno; con s4 vuelve a la izquierda saltando los 1, cuand encuentra un 0 (en el medio de la secuencia), pasa a s5 que continúa a la izquierda saltando los 1 hasta el 0 que se escribió al principio. Se reemplaza de nuevo este 0 por 1, y pasa al símbolo siguiente, si es un 1, se pasa a otra iteración del bucle, pasando al estado s1 de nuevo. Si es un símbolo 0, será el símbolo central, con lo que la máquina se detiene al haber finalizado su cómputo.

Máquinas de Turing deterministas y no deterministas

La entrada de una máquina de Turing viene determinada por el estado actual y el símbolo leído, siendo el cambio de estado, la escritura de un nuevo símbolo y el movimiento las acciones a tomar en función de una entrada. En el caso de que para cada par estado y símbolo posible exista a lo sumo una posibilidad de ejecución, diremos que es una máquina de Turing determinista, mientras que en el caso de que exista al menos un par (estado, símbolo) con más de una posible combinación de actuaciones diremos que se trata de una máquina de Turing No Determinista.

La función de transición δ en el caso no determinista, queda definida como sigue:

La capacidad de cómputo de ambas versiones es equivalente; se puede demostrar que dada una máquina de Turing no determinista existe otra máquina de Turing determinista equivalente, en el sentido de que reconoce el mismo lenguaje, y viceversa. No obstante, la velocidad de ejecución de ambos formalismos no es la misma, pues si una máquina no determinista M reconoce una cierta palabra de tamaño n en un tiempo O(t(n)), la máquina determinista equivalente reconocerá la palabra en un tiempo O(2^t(n)). Es decir, el no determinismo permitirá reducir la complejidad de la solución de los problemas, permitiendo resolver, por ejemplo, problemas de complejidad exponencial en un tiempo polinómico (Ver complejidad computacional).

Máquina Universal de Turing

Una máquina de Turing computa una determinada función parcial de carácter definido, y unívoca, definida sobre las secuencias de posibles cadenas de símbolos de su alfabeto. En este sentido se puede considerar como equivalente a un programa de ordenador, o lo que es lo mismo, a un algoritmo. Sin embargo es posible realizar una codificación de la tabla que representa a una máquina de Turing, a su vez, como una secuencia de símbolos en un determinado alfabeto; por ello, podemos construir una máquina de Turing que acepte como entrada la tabla que representa a otra máquina de Turing, y, de esta manera, simule su comportamiento.

En 1947, Turing indicó:

Se puede demostrar que es posible construir una máquina especial de este tipo que pueda realizar el trabajo de todas las demás. Esta máquina especial puede ser denominada máquina universal.

Esta fue, posiblemente, la idea germinal del concepto de Sistema Operativo, un programa que puede, a su vez, ejecutar en el sentido de controlar otros programas, demostrando su existencia, y abriendo camino para su construcción real.

Con esta codificación de tablas como cadenas, se abre la posiblidad de que unas máquinas de Turing se comporten como otras máquinas de Turing. Sin embargo, muchas de sus posibilidades son indecidibles, pues no admiten una solución algorítmica. Por ejemplo, un interesante problema es determinar si una máquina de Turing cualquiera se parará en un tiempo finito sobre una determinada entrada; problema conocido como Problema de la parada, y que Turing demostró que era indecidible. En general, se puede demostrar que cualquier cuestión no trivial sobre el comportamiento o la salida de una máquina de Turing es un problema indecidible.

Obtenido de "http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing"

MÁQUINAS DE TURING Y

LENGUAJES ACEPTADOS POR FRASES

MÁQUINAS DE TURING

- Son máquinas teóricas capaces de aceptar lenguajes generados por gramáticas

estructuradas por frases.

- Una máquina de Turing tiene una cabeza de lectura/escritura que avanza

bidireccionalmente por una cinta infinita por la derecha.

• Entrada: contenido inicial de la cinta.

• Salida: contenido final de la cinta.

- Símbolos de cinta:

• Símbolos de entrada: Σ

• Símbolos de cinta: Γ ⊇ Σ

- Transiciones: ä(p,x) = (q,y) donde:

• p,q: estados

• x ∈ Σ : símbolo de entrada

• y ∈ Γ ∪ {L,R} : símbolo de cinta o desplazamiento

- En una transición, la máquina de Turing lee un símbolo de la cinta, cambia de estado y

escribe un símbolo o efectúa un desplazamiento a izquierda o derecha.

- Ejemplo de diagrama de transiciones

- Proceso de reconocimiento de una cadena:

• Se parte del estado inicial, y la cinta contiene símbolos de entrada.

• Se efectúan las transiciones pertinentes según la función de transición.

• Si la cabeza lectora rebasa el extremo izquierdo de la cinta, la cadena es

rechazada y el proceso termina (terminación anormal).

• Si la máquina alcanza el estado de parada, la cadena es aceptada.

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -2-

- MT: M(S,Ó,Ã,ä,i,h)

• S: conjunto finito de estados.

• Ó: alfabeto de entrada.

• Ã: alfabeto de símbolos de cinta.

• ä: función de transición (determinista): S x à → S x (Ã∪{L,R}).

• i: estado inicial.

• h: estado de aceptación o de parada.

- En general, las máquinas de Turing son deterministas.

TESIS DE TURING

El poder computacional de una máquina de Turing es tan grande como el de cualquier

sistema computacional posible.

COMBINACIÓN DE MÁQUINAS DE TURING

- Pasos:

1. Eliminar la característica de inicio de los estados iniciales de todas las máquinas,

excepto de la primera.

2. Eliminar la característica de parada de todas las máquinas, e incluir un nuevo estado

de parada.

3. Para cada estado de parada p y para cada x ∈ Γ:

a) Si la nueva máquina se debe detener al llegar a p con x, añadir un arco x/x de p al

nuevo estado de parada.

b) Si al llegar al estado p con el símbolo actual x la máquina compuesta debe

transferir el control a la máquina M(S,Ó,Ã,ä,i,h), dibujar un arco con etiqueta x/z

de p al estado q de M tal que ä(i,x) = (q,z).

CONSTRUCCIÓN MODULAR DE MÁQUINAS DE TURING

- Construcción de máquinas de Turing complejas a partir de bloques elementales.

- Transferencia de control entre máquinas: → →  M1 x M2

- Transferencia de control con varios símbolos:

→  →   → → M1 x, y, z w M2 w M3 }

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -3-

Bloques de construcción básicos

- Bloques más complejos

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -4-

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -5-

EVALUACIÓN DE CADENAS

- Aceptación de una cadena

• Situación inicial:

∗ Cabeza en el extremo izquierdo de la cinta.

∗ La cadena de entrada empieza en la segunda posición de la cinta.

• Situación final:

∗ Máquina de Turing en estado de parada.

- Lenguaje aceptado por una máquina de Turing: conjunto de cadenas que acepta.

- Una máquina de Turing puede escribir un mensaje de aceptación si acepta una cadena.

• Mensaje de aceptación: ∆Y∆∆∆

- Símbolos especiales

• #: extremo izquierdo de la cinta

• *: extremo derecho de la porción alterada de la cinta

- Si la máquina es M, la máquina final es:

• M0 es igual que M, salvo que:

∗ Si M0 alcanza #, se desplazará una casilla a la izquierda (terminación

anormal)

∗ Si M0 alcanza *, debe desplazarlo un lugar a la derecha ejecutando

→ R*L∆

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -6-

Máquinas de Turing de varias cintas

- Cada cinta tiene su propia cabeza de lectura/escritura.

- Una transición:

• Depende de los símbolos acutales de todas las cintas.

• Sólo afecta a una cinta (escribir o desplazar).

- Estado inicial:

• Contenido de la primera cinta: ∆w∆∆∆...

• Las restantes cintas están en blanco, con la cabeza en su extremo izquierdo.

Teorema 3.1

Para cada máquina de Turing M de k cintas, existe una máquina de Turing M' con una

cinta tal que L(M)=L(M').

DEMOSTRACIÓN: Construcción de M'

- Previo:

• Cada casilla en el conjunto de las k cintas se representa como una 2k-tupla:

* En la posición 2n-1 de la tupla se tiene el símbolo de la cinta n.

* En la posición 2n de la tupla hay 1 si la cabeza está en la casilla, ∆ si no.

• Es posible asignar un símbolo de cinta nuevo a cada posible 2k-tupla.

* Así se puede almacenar en una sola cinta toda la información del conjunto

completo de cintas.

• Cada estado de M' se representa como un estado compuesto formado por una k+1-

tupla cuyo primer elemento es el estado de la cinta, siendo los demás elementos los

símbolos actuales de todas las cintas.

- Primer paso: traducir el contenido de la cinta de M' a un formato que represente todas

las cintas de M.

• Desplazar el contenido de la cinta a la derecha un lugar: →R∆SRL∆ (la cabeza queda

en la segunda posición de la cinta).

• Mover la cabeza un lugar a la izauierda, escribir # y mover un lugar a la derecha.

• Repetir los dos pasos siguientes hasta que el símbolo sustituido en b) sea un blanco:

a) Mover la cabeza un lugar a la derecha.

b) Sustituir el símbolo actual x por la tupla (x,∆,∆,...,∆).

• Ejecutar L∆, lo que pondría la cabeza en la segunda casilla de la cinta, y escribir en

ella la tupla (∆,1,∆,1,...,∆,1).

- Simulación de M:

• Cada transición de M supone una secuencia de pasos en M'.

• Estado inicial: (i,∆,∆,...,∆).

• Una transición (ô) sólo afecta a una cinta (jô).

• Secuencia corresponciente a la transición ô:

* Mover la cabeza a la derecha hasta que el componente 2j de la 2k-tupla sea 1.

* Si la transición es uan esceitura, modificar el componente 2jô-1 de la tupla.

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -7-

* Si la transición produce un movimiento a la derecha:

�� Reemplazar el componente 2jô-1 por un ∆.

�� Mover la cabeza a la derecha.

�� Si encuentra un ∆, sustituirlo por la 2k-tupla (∆,∆,...,∆).

�� Reemplazar el componente 2jô-1 por un 1.

* Si la transición produce un movimiento a la izquierda:

�� Reemplazar el componente 2jô-1 por un ∆.

�� Mover la cabeza a la izquierda.

�� Si encuentra un #, mover a la izquierda (terminación anormal).

�� Reemplazar el componente 2jô-1 por un 1.

* Colocar la cabeza en la segunda posición de la cinta (después de buscar a la

izquierda el símbolo #), y pasar al nuevo estado compuesto de M'.

- La máquina M' así construida simula M, y acepta el mismo lenguaje que ella.

Máquinas de Turing no deterministas

- El no determinismo puede consistir en que:

• La máquina no se encuentre totalmente definida.

• Se ofrezcan alternativas en algunos pares estado-símbolo.

- M(S,Ó,Ã,ð,i,h) donde ð es un subconjunto de ((S-{h})xÃ)x(Sx(Ã∪{L,R})).

- Una máquina de Turing no determinista acepta una cadena w cuando es posible que

llegue al estado de parada después de iniciar sus cálculos con la entrada w.

Teorema 3.2

Para toda máquina de Turing M no determinista existe una máquina determinista D que

acepta el mismo lenguaje que M.

DEMOSTRACIÓN

- Para toda máquina de Turing M no determinista existe una máquina determinista M'

con tres cintas que acepta el mismo lenguaje.

• 1ª cinta: contiene la cadena de entrada.

• 2ª cinta: cinta de trabajo. En ella se copia la cinta 1 (desplazada un lugar a la

derecha), marcando el principio de la cinta con # y marcando el final de la

entrada con *. En este cinta se simulan secuencias de transiciones.

• 3ª cinta: control de las transiciones efectuadas.

- Simulación de M:

1. Copiar la cadena de entrada de 1 a 2 (con los marcadores de inicio y fin).

2. Generar la siguiente secuencia de transiciones en la cinta 3.

3. Simular la secuencia con la cinta 2.

4. Si se llega al estado de parada de M, detenerse. Si no, borrar la cinta 2 y volver

al paso 1.

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -8-

LENGUAJES ACEPTADOS POR MÁQUINAS DE TURING

- Gramáticas estructuradas por frases:

• Parte izquierda de las reglas: combinación de símbolos terminales y no

terminales, con al menos un no terminal.

• Parte derecha de las reglas: combinación de símbolos terminales y no terminales

de cualquier longitud (incluso 0).

- Las máquinas de Turing aceptan lenguajes estructurados por frases.

- Configuración de una máquina de Turing:

• Contenido de la cinta: entre corchetes.

• A la izquierda del símbolo actual se incluye el estado.

- Aceptación: secuencia de configuraciones de la máquina que empieza con [i∆w∆] y

termina con [h∆Y∆].

Teorema 3.3

Todo lenguaje aceptado por una máquina de Turing es un lenguaje estructurado por

frases.

DEMOSTRACIÓN

La gramática será (V,Ó,S,R) donde

• V = {S,[,],∆,Y} ∪ Ã

• Ó = alfabeto de M.

• S: axioma.

• R:

S → [h∆Y∆]

∆] → ∆∆]

ä(p.x) = (q,y) produce la regla qy → px

ä(p,x) = (q,R) produce la regla xq → px

ä(p,x) = (q,L) produce las reglas qyx → ypx ∀y∈Ã

[i∆ → ë

∆∆] → ∆]

∆] → ë

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -9-

Teorema 3.4

Todo lenguaje estructurado por frases es aceptado por una máquina de Turing.

DEMOSTRACIÓN

Para cada gramática G existe una máquina de Turing no determinista M de 2 cintas que

aceptas el lenguaje generado por G.

Construcción de la máquina:

1. Se copia la cadena de entrada en la primera cinta.

2. Se escribe S (símbolo inicial) en la cinta 2.

3. Se aplican las reglas de reescritura de forma no determinista a la cadena de la

cinta 2.

4. Si la cinta 2 contiene sólo símbolos terminales, se compara con la cadena de la

cinta 1. Si son iguales, el proceso ha terminado. Si no, provocar una terminación

anormal.

Teorema 3.5

Dado un alfabeto Ó existe al menos un lenguaje L definido sobre Ó que no es un

lenguaje estructurado por frases.

Sistemas de codificación de máquinas de Turing

- Cada estado se representa como una cadena de ceros.

• i = 0

• h = 00

• Los demás: a partir de 000 en adelante.

- Cada símbolo de Ó, así como L y R, se representan como cadenas de ceros.

• L = 0

• R = 00

• Símbolos de Ó: a partir de 000 en adelante.

• Espacio en blanco: cadena vacía.

- Cada transición se puede representar como un conjunto de cadenas de ceros separadas

cada una por un único 1.

- El conjunto de transiciones de la máquina se representa como la secuencia de cadenas

de ceros y unos de todas sus transiciones, poniendo un 1 al principio del todo y un 1 al

final, y un solo 1 para separar dos transiciones consecutivas.

Teoría de Autómatas I

Máquinas de Turing y lenguajes estructurados por frases -10-

Máquinas de Turing universales

- Son máquinas de Turing programables que pueden simular a cualquier otra máquina

de Turing.

• Programa: máquina de Turing simulada codificada + cinta de entrada (con un 1

al principio y un 1 al final).

- Constan de 3 cintas:

• 1ª cinta: programa + cadena de entrada.

* Contendrá la salida de la máquina.

• 2ª cinta: área de trabajo (manipulación de datos).

• 3ª cinta: estado actual de la máquina simulada.

- La máquina universal:

• Copia la cadena de entrada de la cinta 1 a la cinta 2.

• Graba el código del estado inicial en la cinta 3.

• Busca una transición aplicable en la máquina codificada de la cinta 1. Cuando la

encuentra:

* Realiza la transición en la cinta 2.

* Escribe el nuevo estado en la cinta 3.

• La máquina universal continúa con este proceso hasta que llega al estado de

parada de la máquina simulada. Entonces copia la cinta 2 en la cinta 1, coloca la

cabeza de la cinta 1 donde se encontraba la de la cinta 2 y se detiene.

Lenguajes aceptables y decidibles

- Lenguaje decidible: es aquel lenguaje L para el cual existe una máquina de Turing que

puede aceptar cualquier cadena w∈L y rechazar cualquier cadena w∉L.

- Lenguaje aceptable: es aquel lenguaje L para el cual no existe ninguna máquina de

Turing que puede aceptar cualquier cadena w∈L y rechazar cualquier cadena w∉L.

- Lenguajes recursivamente enumerables: lenguajes estructurados por frases.

- Lenguajes recursivos: lenguajes decidibles por una máquina de Turing.

El problema de la parada

- Máquina autoterminante: máquina con un alfabeto {0,1,∆} que se detiene cuando se le

mete como entrada una cadena que es ella misma codificada.

- Existen máquinas de Turing para las que no es posible decidir si son autoterminantes o

no: es decir, no puede saberse con certeza si se detienen ⇒ no puede saberse con certeza

si una máquina de Turing se va a detener ante una cadena de entrada ⇒ EL

PROBLEMA DE PARADA NO ES DECIDIBLE.

Propiedades de cerradura de funciones computables

En la sección anterior introdujimos a las funciones computables como aquellas que son calculables por programas-while . En esta sección presentaremos algunas propiedades de cerradura de las funciones computables, vale decir, presentaremos algunos esquemas de composición de funciones tales que actuando sobre funciones computables dan, también, funciones computables. Veremos también que, aunque la clase de funciones computables es muy grande, es numerable. Esto, con un simple argumento de cardinalidad de conjuntos, implica que hay una gran cantidad de funciones de los naturales en los naturales que no son computables.


Si A y B son dos conjuntos, escribiremos

para denotar a las funciones con dominio en A y contradominio en B.

Programas y funciones computables

Como ya comentamos en el cap´ıtulo anterior, para abordar cuestiones acerca de la computabilidad

necesitamos elegir un modelo de computacion, que nos permita precisar lo

que entendemos por procedimiento efectivo o algoritmo. De esta forma, los algoritmos

estar´an bien definidos y, por tanto, ser´an susceptibles de ser estudiados en Matem´aticas

como cualquier otra teor´ıa. En general, la expresi´on formal de un algoritmo en un modelo

concreto se denomina programa, si el modelo est´a basado en un lenguaje de programaci´on,

o m´aquina, si el modelo es una representaci´on formal orientada a un tipo especial de

procedimiento mec´anico, en el que se hace referencia expl´ıcita a la gesti´on de la memoria

de trabajo donde se almacenan datos.

2.1. El lenguaje de programaci´on GOTO

En esta secci´on introducimos el lenguaje GOTO, que proporciona el modelo de computaci

´on con el que trabajaremos durante el curso. Est´a dise˜nado para manejar n´umeros

naturales. En una primera aproximaci´on podemos decir que este lenguaje consta de:

1. Variables:

(a) Variables de entrada: X ´ X1;X2; :::;Xn; :::

(b) Variables locales: Z ´ Z1;Z2; :::;Zn; :::

(c) Una variable de salida: Y

2. Etiquetas: A ´ A1;B ´ B1;C ´ C1;D ´ D1;E ´ E1;A2;B2;C2;D2;E2; :::

3. Instrucciones: (Con o sin etiquetar)

(a) Incremento: V Ã V + 1

15

I A C C

Dpto. Ccia. Universidad de Sevilla

Cap´ıtulo 2 L´ogica y Computabilidad. 2003–04

(b) Decremento: V Ã V ¡ 1

(c) Condicional: IF V 6= 0 GOTO L

(d) V Ã V

Un programa de GOTO es una sucesi´on finita de instrucciones con o sin etiquetas. Cada

instrucci´on se interpretar´a como una cierta operaci´on b´asica del siguiente modo:

Las instrucciones de un programa se interpretan secuencialmente salvo que

alguna instrucci´on condicional cambie esto. Precisando:

Cada variable usada por el programa almacena un n´umero natural (inicialmente

0, salvo para las variables de entrada).

Las instrucciones act´uan como sigue:

² V Ã V + 1: incrementa en 1 el valor de V .

² V Ã V ¡ 1: resta 1 al valor de V si es distinto de 0, y deja dicho

valor igual si es 0.

² IF V 6= 0 GOTO L: Si V 6= 0 se ejecuta la primera instrucci´on

etiquetada por L (si no existe tal instrucci´on, el programa para); si

V 6= 0, se ejecuta la siguiente instrucci´on.

² V Ã V : No tiene ning´un efecto.

Un programa permite calcular una funci´on dando a las variables de entrada, X1; :::;Xk

unos valores iniciales n1; :::; nk y ejecutando el programa. Si se para (porque no hay pr´oxima

instrucci´on o una instrucci´on condicional nos env´ıa a una etiqueta que no aparece en

el programa etiquetando una instrucci´on) el valor de la funci´on es el valor de la variable

de salida Y .

2.2. Ejemplos

Veamos unos ejemplos de programas en este lenguaje, junto a las funciones que calculan:

Ejemplo 1: Sea P el programa

[A] X Ã X ¡ 1

Y Ã Y + 1

IF X 6= 0 GOTO A

Dpto. Ccia. Universidad de Sevilla 16

L´ogica y Computabilidad. 2003–04 Cap´ıtulo 2

Entonces P(n) = 8<:

1 si n = 0,

n si n 6= 0

; es decir, este programa copia el valor de X en Y , si el

valor no es 0.

Ejemplo 2: Veamos ahora un programa que calcula la funci´on identidad sobre N, es decir

P(n) = n

IF X 6= 0 GOTO B

Z Ã Z + 1

IF Z 6= 0 GOTO E

[B] X Ã X ¡ 1

Y Ã Y + 1

IF X 6= 0 GOTO B

En este programa se ha utilizado un bloque de instrucciones del tipo

Z Ã Z + 1

IF Z 6= 0 GOTO L

cuya ejecuci´on es equivalente a ir incondicionalmente a la etiqueta L; para simplificar

la escritura de los programas, este bloque lo abreviaremos como GOTO L. Pero debe

resaltarse que no hemos a˜nadido ninguna instrucci´on nueva al lenguaje, sino que es una

simple abreviatura de un par de l´ıneas a las que sustituye, es lo que llamamos una macro.

M´as adelante comentaremos c´omo se pueden introducir estas macros en los programas, por

ahora todo lo que necesitamos para poder sustituir una macro por su valor real es utilizar

en ella variables de trabajo que no ocurran en ninguna otra instrucci´on del programa en el

que se encuentre. As´ı, si en un programa ya se utilizara la variable Z, bastar´ıa considerar

un bloque GOTO L del tipo:

Zk à Zk + 1

IF Zk 6= 0 GOTO L

donde la variable Zk no se est´a utilizando.

Ejemplo 3: Damos a continuaci´on un conjunto de l´ıneas en el lenguaje GOTO que nos

permite asignar a una variable el valor nulo. Si V es la variable que queremos anular,

entonces

[A] V Ã V ¡ 1

IF V 6= 0 GOTO A

17 Dpto. Ccia. Universidad de Sevilla

Cap´ıtulo 2 L´ogica y Computabilidad. 2003–04

es un bloque que, insertado convenientemente en un programa (es decir, sustituyendo V

por la variable que queremos anular, y A por una etiqueta que no se est´e utilizando en

dicho programa), produce el efecto de anular la variable. Este bloque de instrucciones lo

abreviaremos por

V Ã 0

Ejemplo 4: El programa dado en el ejemplo 2, en principio, podr´ıa ser interpretado por

una asignaci´on de una variable en otra. Sin embargo, este programa destruye el valor de

la variable X, y por tanto su acci´on no ser´ıa la deseada de asignar solamente el valor de

X al de Y . Para obtener un programa que realice la asignaci´on, seguiremos dos pasos,

uno primero en que el valor de X se copia en dos variables, Y y Z, y se pierde el de X, y

un segundo paso en el que se copia el valor de Z en X, perdi´endose el de Z; el resultado

final es que X mantiene su valor, e Y (la variable de salida) toma el valor de X.

[A] IF X 6= 0 GOTO B

GOTO C

[B] X Ã X ¡ 1

Y Ã Y + 1

Z Ã Z + 1

GOTO A

[C] IF Z 6= 0 GOTO D

GOTO E

[D] Z Ã Z ¡ 1

X Ã X + 1

GOTO C

De esta forma, podemos hablar de la asignaci´on: V Ã V 0, cuyo bloque correspondiente

ser´ıa el programa anterior sustituyendo X por V 0, Y por V y teniendo cuidado con las

variables auxiliares y las etiquetas para que no aparezcan en el programa en que usamos

la macro.

Dpto. Ccia. Universidad de Sevilla 18

L´ogica y Computabilidad. 2003–04 Cap´ıtulo 2

Ejemplo 5: La funci´on suma:

Y Ã X1

Z Ã X2

[B] IF Z 6= 0 GOTO A

GOTO E

[A] Z Ã Z ¡ 1

Y Ã Y + 1

GOTO B

Consider´andola como macro, la notaremos como

V Ã V1 + V2

Ejercicio 6: A partir de la funci´on anterior es f´acil definir la funci´on producto como:

Z2 Ã X2

[B] IF Z2 6= 0 GOTO A

GOTO E

[A] Z2 Ã Z2 ¡ 1

Z1 Ã X1 + Y

Y Ã Z1

GOTO B

Al programa anterior, consider´andolo como macro, lo notaremos:

V Ã V1 ¢ V2

Como ejemplo, veamos como quedar´ıa este programa si no hubi´eramos usado la abreviatura

(macro) de la suma. Obs´ervese c´omo ha habido que renombrar las variables y las

etiquetas para que no coincidan con las que ya existen en las restantes l´ıneas del programa:

19 Dpto. Ccia. Universidad de Sevilla

Cap´ıtulo 2 L´ogica y Computabilidad. 2003–04

Z2 Ã X2

[B] IF Z2 6= 0 GOTO A

GOTO E

[A] Z2 Ã Z2 ¡ 1

Z1 Ã X1

Z3 Ã Y

[B2] IF Z3 6= 0 GOTO A2

GOTO E2

[A2] Z3 Ã Z3 ¡ 1

Z1 Ã Z1 + 1

GOTO B2

[E2] Y Ã Z1

GOTO B

Evidentemente, el programa anterior se podr´ıa seguir expandiendo, sustituyendo las asignaciones

por bloques que realicen esa operaci´on (que ya hemos visto), y las ramificaciones

incondicionales por el bloque correspondiente (teniendo cuidado siempre con las variables

y etiquetas que se usen en la expansi´on).

2.3. Sintaxis de GOTO

Demos ahora la definici´on formal del lenguaje GOTO.

Definici´on: El lenguaje GOTO consta de:

1. Un s´ımbolo que denominaremos variable de salida, y que denotaremos por Y , y dos

conjuntos numerables de s´ımbolos:

fX1; :::;Xn; :::g; fZ1; :::;Zn; :::g

que denominaremos, respectivamente, variables de entrada y variables de trabajo o

auxiliares.

2. Un conjunto de s´ımbolos, tambi´en numerable, distinto de los anteriores, y que denominaremos

etiquetas:

fA1;B1;C1;D1;E1;A2; :::;E2; :::g

Dpto. Ccia. Universidad de Sevilla 20

L´ogica y Computabilidad. 2003–04 Cap´ıtulo 2

3. Para cada variable de GOTO, V , las siguientes expresiones son instrucciones:

V Ã V + 1

V Ã V ¡ 1

V Ã V

Si K y L son etiquetas, las siguientes expresiones son instrucciones:

IF V 6= 0 GOTO L

[K] V Ã V + 1

[K] V Ã V ¡ 1

[K] V Ã V

[K] IF V 6= 0 GOTO L

Definici´on: Un programa de GOTO es una sucesi´on finita de instrucciones con o sin

etiquetas. Es decir, un programa, P, es una sucesi´on I1; :::; Ik, donde Ij 2 Ins. A k se le

denomina longitud de P.

Nota:

Como ´unica salvedad, prohibiremos que la ´ultima instrucci´on de P sea la instrucci´on

Y Ã Y , por motivos que veremos en temas posteriores. De hecho, debido a su

interpretaci´on (no tiene efecto), una instrucci´on de este tipo al final de un programa

puede ser eliminada sin alterar el comportamiento de ´este.

Un caso l´ımite de programa es el programa vac´ıo, es decir, el programa sin instrucciones,

que se considera de longitud 0.

Definici´on: Para cada instrucci´on, I, de un programa, P, definimos var(I) como:

var(I) = V si I 2 fV Ã V; V Ã V + 1; V Ã V ¡ 1; IF V 6= 0 GOTO Lg

El conjunto de variables del programa P = I1; :::; Ik es:

var(P) = fvar(Ij) : j = 1; :::; kg

Definici´on: Dado un programa, P, de GOTO, un estado de P es un conjunto finito, ¾,

de pares ordenados, ¾ µ V ar £N, tal que para cada variable V 2 var(P) existe un ´unico

par (V;m) 2 ¾.

21 Dpto. Ccia. Universidad de Sevilla

Cap´ıtulo 2 L´ogica y Computabilidad. 2003–04

Esencialmente, ¾ se puede ver como una funci´on ¾ : V ar ¡ ¡! N, con var(P) µ dom(¾).

Como es habitual cuando tratamos con funciones, denotaremos por ¾(V ) al ´unico n´umero

natural tal que (V; ¾(V )) 2 ¾, y diremos que es el valor de V en ¾.

Una forma de representar habitualmente los estados de un programa es como un conjunto

finito de ecuaciones de la forma V = m.

Ejemplo: Si P es el programa del ejemplo 2, entonces fX = 5; Y = 7; Z = 3g es un

estado de P (aunque nunca se llegue a alcanzar), fX = 5; Y = 3; Z = 3g es otro estado;

sin embargo, fX = 5; Z = 3g y fX = 5; X = 3; Z = 2; Y = 0g no son estados de P.

Definici´on: Dado un programa, P, de longitud n, una descripci´on instant´anea de P es

un par (i; ¾), donde ¾ es un estado de P, y 1 · i · n + 1.

Si i = n + 1 diremos que (i; ¾) es terminal.

Si V 2 var(P), el valor de V en la descripci´on instant´anea s = (i; ¾) es ¾(V ), y se denota

por s(V ).

Definici´on: Sea P = I1; :::; In un programa en GOTO. Dada un descripci´on instant´anea

no terminal, s = (i; ¾), definimos el sucesor de s como la descripci´on instant´anea (j; ¿ )

dada como:

Caso 1: Si Ii es V Ã V , entonces j = i + 1, y ¿ = ¾.

Caso 2: Si Ii es V Ã V + 1 entonces j = i + 1 y ¿ (W) = 8<:

¾(V ) + 1 si W = V

¾(W) si W 6= V

Caso 3: Si Ii es V Ã V ¡1, entonces j = i+1 y ¿ (W) = 8>><>>:

¾(W) si W 6= V

0 si ¾(V ) = 0

¾(V ) ¡ 1 si ¾(V ) 6= 0

.

Caso 4: Si Ii es IF V 6= 0 GOTO L, entonces ¿ = ¾ y

² Si ¾(V ) = 0 entonces j = i + 1.

² Si ¾(V ) 6= 0 y existe una instrucci´on de P con la etiqueta L, entonces

j = m´ınfi : Ii tiene L como etiquetag

² En otro caso j = n + 1.

Para instrucciones etiquetadas la definici´on es la misma.

Dpto. Ccia. Universidad de Sevilla 22

L´ogica y Computabilidad. 2003–04 Cap´ıtulo 2

Definici´on: Una computaci´on de un programa P es una sucesi´on finita s1; :::; sk de descripciones

instant´aneas tal que:

1. Para cada i = 1; :::; k ¡ 1, si+1 es el sucesor de si.

2. sk es una descripci´on instant´anea terminal

3. s1 = (1; ¾), donde ¾ es un estado de P.

Ejemplo: Para el ejemplo 2 visto anteriormente, si tomamos s1 = (1; fX = 3; Y =

0; Z = 0g), la computaci´on que se obtiene es:

IF X 6= 0 GOTO B

Z Ã Z + 1

IF Z 6= 0 GOTO E

[B] X Ã X ¡ 1

Y Ã Y + 1

IF X 6= 0 GOTO B

s1 = (1; fX = 3; Y = 0; Z = 0g)

s2 = (4; fX = 3; Y = 0; Z = 0g)

s3 = (5; fX = 2; Y = 0; Z = 0g)

s4 = (6; fX = 2; Y = 1; Z = 0g)

s5 = (7; fX = 2; Y = 1; Z = 0g)

s6 = (4; fX = 2; Y = 1; Z = 0g)

s7 = (5; fX = 1; Y = 1; Z = 0g)

s8 = (6; fX = 1; Y = 2; Z = 0g)

s9 = (7; fX = 1; Y = 2; Z = 0g)

s10 = (4; fX = 1; Y = 2; Z = 0g)

s11 = (5; fX = 0; Y = 2; Z = 0g)

s12 = (6; fX = 0; Y = 3; Z = 0g)

s13 = (7; fX = 0; Y = 3; Z = 0g)

s14 = (8; fX = 0; Y = 3; Z = 0g)

Definici´on: Dado un programa P, y k ¸ 1, P define una funci´on Ã(k)

P : Nk¡ ¡! N como

sigue:

Dado (n1; :::; nk) 2 Nk, sea ¾ el estado de P definido por:

¾(Xi) = ni; 1 · i · k.

¾(Y ) = 0.

¾(V ) = 0; 8 V 2 var(P); V 6= Xi (i = 1; :::; k).

Sea s1 = (1; ¾). Distinguimos dos casos:

Caso 1: Si existe una computaci´on s1; :::; sr de P, entonces Ã(k)

P (n1; :::; nk) #

y Ã(k)

P (n1; :::; nk) = sr(Y ).

23 Dpto. Ccia. Universidad de Sevilla

Cap´ıtulo 2 L´ogica y Computabilidad. 2003–04

Caso 2: No existe una computaci´on de P cuya descripci´on instant´anea

inicial sea si. Entonces Ã(k)

P (n1; :::; nk) ".

Ã(k)

P es la funci´on k-aria calculada por el programa P.

Definici´on: Diremos que una funci´on f : Nk¡ ¡! N es GOTO-computable si existe un

programa P de GOTO tal que Ã(k)

P = f, es decir, 8~x 2 Nk; f(~x) ' Ã(k)

P (~x)

2.4. Macros

Sea P un programa de GOTO que calcula una funci´on f : Nk¡ ¡! N. Podemos

suponer que var(P) = fY;X1; :::;Xn;Z1; :::;Zkg y que todas las etiquetas que aparecen

en P son E;A1; :::;Ar. Cumpli´endose adem´as que para cada instrucci´on de la forma

IF V 6= 0 GOTO Ai existe otra instrucci´on en P etiquetada por Ai. (En caso de que

P no verificase estas instrucciones podemos conseguir otro programa P0 a partir de ´el

sustituyendo convenientemente las etiquetas que aparecen en P y trabajar´ıamos con este

nuevo programa P0, que calcula la misma funci´on).

Escribiremos este programa como P = P(Y ;X1; :::;Xn;Z1; :::;Zk;E;A1; :::;Ar), para cada

m sea

Qm = P(Zm;Zm+1; :::;Zm+n;Zm+n+1; :::;Zm+n+k;Em;Am+1; :::;Am+r)