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

Recursivamenteenumerables

Tipo 0 ( )

Máquina deTuring

??

Dependiente delcontexto

Tipo 1 ( )

Autómata dedoblepila/lineal confronteras

Independientedel contexto

Tipo 2 ( )

Autómata depila

Regular Tipo 3 ( )

Autómatafinito

α → β

αV β → αγβww, anbncn

V → αw ,wr anbn

V → aA|ϵw, a∗

Lo que sabemos

Si existe una máquina de Turing para el lenguaje, se trata deun lenguaje recursivamente enumerable

Con autómatas finitos, autómatas de pilas, autómatas dedoble pila y autómatas con frontera 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 q30001000100010010

Con = 1, = 2, = 3; 0 = 1, 1 = 2, B = 3; L = 1, R = 2q1 q2 q3

01001000101001100010101001001100010010010100110001000100010010

Máquin de Turing Universal

It is possible to invent a single machine which can be used tocompute any computable sequence. If this machine is

supplied 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 same

sequence 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 leescribe la descripción estándar de una tabla de acción de

alguna máquina , entonces computará la mismasecuencia que

U

M UM

MTU: Máquina de Turing que puedesimular una MT arbitraria

Mu

Lenguaje aceptado y su correspondiente = {mw|w ∈ L(m)}Lu Mu

Verdadero

FalsoW

MTUM

M

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 u otrasmáquinas

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

M c0 M c

1 M c2 M c

3 M c4 …

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

M c0 M c

1 M c2 M c

3 M c4 …

M0 …M1 …M2 …M3 …M4 …… … … … … … …

Md T F T F F …

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

M c0 M c

1 M c2 M c

3 M c4 …

M0 …M1 …M2 …M3 …M4 …… … … … … … …

Md F T F T T …

¡ no existe!Md

¡No es recursivamente enumerable!

= {m|mm ∉ (mm)}Ld Mu

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 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 no es decidibleLd Lu

RE no R

Sabemos que hay MT que son decidibles: verdadero y falso

Sabemos que hay otras MT: complemento de Mu

Sabemos que hay problemas para los cuales no existe MT, Ld

¿Qué hace diferente RE a R?

Máquina H

Para

No paraw

MTUM

M Verdadero

Falso

Dado un par podemos saber si la máquina va a pararM, w

Depende de , entonces es RE, por lo tanto el no parar es latercera opción

Mu

Supongamos que existe Mhalt

Es posible definir la siguiente máquina a partir de ella

Para

H'M

H Para

No para

Para

H'H'

H Para

No para

Sí para con , también lo hace , pero por definición sequeda en un cicloSí se cicla con , también lo hace con , pero por definiciónse para

H ′ H ′ H

H ′ H ′ H

Opciones de una máquina de Turing¿Cuándo se acepta? Llega a estado aceptor¿Cuándo se rechaza? Llega a estado del que no hay transicióndado el 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 noaceptorLoop 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 noaceptorLoop infinito No termina nunca

Ante problemas muy, muy difíciles, no sabemos si sigueprocesando o está en un loop infinito

Ejemplo de problema muy muy difícilDe un conjunto de números enteros de tamaño ¿existe una

combinación del subconjuntos de ellos que sume ?N

C

¿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 un loop?Por diseño, loops son importantes desde lenguajesregulares

¿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

Jerarquía de Chomsky extendida*Lenguaje Gramática Máquina Ejemplo

No RE -- --

RE/Rec Tipo 0 ( )

Máquina deTuring

,

Dependientedel contexto

Tipo 1 ( )

Autómata dedoble pila/linealcon fronteras

Independientedel contexto

Tipo 2 ( )

Autómata depila

Regular Tipo 3 ( )

Autómata finito

Ld

α → βmw mmi

αV β → αγβww, anbncn

V → αw ,wr anbn

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