M´aquinas de Turing y otros artilugios 1er Encuentro de Educaci´ on en Ciencia de la Computaci´on
Luis Sierra Instituto de Computaci´ on
1 de Noviembre del 2012
Luis Sierra (InCo)
M´ aquinas
EECC 2012
1 / 22
Plan
M´aquinas de Turing
Luis Sierra (InCo)
M´ aquinas
EECC 2012
2 / 22
Plan
M´aquinas de Turing Otros artilugios
Luis Sierra (InCo)
M´ aquinas
EECC 2012
2 / 22
Plan
M´aquinas de Turing Otros artilugios 1
2
3
m. Mecanismo, artefacto, sobre todo si es de cierta complicaci´on. U. m. en sent. despect. m. Ardid o ma˜ na, especialmente cuando forma parte de alg´ un plan para alcanzar un fin. m. Herramienta de un oficio.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
2 / 22
Luis Sierra (InCo)
M´ aquinas
EECC 2012
3 / 22
Procesos combinatorios finitos (Journal of Symbolic Logic, Vol.1, Iss.3, 1936)
Tenemos en mente un problema general formado por una clase de problemas especificos. Una soluci´ on al problema general proporcionar´a una respuesta a cada problema espec´ıfico. En la siguiente formulaci´on de la soluci´ on participan dos conceptos: el de un espacio de s´ımbolos en el que se lleva a cabo el trabajo de pasar del problema a la respuesta, y el de un conjunto de instrucciones fijo e inalterable que controla tanto las operaciones en el espacio de s´ımbolos como el orden en que dichas instrucciones se deben aplicar.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
4 / 22
Procesos combinatorios finitos En esta formulaci´on el espacio de s´ımbolos consiste en una secuencia de espacios o casillas, que es infinita en ambos sentidos; es decir, ordinalmente similar a la serie de enteros . . . , -3, -2, -1,0,1,2,3 , . . . El solucionador de problemas, o trabajador, debe moverse y trabajar en este espacio de s´ımbolos, pudiendo ver y operar sobre una u ´nica casilla a la vez. Aparte de la presencia del trabajador, una casilla admite s´olo una de dos condiciones posibles; estar vac´ıa, o tener una marca u ´nica, por ejemplo un trazo vertical. Se debe elegir una casilla llamada el punto de partida. Suponemos que un problema espec´ıfico debe darse en forma simb´ olica por medio de un n´ umero finito de casillas marcadas. Del mismo modo, la respuesta debe darse en forma simb´olica por una configuraci´ on de casillas marcadas. Para ser espec´ıficos, la respuesta es la configuraci´ on de casillas marcadas que quedan luego del proceso de resoluci´ on. Luis Sierra (InCo)
M´ aquinas
EECC 2012
5 / 22
Procesos combinatorios finitos
Se supone que el trabajador es capaz de realizar las siguientes acciones primitivas: (a) Marcar la casilla en que se encuentra (suponi´endola vac´ıa) (b) Borrar la marca de la casilla en que se encuentra (suponi´endola marcada) (c) Moverse a la casilla de la derecha (d) Moverse a la casilla de la izquierda (e) Determinar si la casilla en que se encuentra est´a marcada o no
Luis Sierra (InCo)
M´ aquinas
EECC 2012
6 / 22
Procesos combinatorios finitos El conjunto de instrucciones que, sea dicho, es el mismo para todos los problemas espec´ıficos y por tanto corresponde al problema general, ha de ser de la siguiente forma. Debe comenzar Comience en el punto de partida y siga la instrucci´on 1 Luego, consta de un n´ umero finito de instrucciones numeradas 1, 2, 3, . . . , n . La instrucci´ on i-´esima debe tener alguna de las siguientes formas: (A) Realice la operaci´on Oi [Oi = (a), (b), (c), o (d)] y luego siga la instrucci´on ji (B) Realice la operaci´on (e) y, seg´ un la respuesta es s´ı o no, seguir la instrucci´on ji0 o ji00 (C) Det´engase
Luis Sierra (InCo)
M´ aquinas
EECC 2012
7 / 22
Procesos combinatorios finitos El conjunto de instrucciones que, sea dicho, es el mismo para todos los problemas espec´ıficos y por tanto corresponde al problema general, ha de ser de la siguiente forma. Debe comenzar Comience en el punto de partida y siga la instrucci´on 1 Luego, consta de un n´ umero finito de instrucciones numeradas 1, 2, 3, . . . , n . La instrucci´ on i-´esima debe tener alguna de las siguientes formas: (A) Realice la operaci´on Oi [Oi = (a), (b), (c), o (d)] y luego siga la instrucci´on ji (B) Realice la operaci´on (e) y, seg´ un la respuesta es s´ı o no, seguir la instrucci´on ji0 o ji00 (C) Det´engase
Pero ... ...esta no es la m´aquina de Turing. Luis Sierra (InCo)
M´ aquinas
EECC 2012
7 / 22
Post vs Turing
Finite Combinatory Processes - Formulation 1, Emil L. Post, The Journal of Symbolic Logic, Vol. 1, No. 3, pp. 103-105 (Sep., 1936) On Computable Numbers, with an application to the Entscheidungsproblem, Alan Turing, Proceedings of the London Mathematical Society (2) 42 pp 230-265 (1936-37)
Luis Sierra (InCo)
M´ aquinas
EECC 2012
8 / 22
Post vs Turing
Finite Combinatory Processes - Formulation 1, Emil L. Post, The Journal of Symbolic Logic, Vol. 1, No. 3, pp. 103-105 (Sep., 1936) On Computable Numbers, with an application to the Entscheidungsproblem, Alan Turing, Proceedings of the London Mathematical Society (2) 42 pp 230-265 (1936-37) ¿En qu´e se parecen o diferencian estas propuestas?
Luis Sierra (InCo)
M´ aquinas
EECC 2012
8 / 22
Luis Sierra (InCo)
M´ aquinas
EECC 2012
9 / 22
Luis Sierra (InCo)
M´ aquinas
EECC 2012
9 / 22
Se diferencian en ...
el largo Post: pp. 103-105, Turing: pp 230-265 las marcas En Turing hay marcas de primera clase (0, 1) y marcas de segunda, auxiliares para el c´ omputo, pero que no se consideran resultado del c´ omputo las instrucciones En Turing son de largo fijo (`a la RISC), en Post de largo variable (`a la CISC)
Luis Sierra (InCo)
M´ aquinas
EECC 2012
10 / 22
Se parecen en la implementaci´on
Biblioteca Despliegue Motor Lo diferente Total
Post 18 161 87 41 307
Turing 18 161 87 32 298
El c´ odigo coincide en un 90%.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
11 / 22
Se parecen sus programas
Las instrucciones son tiras finitas. Los programas son tiras finitas de instrucciones.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
12 / 22
Se parecen sus programas
Las instrucciones son tiras finitas. Los programas son tiras finitas de instrucciones. Podemos numerar los programas; asignarle un nombre, o ´ındice a cada programa.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
12 / 22
Se parecen sus programas
Las instrucciones son tiras finitas. Los programas son tiras finitas de instrucciones. Podemos numerar los programas; asignarle un nombre, o ´ındice a cada programa. 1 ? 2 4 2 O 3 3 R 1 4 X
Luis Sierra (InCo)
M´ aquinas
EECC 2012
12 / 22
Se parecen sus programas
Las instrucciones son tiras finitas. Los programas son tiras finitas de instrucciones. Podemos numerar los programas; asignarle un nombre, o ´ındice a cada programa. 1 ? 2 4 1 ? 11 1111 11 O 111 111 R 1 1111 X 2 O 3 3 R 1 4 X
Luis Sierra (InCo)
M´ aquinas
EECC 2012
12 / 22
Se parecen sus programas
Las instrucciones son tiras finitas. Los programas son tiras finitas de instrucciones. Podemos numerar los programas; asignarle un nombre, o ´ındice a cada programa. 1 ? 2 4 1 ? 11 1111 11 O 111 111 R 1 1111 X 2 O 3 3 R 1 1 1 11 1111 11 11 111 111 111 1 1111 1111 4 X
Luis Sierra (InCo)
M´ aquinas
EECC 2012
12 / 22
Se parecen en lo que pueden hacer
Pueden sumar y borrar. Y adem´as calculan funciones constantes, proyecciones, y sucesor Y pueden programar if x=y then w else z
Luis Sierra (InCo)
M´ aquinas
EECC 2012
13 / 22
Se parecen en lo que pueden hacer
Pueden sumar y borrar. Y adem´as calculan funciones constantes, proyecciones, y sucesor Y pueden programar if x=y then w else z O sea, son artilugios que cumplen las siguientes propiedades de Hennie la Propiedad 1, de las funciones b´asicas la Propiedad 4, de selecci´ on
Luis Sierra (InCo)
M´ aquinas
EECC 2012
13 / 22
Tambi´en cumplen la propiedad 2 de Hennie Propiedad de clausura Si tengo un programa P que computa la funci´ on f , y un programa Q que computa la funci´on g , hay un programa P; Q que computa la funci´on g .f .
Luis Sierra (InCo)
M´ aquinas
EECC 2012
14 / 22
Tambi´en cumplen la propiedad 2 de Hennie Propiedad de clausura Si tengo un programa P que computa la funci´ on f , y un programa Q que computa la funci´on g , hay un programa P; Q que computa la funci´on g .f .
Algo as´ı como ... 1
Si computo P con la entrada a
2
y obtengo la salida b
3
que uso de entrada al programa Q
4
que computa la salida c,
5
entonces el programa P; Q computa c a partir de la entrada a
Luis Sierra (InCo)
M´ aquinas
EECC 2012
14 / 22
Tambi´en cumplen la propiedad 2 de Hennie Propiedad de clausura Si tengo un programa P que computa la funci´ on f , y un programa Q que computa la funci´on g , hay un programa P; Q que computa la funci´on g .f .
Algo as´ı como ... 1
Si computo P con la entrada a
2
y obtengo la salida b
3
que uso de entrada al programa Q
4
que computa la salida c,
5
entonces el programa P; Q computa c a partir de la entrada a
Si prefieren, computa la secuencia o la composici´ on de dos programas.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
14 / 22
Tambi´en cumplen la propiedad 3 de Hennie
Propiedad de enumeraci´on Hay un programa universal U que interpreta cualquier otro programa P.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
15 / 22
Tambi´en cumplen la propiedad 3 de Hennie
Propiedad de enumeraci´on Hay un programa universal U que interpreta cualquier otro programa P.
Algo as´ı como ... 1
Si quiero computar P con la entrada a
2
y n es el ´ındice de P
3
invoco al programa int´erprete U con dos argumentos;
4
el ´ındice n y la entrada a
Luis Sierra (InCo)
M´ aquinas
EECC 2012
15 / 22
Se parecen en lo que NO pueden hacer Consideremos un programa Halt que recibe dos argumentos, i y x, y devuelve 1 si el programa con ´ındice i termina al ejecutarse con la entrada x, y 0 en caso contrario.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
16 / 22
Se parecen en lo que NO pueden hacer Consideremos un programa Halt que recibe dos argumentos, i y x, y devuelve 1 si el programa con ´ındice i termina al ejecutarse con la entrada x, y 0 en caso contrario.
el programa con ´ındice i termina con la entrada x ⇒ Halt.i.x = 1
Luis Sierra (InCo)
el programa con ´ındice i NO termina con la entrada x ⇒ Halt.i.x = 0
M´ aquinas
EECC 2012
16 / 22
Se parecen en lo que NO pueden hacer
el programa con ´ındice i termina con la entrada x ⇒ Halt.i.x = 1
el programa con ´ındice i NO termina con la entrada x ⇒ Halt.i.x = 0
Considere el programa siguiente, con ´ındice k: P(x): if Halt.x.x = 1: NO TERMINA else: TERMINA
Luis Sierra (InCo)
M´ aquinas
EECC 2012
16 / 22
Se parecen en lo que NO pueden hacer
el programa con ´ındice i termina con la entrada x ⇒ Halt.i.x = 1
el programa con ´ındice i NO termina con la entrada x ⇒ Halt.i.x = 0
Considere el programa siguiente, con ´ındice k: P(x): if Halt.x.x = 1: NO TERMINA else: TERMINA Consideremos la situaci´on que resulta de invocar P(x) con el argumento k.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
16 / 22
Se parecen en lo que NO pueden hacer
P termina con la entrada k ⇒ Halt.k.k = 1
P NO termina con la entrada k ⇒ Halt.k.k = 0
Considere el programa siguiente, con ´ındice k: P(x): if Halt.x.x = 1: NO TERMINA else: TERMINA Consideremos la situaci´on que resulta de invocar P(x) con el argumento k.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
16 / 22
Diferencias en los art´ıculos de Post y Turing
treinta carillas Turing construye la m´aquina universal (el primer int´erprete).
Luis Sierra (InCo)
M´ aquinas
EECC 2012
17 / 22
Diferencias en los art´ıculos de Post y Turing
treinta carillas Turing construye la m´aquina universal (el primer int´erprete). Turing muestra el problema de la parada.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
17 / 22
Diferencias en los art´ıculos de Post y Turing
treinta carillas Turing construye la m´aquina universal (el primer int´erprete). Turing muestra el problema de la parada. Turing lo aplica al Entscheidungsproblem.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
17 / 22
Diferencias en los art´ıculos de Post y Turing
treinta carillas Turing construye la m´aquina universal (el primer int´erprete). Turing muestra el problema de la parada. Turing lo aplica al Entscheidungsproblem.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
17 / 22
Diferencias en los art´ıculos de Post y Turing
treinta carillas Turing construye la m´aquina universal (el primer int´erprete). Turing muestra el problema de la parada. Turing lo aplica al Entscheidungsproblem.
ENTSCHEIDUNGSPROBLEM Problema de decisi´on de los teoremas de la l´ ogica de primer orden
Luis Sierra (InCo)
M´ aquinas
EECC 2012
17 / 22
Diferencias en los art´ıculos de Post y Turing
treinta carillas Turing construye la m´aquina universal (el primer int´erprete). Turing muestra el problema de la parada. Turing lo aplica al Entscheidungsproblem.
ENTSCHEIDUNGSPROBLEM Problema de decisi´on de los teoremas de la l´ ogica de primer orden Planteado por David Hilbert en 1928
Luis Sierra (InCo)
M´ aquinas
EECC 2012
17 / 22
Diferencias en los art´ıculos de Post y Turing
treinta carillas Turing construye la m´aquina universal (el primer int´erprete). Turing muestra el problema de la parada. Turing lo aplica al Entscheidungsproblem.
ENTSCHEIDUNGSPROBLEM Problema de decisi´on de los teoremas de la l´ ogica de primer orden Planteado por David Hilbert en 1928 Resuelto por Alonzo Church en 1936
Luis Sierra (InCo)
M´ aquinas
EECC 2012
17 / 22
Diferencias en los art´ıculos de Post y Turing
treinta carillas Turing construye la m´aquina universal (el primer int´erprete). Turing muestra el problema de la parada. Turing lo aplica al Entscheidungsproblem.
ENTSCHEIDUNGSPROBLEM Problema de decisi´on de los teoremas de la l´ ogica de primer orden Planteado por David Hilbert en 1928 Resuelto por Alonzo Church en 1936 Y por Alan Turing en 1936
Luis Sierra (InCo)
M´ aquinas
EECC 2012
17 / 22
Otras tres diferencias
La m´aquina de Post modela a un trabajador que sigue instrucciones; la m´aquina de Turing hace consideraciones acerca de la memoria humana
Luis Sierra (InCo)
M´ aquinas
EECC 2012
18 / 22
Otras tres diferencias
La m´aquina de Post modela a un trabajador que sigue instrucciones; la m´aquina de Turing hace consideraciones acerca de la memoria humana La m´aquina de Post es determinista; Turing se concentra en las m´aquinas autom´aticas, pero tambi´en presenta las choice machines en las que el no determinismo es resuelto por un external operator.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
18 / 22
Otras tres diferencias
La m´aquina de Post modela a un trabajador que sigue instrucciones; la m´aquina de Turing hace consideraciones acerca de la memoria humana La m´aquina de Post es determinista; Turing se concentra en las m´aquinas autom´aticas, pero tambi´en presenta las choice machines en las que el no determinismo es resuelto por un external operator. La m´aquina de Turing que mostr´e ...
Luis Sierra (InCo)
M´ aquinas
EECC 2012
18 / 22
Otras tres diferencias
La m´aquina de Post modela a un trabajador que sigue instrucciones; la m´aquina de Turing hace consideraciones acerca de la memoria humana La m´aquina de Post es determinista; Turing se concentra en las m´aquinas autom´aticas, pero tambi´en presenta las choice machines en las que el no determinismo es resuelto por un external operator. La m´aquina de Turing que mostr´e ... ... tampoco es la del art´ıculo
Luis Sierra (InCo)
M´ aquinas
EECC 2012
18 / 22
Tesis de Church La noci´on de calculabilidad efectiva Definimos ahora la ya discutida noci´ on de una funci´ on efectivamente calculable de los naturales identific´andola con la noci´ on de funci´on recursiva sobre los naturales. (o sobre las funciones λ-definibles sobre naturales). Pensamos que esta definici´ on queda justificada por las siguientes consideraciones ...
Luis Sierra (InCo)
M´ aquinas
EECC 2012
19 / 22
Tesis de Church La noci´on de calculabilidad efectiva Definimos ahora la ya discutida noci´ on de una funci´ on efectivamente calculable de los naturales identific´andola con la noci´ on de funci´on recursiva sobre los naturales. (o sobre las funciones λ-definibles sobre naturales). Pensamos que esta definici´ on queda justificada por las siguientes consideraciones ...
Algunos modelos Emil Post, y su m´aquina
Luis Sierra (InCo)
M´ aquinas
EECC 2012
19 / 22
Tesis de Church La noci´on de calculabilidad efectiva Definimos ahora la ya discutida noci´ on de una funci´ on efectivamente calculable de los naturales identific´andola con la noci´ on de funci´on recursiva sobre los naturales. (o sobre las funciones λ-definibles sobre naturales). Pensamos que esta definici´ on queda justificada por las siguientes consideraciones ...
Algunos modelos Emil Post, y su m´aquina Alan Turing, y su m´aquina
Luis Sierra (InCo)
M´ aquinas
EECC 2012
19 / 22
Tesis de Church La noci´on de calculabilidad efectiva Definimos ahora la ya discutida noci´ on de una funci´ on efectivamente calculable de los naturales identific´andola con la noci´ on de funci´on recursiva sobre los naturales. (o sobre las funciones λ-definibles sobre naturales). Pensamos que esta definici´ on queda justificada por las siguientes consideraciones ...
Algunos modelos Emil Post, y su m´aquina Alan Turing, y su m´aquina Alonzo Church, y su λ-c´alculo
Luis Sierra (InCo)
M´ aquinas
EECC 2012
19 / 22
Tesis de Church La noci´on de calculabilidad efectiva Definimos ahora la ya discutida noci´ on de una funci´ on efectivamente calculable de los naturales identific´andola con la noci´ on de funci´on recursiva sobre los naturales. (o sobre las funciones λ-definibles sobre naturales). Pensamos que esta definici´ on queda justificada por las siguientes consideraciones ...
Algunos modelos Emil Post, y su m´aquina Alan Turing, y su m´aquina Alonzo Church, y su λ-c´alculo Stephen Kleene, y las funciones generales recursivas de Herbrand y G¨odel Luis Sierra (InCo)
M´ aquinas
EECC 2012
19 / 22
En breve ...
En los treinta, antes de las computadoras modernas, ya sab´ıamos de los l´ımites de la inform´atica.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
20 / 22
En breve ...
En los treinta, antes de las computadoras modernas, ya sab´ıamos de los l´ımites de la inform´atica. En el siglo veintiuno, luego del uso masivo de computadoras, se cree que no hay l´ımites para la inform´atica.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
20 / 22
En breve ...
En los treinta, antes de las computadoras modernas, ya sab´ıamos de los l´ımites de la inform´atica. En el siglo veintiuno, luego del uso masivo de computadoras, se cree que no hay l´ımites para la inform´atica. Hace algunos a˜ nos me preguntaba si era pertinente introducir los temas de computabilidad en la ense˜ nanza media y primaria.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
20 / 22
En breve ...
En los treinta, antes de las computadoras modernas, ya sab´ıamos de los l´ımites de la inform´atica. En el siglo veintiuno, luego del uso masivo de computadoras, se cree que no hay l´ımites para la inform´atica. Hace algunos a˜ nos me preguntaba si era pertinente introducir los temas de computabilidad en la ense˜ nanza media y primaria. Hoy me pregunto c´omo habr´ıa que hacerlo, o al menos, c´omo convencer a la gente que los l´ımites de la inform´atica van m´as all´a de los costos y el procesador que se tenga.
Luis Sierra (InCo)
M´ aquinas
EECC 2012
20 / 22
Herramientas
HTML http://www.w3.org/TR/html4/ CSS http://www.w3.org/TR/CSS2/ JavaScript https://developer.mozilla.org/en/JavaScript/ SVG http://www.w3.org/TR/SVG/ Rapha¨el Rapha¨el-JavaScript Library http://raphaeljs.com/
Luis Sierra (InCo)
M´ aquinas
EECC 2012
21 / 22
Bibliograf´ıa
Finite Combinatory Processes - Formulation 1, Emil L. Post, The Journal of Symbolic Logic, Vol. 1, No. 3, pp. 103-105 (Sep., 1936) On Computable Numbers, with an application to the Entscheidungsproblem, Alan Turing, Proceedings of the London Mathematical Society (2) 42 pp 230-265 (1936-37) An Unsolvable Problem of Elementary Number Theory, Alonzo Church, The American Journal of Mathematics 58 pp 345-363 (1936) The undecidable, Martin Davis (Ed.), Dover, 2004 Introduction to Computability, Fred Hennie, Addison-Wesley Longman Publishing Co., 1977
Luis Sierra (InCo)
M´ aquinas
EECC 2012
22 / 22
