View
46
Download
1
Category
Preview:
Citation preview
Máquinas que comen máquinas
To iterate is human, to recurse divine.—L. Peter Deutsch
Ivan Meza
Máquinas de TuringEs una tupla (Q, Σ, Γ, , B, A, δ)q0
conjunto finito de estados alfabeto de cadenas reconocidas alfabeto de cinta, estado inicial Símbolo de espacio en blanco pero estados finales
función de transición
QΣΓ Σ ⊂ Γq0B B ∈ Γ B ∉ ΣAδ Q × Γ → Q × Γ × {der, izq}
Jerarquía de ChomskyLenguaje Gramática Máquina Ejemplo
Tipo 0 ( )
Máquina de Turing,APDo, AC
??
Tipo 1 ( )
Autómata lineal confronteras
Tipo 2 ( )
Autómata de pila
Tipo 3 ( )
Autómata finito
/LRE LRec
α → β
LDC
αV β → αγβww, anbncn
LLC
V → αw ,wr anbn
Lreg
V → aA|ϵw, a∗
Lo que sabemos
Las máquinas que al pasar por un estado �nal terminanaceptando la cadena, otras que no tienen una transición yrechazan la cadena, pero de vez en cuando se pueden quedaren un ciclo
Si la cadena debe ser aceptada por la MT, eventualmentellegará al estado aceptor; si la cadena debe ser rechazadapuede llegué a una transición inexistente o se quede en unciclo.
Las autómatas �nitos, autómatas de pilas, autómatas confrontera lineal, son máquinas aceptoras: verdadero o falso
Entonces las MT contienen máquinas aceptoras
Codificación de una cadena δ( , ) = ( , , )qi Xj qk Xl Dm
Asignar a cada estado , a cada símbolo de y cada dirección unenteroCodificar cada entrada de la MT como Separar cada codificación con doble uno ( )
Q Γ
0i10j10k10l10m
11
Ejemplo δ( , 1) = ( , 0, R)q1 q3 0100100010100
δ( , 0) = ( , 1, R)q3 q1 0001010100100δ( , 1) = ( , 0, R)q3 q2 00010010010100δ( , B) = ( , 1, L)q3 q3 0001000100010010
Con = 1, = 2, = 3; 0 = 1, 1 = 2, B = 3; L = 1, R = 2q1 q2 q3
01001000101001100010101001001100010010010100110001000100010010
Máquina de Turing Universal
It is possible to invent a single machine which can be used tocompute any computable sequence. If this machine issupplied with a tape on the beginning of which is written theS.D ["standard description" of an action table] of somecomputing machine , then will compute the samesequence as .
U
M UM
Turing, 1936
Es posible inventar una máquina que pueda ser usada paracomputar cualquier secuencia computable. Si esta máquina se le provee con una cinta en la que al principio se le escribe ladescripción estándar de una tabla de acción de algunamáquina , entonces computará la misma secuencia que
U
M UM
MTU: Máquina de Turing quepuede simular una MT arbitrariaMu
Lenguaje aceptado= {mw|w ∈ L(M)}Lu
El lenguaje máquinas y cadenas dónde la máquina acepta a lacadena
Verdadero
FalsoW
MTUM
M
Por el momento, haremos la hipótesis que esrecursivo/decidible
Mu
Realización, una MT es una cadena
Como cadena se podía presentar a una máquina de Turinguniversal
Verdadero
Falsom
MTUm
Mi
ii
Las máquinas de Turing que se aceptan a si mismas
= {m|m ∈ L(M)}Ld̄
Las máquinas en realidad son un número, como número laspodemos ordenar
Ordenadas, cada una corresponde a un número entero
Entonces,...
T F F T F
F F F F F
T T T T T
F T F F F
T F T F F
m0 m1 m2 m3 m4 …M0 …M1 …M2 …M3 …M4 …… … … … … … …
T F F T F
F F F F F
T T T T T
F T F F F
T F T F F
m0 m1 m2 m3 m4 …M0 …M1 …M2 …M3 …M4 …… … … … … … …
Md¯ T F T F F …
F F F T F
F T F F F
T T F T T
F T F T F
T F T F T
m0 m1 m2 m3 m4 …M0 …M1 …M2 …M3 …M4 …… … … … … … …
Md F T F T T …
El lenguaje de las máquinas que no se aceptan a si mismas = {m|m ∉ L(M)}Ld
Si es RE o Rec existe una máquina de Turing, , ¿qué pasacon su descripción ?
Md
md
Si , quiere decir que no se acepta a si misma, peropara eso tendría que aceptarla, que la hace una máquinaque se acepta a si misma, contradicción
∈md Ld
Md
Si , quiere decir que se acepta a si misma, pero paraeso no tendría que aceptarla, que la hace una máquinaque no se acepta a si misma, contradicción
∉md Ld
Md
existe afuera de lasmáquinas de TuringLd
Lenguaje Gramática Máquina Ejemplo
No RE -- --
Tipo 0 ( )
Máquina de Turing,APDo, AC
??
Tipo 1 ( )
Autómata lineal confronteras
Tipo 2 ( )
Autómata de pila
Tipo 3 ( )
Autómata finito
Ld
/LRE LRec
α → β
LDC
αV β → αγβww, anbncn
LLC
V → αw ,wr anbn
Lreg
V → aA|ϵw, a∗
Lenguajes aceptados por máquinas aceptoras: recusivos odecidibles
¿Las máquinas de Turing son las máquinas aceptoras?
Sabemos que las máquinas Turing tiene un límite
MT Verdadero
FalsoW
Imaginemos
MT Verdadero
FalsoW
Verdadero
Falso
Complemento de todos los recursivos son recursivo
Lenguaje aceptado
Verdadero
FalsoW
MTUM
M
= {mw|w ∈ L(m)}Lu
¿Si pasamos nuestra numeración de ?MTi
Si es recursivo, su complemento también...Lu
Verdadero
FalsoW
MTUM
M Verdadero
Falso
¿Si pasamos nuestra numeración de ?MTi
¡Aceptaría ! ¡No es posible! por lo tanto tiene algo raroLd Lu
no es Rec pero RE
Lenguaje Gramática Máquina Ejemplo
No RE -- --
Tipo 0 ( )
Máquina de Turing,APDo, AC
/
Tipo 1 ( )
Autómata lineal confronteras
Tipo 2 ( )
Autómata de pila
Tipo 3 ( )
Autómata finito
Ld
/LRE LRec
α → βLu
LDC
αV β → αγβww, anbncn
LLC
V → αw ,wr anbn
Lreg
V → aA|ϵw, a∗
Sabemos que hay MT que son decidibles: verdadero y falso
Sabemos que hay problemas para los cuales no existe MT, Ld
Sabemos que hay MT que no son decidibles: verdadero, falsoy ciclo
Opciones de una máquina deTuring
¿Cuándo se acepta? Llega a estado aceptor¿Cuándo se rechaza? Llega a estado del que no hay transición dadoel estado de la cinta¿Otra opción? Quedarse en un ciclo infinito
MT Verdadero
FalsoW
Modelo teórico: instantáneoAceptar (T) Llega a estado aceptorRechazar (F) Se queda en estado no aceptorLoop infinito Rechazó o loopinfinito?
Modelo práctico: tiempoAceptar (T) En algún momento llega a estado aceptorRechazar (F) En algún momento llega a estado no aceptorLoop infinito No termina nunca
Ante problemas muy, muy difíciles, no sabemos si sigueprocesando o está en un loop in�nito
Ejemplo de problema muy muydifícilDe un conjunto de números enteros de tamaño ¿existe unacombinación del subconjuntos de ellos que sume ?
NC
¿Cómo se diseña la MT?
N = 1, ∗ 1 = 2 = 2ns21
N = 2, ∗ 2 = 8 = 8ns22
N = 3, ∗ 3 = 24 = 24ns23
N = 10, 0 ∗ 10 = 10, 240 = 10micros21
N = 20, 0 ∗ 20 = 20, 971, 520 = 2milis22
N = 30, 0 ∗ 30 = 32, 212, 254, 720 = 32s23
N = 40, 0 ∗ 40 = 43, 980, 465, 111, 040 = 12h24
N = 50, 0 ∗ 50 = 56, 294, 995, 342, 131, 200 = 651d25
¿Por qué mi programa tiene unloop?
Por diseño, loops son importantes desde lenguajes regulares
¿Por qué mi programa tiene unloop infinito?
Un errorPor diseño, interfaz gráfica, satélites, switches, robots
Hecho de la computación: los loops son básicos en lacomputación
Pero nos meten en problemas rápidamente
¿Qué hay de lenguajesrecursivos?
El lenguaje de las máquinas y cadenas que se aceptan en pasos
n
= {mw|w ∈ L(M) en n pasos}Ln
Enumeremos todas las codi�caciones de automatas linealescon frontera (MT) decidibles, { , , …}M1 M2
Enumeramos todas las cadenas de Σ∗
= { | ∉ L( )}Lf̄ xi xi Mi
Si fuera sensitivo al contexto, una de máquina aceptaría atodas las cadenas dentro de , que va encontra de la definición.Por lo tanto no es sensitivo al contexo.Sin embargo, si es decidible ya que la máquina lo único quetiene que hacer es simular a cada con (es decir, es universal),pero no se queda trabada porque se trata de máquinas decidibles
Lf̄ Mx
Lf̄
Mf̄
Mi xi
Lenguaje Gramática Máquina Ejemplo
No RE -- --
Tipo 0 ( )
Máquina de Turing,APDo, AC
/ ,
Tipo 1 ( )
Autómata lineal confronteras
Tipo 2 ( )
Autómata de pila
Tipo 3 ( )
Autómata finito
Ld
/LRE LRec
α → βLu Ln Lf̄
LDC
αV β → αγβww, anbncn
LLC
V → αw ,wr anbn
Lreg
V → aA|ϵw, a∗
ivanvladimir@gmail.com ivanvladimir.github.io ivanvladimir
Máquinas de Turing o máquinas con cola by islicensed under a
. Creado a partir de la obra en
.
Ivan V. Meza RuizCreative Commons Reconocimiento 4.0Internacional License
http://turing.iimas.unam.mx/~ivanvladimir/slides/lfya/mt.html
Recommended