Embed Size (px)
Citation preview
La pregunta para la que no me puedodecidir
To iterate is human, to recurse divine.—L. Peter Deutsch
Ivan Meza
La tesis de Turing-Church (relajada)Toda computación real puede ser transformada a una
máquina de Turing
La tesis de Turing-ChurchToda computación efectiva puede llevarse a cabo por una
máquina de Turing
Método efectivo, M está compuesto por un número finito de instrucciones cuando llevado a cabo sin error siempre produce el resultado
deseado en un número finito de pasos puede llevarse a cabo por un humano sin la necesidad de una
computadora, pero con lápiz y papel no necesita de conocimiento externo o ingenuidad de parte
del humano que lo ejecuta
MM
M
M
EvidenciaToda función efectivamente calculable se ha comprobado ser unamáquina de TuringTodos los métodos para obtener nuevas funciones efectivamentecalculables tienen un equivalente en máquina de TuringTodos los intentos de formalizar la noción intuitiva deefectivamente calculable han resultado en el mismo conjunto,recursivo enumerable
Otras formalizacionesCálculo lambdaGramática tipo 0Funciones parcialesrecursivasAlgoritmos PostForma canónica PostAlgoritmos de Markov
VariacionesTodas las funciones físicas computables son Turing-computableUna máquina probabilistica de Turing puede simulareficientemente cualquier modelo razonable de computaciónMáquinas razonables pueden simularse las unas a las otras conun exceso polinomial en tiempo y un factor constante en espacioUna máquina de Turing cuántica puede simular eficientementecualquier modelo realista de computación
Problemas computables, REProblemas no computables, NRE, Ld
Jerarquía de Chomsky extendida*Lenguaje Gramática Máquina Ejemplo
No RE -- --
RE Tipo 0 ( ) MT ,
Rec Tipo 0 ( ) MT decidible
DC Tipo 1 ( ) APDo/ALF
IC Tipo 2 ( ) AP
Reg Tipo 3 ( ) AF
Ld
α → β mw mmi
α → β =1i1j 1i∗j
αV β → αγβ ww, anbncn
V → α w ,wr anbn
V → aA|ϵ w, a∗
Lenguajes decidibles
MT Verdadero
FalsoW
Suma¿Dado dos número en notación unaria, verificar que se
puedan sumar?
Los sumamos
Muy fácili, O(n + m)
Verificación de suma¿Dado tres número en notación unaria, verificar que el último
sea la suma de los dos primeros?
Los sumamos y comprobamos que sean el mismo valor
Muy fácil, O(n + m)
Multiplicación¿Dado dos número en notación unaria, verificar que se
puedan multiplicar?
Los multiplicamos
Más o menos fácil, (naive)O(n ∗ m)
Verificación de multiplicación¿Dado tres número en notación unaria, verificar que el último
sea producto de los dos primeros?
Los multiplicamos y comprobamos que sean el mismo valor
Más o menos fácil, (naive)O(n ∗ m)
Verificar número primos¿Dado un número en notación unaria, es primo?
Dividir número entre factores de hasta 2 n√
¡Más o meno algo de tiempo! O( )n√
Identificar factores¿Dado un número en notación unaria, identificar si es
divisible entre dos factores primos?
Encontrar un par de primos menores a que produzcan elnúmero n
n
¡Más dificil! O( )n∗ n)(√
log(n)2
Verificación factor¿Dado tres número en notación unaria, verificar que el último
sea el producto de los dos primeros?
Los multiplicamos y comprobamos que sean el mismo valor
Más o menos fácil, (naive)O(n ∗ m)
Sacar un elemento de un arreglo Sacar un elemento de un ábol B Verificar que mi usuario esté en la base de datos
O(n)O(log(n))
O(n)
Nuestro talón de aquiles comienza con que el complementode decidibles son decidibles
Lenguajes no decidibles
Problema del paroExiste una máquina de Turing que pueda tomar cualquier
máquina y una entrada y pueda determinar si elprograma para.
Mh
M w
La respuesta es NO
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 i0 i1 i2 i3 i4 …j0 …j1 …j2 …j3 …j4 …… … … … … … …
Cualquiera recursiva/decidibleM(i, j)
La función computable (no decidible)
(i) = {Mg0loop
siM(i, i) = 0otherwise
Sabemos que es computable
Definición de halt
(M, w) = {Mh10
si M para con entrada xotherwise
Dos opciones¿Qué define a ?M Mh
Si entonces , entonces M( , ) = 0Mg Mg ( ) = 0Mg Mg
( , ) = 1Mh Mg Mg
Si entonces loops, entonces M( , ) = 1Mg Mg ( )Mg Mg
( , ) = 0Mh Mg Mg
No hay una que que corresponda con para elprograma
M Mh
Mg
Uno de los primeros problemas descubiertos ser nodecidibles
Es común transformar problemas al problema de paro parademostrar que también son no decidibles
Teorema de RiceToda propiedad no trivial de los lenguajes RE es indecidible
Todo conjunto de lenguajes de RE es unapropiedad
y RE son propiedades triviales∅
El conjunto de que regresan verdadero para toda El conjunto de que no aceptan al lenguaje vacioEl conjunto de que corresponde a un lenguajes libres decontexto
M wMM
La app va a vigilarmeLa app va alentar micelularLa app va a pasmarse
No recursivamente enumerables
Nuestro talón de aquiles continua con que hay problemaspara los cuales no hay una MT
y son Rec y no en RE
y no enRE
L L¯ ¯¯̄
L L¯ ¯¯̄
L ∈ RE ⋂ R¯ ¯¯̄
L¯ ¯¯̄
Los complementos de REM_u=\{[M,w] | w \in L(M) } \}
\overline{M_u}=\{[M,w] | w \not \in L(M) \text{y }M\text{i no una máquina de Turing\}
Los complementos de REh = {[M, w]|w ∈ L(M) y para}
= {[M, w]|w ∈ L(M)no para si M es una máquina de Turing oh¯¯̄
M no es una Máquina de Turing
El conjunto de que regresan falso para toda o no es unaMTEl conjunto de que aceptan al lenguaje vacio o no es unaMTEl conjunto de que corresponde a los lenguajes no son libresde contexto o no es una MT
M w M
M M
MM
La app no va a vigilarmeLa app no va alentar micelularLa app no va a pasmarse
[email protected] ivanvladimir.github.io ivanvladimir
La pregunta para la que no me puedo decidir 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/problems.html
