Se van a cubrir los temas siguientes:
En latín:
¿Que podemos hacer con piedritas?
Se puede hacer operaciones simples: sumar, restar, comparar, etc.
Y operaciones más complicadas combinando operaciones básicas: multiplicar, etc.
Cálculo: series de operaciones que se realizan para obtener un resultado.
¿Cuáles son las cosas que se pueden calcular?
"f es computable si existe un procedimiento efectivo p tal que p(x) = f(x) para toda x"
Un "procedimiento efectivo" es un cálculo que se puede hacer en el mundo real (con papel y lapizera).
¿Pero cómo hacemos explicito lo que es un procedimiento efectivo?
¿Qué modelo podemos proponer para representar matemáticamente la noción de cálculos del mundo real?
¿Qué problemas podemos resolver?
¿Qué podemos conocer?
Como problemas, consideramos funciones booleanas sobre un alfabeto binario:
f: {0, 1} * ↦ {0, 1}
Queremos ser capaces de, dada cualquiera palabra x ∈ {0, 1} * , calcular si f(x) vale 1 o 0.
Es decir contestar por "si" o por "no" alguna pregunta f acerca de x.
Una palabra booleana parece simple pero puede representar muchas cosas: números, grafos, fórmulas, etc.
De esta forma podemos formular cualquier problema "si/no" acerca de objetos que se tienen una representación binaria.
"¿x tiene una mayoria de 1?"
"¿x es de la forma {0^n, 1^n}?"
"¿x es representa una formula proposicional satisfacible?"
"¿x representa un grafo que se puede colorar con 3 colores?"
"¿x representa < G, a, b > con G un grafo y existe un camino entre los nodos a y b?"
Circuitos Booleanos
Automatas Finitos
Ver Great Ideas in Theoretical Computer Science, Lecture 3, de Scott Aaronson (secciones 3 a 6).
Hay muchos lenguajes que parecen simples de decidir, pero los automatas no llegan, por ejemplo:
Restricciones de los automatas:
Relajando estas restricciones, vamos a considerar otro modelo de cálculo.
Propuesta por Alan Turing en el 1936 bajo el nombre "computing machine", en su artículo "On Computable Numbers".
Características:
En casa paso de un cálculo, una máquina de Turing elije:
Lo hace en función de su estado actual y del símbolo que está leyendo.
Una Máquina de Turing es una lista de reglas de la forma siguiente:
Implica:
Generalizamos a máquinas que tienen más de una cinta (1 para el input, otras para cálculos intermedios).
Tienen:
Separamos la cinta de input (en lectura sola) de las otras para poder medir la cantidad de memoria usada por la máquina.
Una MT es un tuple (k, Γ , Q, δ) con:
Llamamos configuración de una máquina el estado activo junto al contenido de sus cintas y la posición de sus cabezales.
La configuración inicial con una entrada x ∈ {0, 1} * es:
Una máquina corre aplicando pasos de acuerdo a su función de transición, a partir de una configuración inicial.
Dada x ∈ {0, 1} * , una corrida de una máquina M con entrada x puede:
Una MT M computa una función f: {0, 1} * ↦ {0, 1} si para toda x ∈ {0, 1} * , M(x) = f(x).
Una MT decide el lenguaje Lf si computa su función característica f.
Un lenguaje es decidible si existe una MT que lo decide.Enunciar las reglas de una Máquina de Turing que detecta palabras capicúas. Es posible definirla con 2 cintas o 1 sola, pero es más simple con 2.
Aún sin ningun estado interno y solo modificando la cinta de input, una Máquina de Turing puede decidir lenguajes que un automata no puede.
En el artículo "The uniform halting problem for generalized one state Turing machines" de Hermann, ver el ejemplo para el lenguaje AanbmB con n < m.
Desarrollarlo con el ejemplo AaabbbB.
Vimos las Máquinas de Turing como automatas con más capacidad.
Otra manera de verlo, es que son una abstraccion de una persona llevando a cabo un cálculo usando una hoja de papel.
Alan Turing procedió así:
En algunos lados, se define que una MT tiene una cinta de output, donde se escribe el resultado del cálculo, y que tiene un solo estado de detencion qhalt.
En el artículo de Turing ("On Computable Numbers"), las máquinas no se detienen y producen secuencias infinitas de dígitos de nombres reales.
Demostrar:
Si M reconoce L, entonces:
Si M decide L, entonces:
Es decir M siempre se detiene, con cualquier entrada.
Notación O: dadas funciones f, g: N ↦ N. Escribimos f ∈ O(g) si existen una constante c > R + y un rango n ∈ N tales que para toda m > n, f(n) ≥ c. g(n).
Decimos que f es acotada por g (módulo un factor multiplicativo) a partir de un cierto rango (o en el infinito).
En lugar de pensar el conjunto de estados de una máquina como uno solo, podemos decir que una máquine tiene más de un estado activo.
Es igual tener n estados activos, cada uno tomando valores en un conjunto Qi, que un solo estado activo tomando valores en el conjunto Q1 × Q2 × … × Qn.
Eso permite "almacenar" información (solo valores dentro de un conjunto fijo).
Para toda f: {0, 1} * ↦ {0, 1} y T: N ↦ N constructible en tiempo, si f es computable por una MT M con k ≥ 2 cintas y un alfabeto Γ en tiempo T(n), entonces es computable por:
Se puede representar cualquier elemento de Γ de forma binaria usando log2( ∣ Γ ∣ ) bits (redondeado para arriba).
Para cada celda de M, hay log2( ∣ Γ ∣ ) celdas en Mʹ.
Para simular un paso de M, Mʹ usa:
Los estados de Mʹ tienen que almacenar: el estado de M, k símbolos de Γ , un contador de 1 a log2( ∣ Γ ∣ ).
En Mʺ las celdas 1, k + 1, 2k + 1. . . representan la primera cinta de M, las celdas 2, k + 2, 2k + 2, . . . la segunda, etc.
Doblamos el tamaño del vocabulario de M, usando para cada símbolo a, su versión "marcada" â que representa la posición del cabezal.
Ejecución de Mʺ con entrada x:
M corre en T(n) pasos, entonces solo modifica celdas a una distancia de T(n) del principio de cada cinta. El recorrido hecho por Mʺ para cada paso de M dura 2T(n) pasos. Entonces Mʺ corre en tiempo O(T(n)2).
Substitución de MT con cinta infinita en las dos direcciones, por una cinta infinita en una sola dirección.
Más resultados de cambio de tipo de MT con desaceleración polinomial:
Ver slides 23 a 30.
Por el momento, no es necesario entrar en los detalles de codificacion/representacion.
Idea: como entrada de una TM se puede representar
Dado un entero/grafo/automata/MT x, escribimos < x > su representación como palabra binaria.
¿Qué información es requerida para describir una TM?
Por ejemplo dada una TM M = < 2, Γ , Q, δ > , podemos armar una palabra < k, Γ , Q, δ > con < δ > siendo el grafo de δ representado como una lista:
< q0, s0, s0, qn, sw, zi, zw > , < . . . > , < . . . > , . . . (con zi, zw ∈ {←, = , →}).
Consecuencia: podemos establecer una relación uno-a-uno m de los enteros naturales a las máquinas de Turing.
Consideremos la representación binaria del entero natural n. Si representa una Máquina de Turing Mn decimos que m(n) = Mn, sino m(n) = X , con X una maquina de Turing arbitraria que entra en un bucle infinito con todo input.
cardinalidad de todas las máquinas de Turing < cardinalidad de todos los lenguajes
¿Porqué?
Cardinalidad de todos los lenguajes = Cardinalidad de los reales
se demuestra con un argumento de diagonalisación de Cantor.
Las máquinas de Turing no alcanzan para decidir todos los lenguajes.
Representando MT como palabras, podemos disenar MT que toman descripciones de otras MT como entrada y hacen cosas divertidas.
En su articulo de 1936, justo después de presentar sus Máquinas, Alan Turing describe una máquina universal.
Una máquina U es universal si para cualquiera máquina M y palabra x ∈ {0, 1} * , U( < M, x > ) = M(x).
Si una máquina es universal, puede leer la descripcion de otra máquina y "ejecutarla" con una palabra de entrada.
Sin máquina universal, tendríamos que construir (físicamente) una máquina por tarea.
Con máquinas universales, tenemos software (máquinas simuladas) corriendo arriba de hardware (máquinas universales).
Construir una MTU U, capaz de simular cualquier MT M con k cintas.
Requiere: lemma k cintas trabajo a 1 cinta trabajo.
¿Cúales son las fases principales de la ejecución de MTU?
¿Cómo simular un paso de M?
¿En cúanto tiempo corre U( < M, x > ) con respeto a M(x)?
Hemos observado que por una diferencia de cardinalidades, hay lenguajes (de hecho, la gran mayoría) que no son decidibles.
Ahora que sabemos representar MT como palabras vamos a ver lenguajes indecidibles particulares que involucran MT.
Las demostraciones de indecidibilidad van a involucrar MTU.
AccTM = { < M, x > ∣ M es una MT y acepta x}
Dibujar una tabla con las MT etiquetando cada línea, y las palabras representando las MT etiquetando cada columna.
La diagonal central representa el resultado de M( < M > ) para toda M.
D está construida para ser distinta de esa diagonal, entonces D no puede aparecer como etiqueta de una linea en esa tabla.
Contradiccion dado que supusimos que la tabla incluía a todas las MT.
HaltMT = { < M, x > ∣ M es una MT y se detiene con entrada x}
HaltMT es el problema de la detención (Halting Problem).
Decidir HaltMT significa poder detectar si una MT va a entrar en un bucle infinito sin ejecutarla.
Por ejemplo podríamos demostrar o infirmar la Conyectura de Goldbach (todos los números ≥ 4 son la suma de dos números primos):
for i = 2 to infinity:
if 2*i is not the sum of two primes:
then HALTSi HaltMT fuera decidible podríamos detectar si este programa terminara.
Suena demasiado lindo...
$ Halt_{MT} = {
La idea es mostrar que su pudieramos decidir HaltMT, podriamos decidir AccTM.
¿Las MT representan todos los procedimientos efectivos?
Como un procedimiento efectivo es una noción informal, no lo podemos demostrar.
Pero algunas cosas indican que sí, es el caso.
Se demostro que tres modelos de calculo:
Eran equivalentes, ie calculaban las mismas funciones.
La hypothesis que las máquinas de Turing representan todos los procedimientos efectivos se llama Tesis de Church-Turing.
Arora y Barak: Capítulo 1 hasta 1.5 incluido (Sin sección 1.2.1, remark 1.7, claim 1.8, section 1.5.2).
Sipser: Capítulo 0. Capítulo 4, sección 2: lenguajes indecidibles y problema de la detención.