domingo, 6 de enero de 2008

Saber cuándo parar

Muchas veces nos encontramos con situaciones en las que se produce aquello del “efecto bola de nieve[1]. Situaciones en las que parece que no hay un final, cada nuevo elemento que aparece, cada nuevo factor, modifica las variables nuevamente y su fin se presume cada vez más complicado. No sabemos cuándo y cómo finalizará el problema, y tenemos que tomar la decisión de pararlo. Pero la cuestión es: ¿cuándo intervenir? En Teoría de la Computación se estudia este problema desde los años 30, al que se denomina “el problema de la parada” o “el problema de la detención”, y es considerado como el problema irresoluble más conocido.


Alan Turing, (1912-1954) matemático, criptógrafo, filósofo, precursor y pionero
de la Inteligencia Artificial, concibió, con lápiz y papel, la máquina computadora moderna hacia 1935. Todos los ordenadores actuales son en el fondo “máquinas de Turing”. Resumidamente una "máquina de Turing" es una “máquina” idealizada matemáticamente. La importancia de este dispositivo imaginario es que es capaz de resolver cualquier problema matemático si éste ha sido especificado como algoritmo. Turing pretendía resolver el “Entscheidungsproblem de David Hilbert, esto es, “encontrar un algoritmo que determine la verdad o falsedad de cualquier proposición en el sistema formal”, demostrar en definitiva que cualquier problema bien definido se puede resolver ejecutando un algoritmo determinado.


A través de su “máquina” Turing demostró que existen problemas que un ordenador no puede
resolver, existen funciones que no son posibles calcular mediante la “máquina de Turing”, ya que no admiten una solución algorítmica. El más conocido de ellos es el problema de la parada”, que consiste en determinar si una “máquina de Turing” cualquiera se parará en un tiempo determinado sobre una entrada determinada. Podemos decir que no existe ningún método que permita predecir en todos los casos, una vez que un computador ha comenzado un cálculo, si dicho cálculo terminará alguna vez. En algunos casos, lo más que puede hacer es ejecutar el programa y esperar (¿eternamente?). Este problema y sus conclusiones son fundamentales en el tratamiento de los “bucles infinitos”.




Steam-powered Turing Machine Mural, group of CSE students, 1987

Para intentar resolver este problema Turing imaginó una máquina equipada con una “caja negra, un “oráculo”, que sería un mecanismo que llevaría a cabo las tareas “no computables”. El oráculo consistiría en un dispositivo medidor perfecto más una memoria que contiene un valor (llamémoslo T, en honor a Turing) de cierta magnitud física. T es un número irracional, y su propiedad sería que en sus dígitos representaría lo programas que terminan y los que no. Hoy día no existe ninguna forma practicable de materializar un oráculo. De ser encontrada, el impacto sobre las ciencias de cómputo sería enorme. Pero mientras tanto, sólo nosotros podemos ver si un bucle es infinito y saber cuándo parar el proceso. Al fin y al cabo, son este tipo de cosas las que siempre nos han diferenciado de las máquinas, pues nosotros, a diferencia de las máquinas, tomamos decisiones a partir de emociones [2].


Notas:

[1] Entiéndase también como "márketing viral"
[2] Antrópicos: 'emoción y razón'



12 comentarios:

orejonkz dijo...

Cuando se presenta un problema de este tipo y tenemos la disyuntiva de decidir donde esta la línea divide lo "permitido" y lo "no permitido", o "el bien" y "el mal", las maquinas no tienen a día de hoy criterio para hacerlo.
El problema aparece porque cada uno pondríamos esa línea más adelante o más atras, antes o después.

Lo importante es tener la capacidad de darse cuenta que algunas bolas hay que pararlas y cuanto antes mejor, asi que dalé una patada a la que te moleste y deshazte de ella.

Un saludo.

D.I.E.G.O. dijo...

Douglas Hofstadter, escribió un libro dificil para mi (a fuerza de ser sincero algunas cosas me pasaron por encima sin siquiera despeinarme) se llama Escher, Gödel,Bach un Eterno y Gracil Bucle.
Escribe y te ilustra del tema (no se si lo leiste, te lo recomiendo).
lo editó Tusquets coleccion Metatemas 14 la tradución fue supervisada por el autor, vale lo que pesa) 882 pags.

D.I.E.G.O. dijo...

saludos, perdón

Ulysses dijo...

Hola:
Hay varios temas planteados en este post.
Pero creo que la pregunta es: ¿Puede existir la inteligencia artificial?
La respuesta propuesta es:
Las máquinas piensan algorítmicamente
Los humanos algorítmicamente y heurísticamente (1)
Pero si pudieramos incluir emociones en el programa. ¿Que sucedería? (No sé si se pueda)

(1) En algunas ciencias, manera de buscar la solución de un problema mediante métodos no rigurosos, como por tanteo, reglas empíricas, etc.

Pd. Estoy de acuerdo con D.i.e.g.o. ese libro es excelente

Saludos

Tawaki dijo...

Muy interesante. Yo creo que todo es posible, que sólo hace falta que transcurra el tiempo necesario.

Un saludo.

fernando dijo...

las maquinas nunca serán como los humanos para bien o para mal ;)

un abrazo.

Payne dijo...

Estimado Miguel Ángel:

Soy de letras.

Generalmente, con esta declaración suele uno dar por concluido cualquier problema tipo Turing. Sin embargo siendo de letras, pueden encontrarse algunas aproximaciones.

1.-El editor de este blog tiene entre sus libros favoritos un buen puñado a los que sus autores no han tenido más remedio que poner fin ¿No son en realidad libros con vocación de infinitud? El hombre se rebela con mucha frecuencia contra la necesidad de detenerse. Lamentablemente y por lo general la rebeldía degenera en patología, pero en la literatura, es fácil rastrar esa ansia por lo interminable. (Borges)

2.-¿Qué valor tiene -lo pregunto literalmente- la "solución de problemas a través de emociones"? Es precisamente esa variable la que hace que la "parada" o mejor la "decisión" en la "bifurcación" sea errónea tantas veces.

3.-Las emociones dan lugar a las llamadas autoprofecías: La profecía que se autorrealiza es, al principio, una definición "falsa" de la situación que despierta un nuevo comportamiento que hace que la falsa concepción original de la situación se vuelva "verdadera". (wikipedia)

4.-Conocí al dueño de un burdel de carretra que antes de la crisis de los ochenta gastó un buen dinero en iluminar la fachada de su casa de citas. Era una cosa espectacular -además de muy kitch-. El asunto es que, en cuanto se anunció que iban a llegar las vacas flacas, el tipo pensó que tendría menos clientes y que había que ahorrar, así que aflojó algunas bombillas; la iluminación fue siendo menos vistosa, entraba menos público. S
Siguió reduciendo la iluminación y la espiral continuó hasta que el local ya no era visible desde la carretera y nadie se detenía a solazarse. Una tarde, minetras nos tomábamos un Dyc en vaso de tubo, me dijo: -Si estaba claro: la crisis se veía venir.

Me temo que no quiero emociones en el cálculo, ni rumores; no quiero miedo, ni euforia. Si hay que seguir haciendo operaciones, opérese. Pero déjense los sentimientos para otras causas que resistan mejor sus nunca bien recordados y temibles efectos. El manejo de los sentimientos se realiza con tal ferocidad por aquéllos que los dominan que es preferible apellidarse HAL o IBM.
¿Conoce usted esta película?

http://zeitgeistmovie.com/

está disponible en español y puede verse en el acto.(son casi dos horas, pero creo que a usted no le va a aburrir.) Cada cual es muy libre; hay partes que incluso resultan casi conspiranóicas, pero ¿Alguien se acuerda de los ataques con antrax metido en sobrecitos y enviados a agunas oficinas de NY? Sentimientos, emociones; el problema de la parada. Otros paran por nosotros.

Extensa y atentamente

P.d. Ya me dirá si me he salido del tiesto por completo o la solución al problema no es, como creo, un problema mayor.

Myriam dijo...

Madre mia!!! Estoy una temporada desconectada y cuando vuelvo has escrito casi la Biblia en verso!!!

Ante todo Feliz Año 2008. Y muchas gracias por acordarte de mí.

Me resulta muy curioso esto de los programas informáticos, aunque debo reconocer que a veces escapa un poco a mi comprensión pues mis conocimientos no llegan tan lejos, pero aprender siempre es bueno.
Algo teniamos que tener los humanos que nos diferenciara de las máquinas... si es que por mucho que se pongan yo creo que faltan miles de años para que consigan una máquina que tenga una "inteligencia" similar a la nuestra.
Prometo ir leyendo todas las entradas que has hecho durante este tiempo, que seguro que son muy interesantes, aunque ya he visto que para la de Carl Sagan necesito tiempo.... jajaja.
Un saludo

i75mara dijo...

Qué lujo tener comentaristas tan sabios!

Orejonkz: Tienes mucha razón. No hay que comportarse como máquinas. Y aún así, a veces caemos en alguna situación que nos arrastra a tal extremo que muchos llegamos a perder lo papeles. Tenemos que andar con pies de plomo cuando expresamos opiniones públicamente, pues nunca están exentas de provocar equívocos. Y por supuesto no excederse con el ego. Saludos

Diego: Has dado con una de las claves de esta historia: el Teorema de Gödel. No conocía el libro que me recomiendas, y el título ya lo dice todo. Apuntado queda. Saludos

Hola Ulysses. Hay algo en lo que difiero contigo, y es que comentas que las máquinas no usan heurísticas. Verás, una de las técnicas de solución de los problemas relativos a la IA es el uso de heurísticas, que intentan capturar el conocimiento (normalmente incompleto e impreciso) del dominio. De hecho, una de las etapas más fructíferas de la IA fue el empleo de medios heurísticos (entre 1956-196x) para resolver problemas de entornos formales, micromundos, que eran idealizaciones del mundo real: demostración de teoremas, estrategias heurísticas en juegos, etc. Hoy día la IA camina por otras vías, pero todavía se usan estos métodos. Digamos que siguen siendo útiles en la búsqueda de soluciones. Saludos

Tawaki: Hola. Yo no sé qué pensar. Lo único que sé es que a nuevas opciones, nuevos retos, y por qué no decirlo, nuevos problemas a resolver. Siempre podremos recurrir a las leyes de Asimov sobre la robótica. Saludos

Fernando: En eso tienes muchísima razón. Creo que siempre serán distintas, aunque puedan hacer las mismas cosas. Pienso, como afirman algunos expertos, que todo conocer depende de la estructura que conoce. Saludos

Payne: Veo que ha vuelto a tratarme de “usted”. No creo que tenga que ver con la seriedad (que no existe, por lo menos no lo pretendo) de lo que se cuenta.

Vayamos por partes. En lo de la vocación de infinitud de los autores de libros de divulgación tiene muchísima razón. Yo, más que infinitud, diría trascendencia, pues no sólo se habla de lo temporal o espacial. Stephen Hawking, en su “Historia del Tiempo”, nos decía “Si se encontrase una teoría que fuese matemáticamente consistente e hiciese predicciones que estuviesen de acuerdo con las observaciones, llegaríamos al momento cumbre de la lucha intelectual por comprender el Universo ... Aunque sólo sería el primer paso hacia la comprensión de lo que sucede a nuestro alrededor y de nuestra propia existencia”. Nunca dejaremos de buscar. Esa es nuestra naturaleza.

Este pdf: www.it.uc3m.es/jvillena/irc/practicas/estudios/Emocion.pdf, explica brevemente algunos conceptos sobre la importancia dentro del campo de la IA del estudio de la emoción como herramienta fundamental para que una máquina pueda desarrollar inteligencia. ¿Para qué serviría? Bueno, hay muchos libros y películas que nos hablan de ello. Recordemos la espléndida “Blade Runner”. Y no me dirá que no es hermoso ese final del "replicante" diciendo aquello de: “Yo... he visto cosas que vosotros no creeríais... atacar naves en llamas más allá de Orión, he visto rayos C brillar en la oscuridad cerca de la puerta Tannhäuser.

Todos esos momentos se perderán en el tiempo como lágrimas en la lluvia.

Es hora de morir”.
¿Podrían acabar las máquinas siendo más humanos que los humanos? Después de ejemplares como Hitler, estoy seguro que cualquier máquina es capaz de desarrollar más empatía.

Y el problema de la parada sigue estando ahí, sin solución. Y su solución sería trascendental. Le voy a transcribir un comentario que ha provocado la publicación de este ‘post’:

“Un problema relacionado matemáticamente es el de la compresión de datos.
En principio un número irracional necesita un número infinito de cifras para ser representado. Pensemos en un número como pi: 3.1415926535....
Pero existen algoritmos finitos (en definitiva, programas informáticos) que son capaces de calcular pi con cualquier precisión decidida de antemano. En ese sentido podemos decir que el número pi es "comprimible" (o "compresible", como gusten).
Sin embargo, hay números que podemos definir, pero que no podemos calcular de manera eficiente, y se puede demostrar que no se pueden calcular usando el problema de la parada”.

Todavía es necesaria la presencia de algo o alguien que detenga a una máquina si el proceso se convierte en una serie de bucles infinitos. Saludos

Myriam: qué bien tenerte por aquí otra vez. A lo que dices te respondería: “hoy las ciencias avanzan que es una barbaridad”. Y quien mejor que tú para decirlo. En IA existen dos campos de estudio diferenciados, por un lado la IA “conexionista”, donde se suele considerar que los seres vivos y las máquinas pueden ser comprendidos usando los mismo principios organizadores y las mismas herramientas, autoprogramable por aprendizaje, y luego está la IA “simbólica”, donde es necesaria una programación y en la que no hay aprendizaje. Digamos que en la primer pretendemos imitarnos, mientras que en la otra pretendemos representar el conocimiento por otras vías... Y no te pierdas el artículo de Carl Sagan, es de esos que producen más preguntas que respuestas después de leerlo. Como debe ser. Saludos.

i75mara dijo...

Ah! Se me olvidaba decir que a quien le interese el tema, existe un fantástico libro de Roger Penrose sobre esto: "La nueva mente del emperador". En esta extensa obra, Penrose pretende demostrar que el conocimiento humano no es computable.

Susana dijo...

Y ahora es cuando llego yo y digo: "EIN?" Lo siento, mi mente ha implosionado intentando entenderlo y he descubierto que yo sí tengo capacidad para parar, pero me ha costado, he llegado al borde del mareo infinito en el que me he tenido que coger la cabeza con las dos manos para poder pararla y que dejara de girar... y girar... y girar...
Reconozco que yo sí conozco el libro que dice diego, pero por Escher y Bach, reconozco también no haberlo leído.
En cuanto a la inteligencia artificial, creo que ese ha sido siempre un gran reto para el hombre, ya en la Odisea Homero describía a dos "androides" y bueno, como no, tenemos el fantástico libro Neuromante de William Gibson, que si no habla de inteligencia artificial si nos plantea la posibilidad de su existencia, amen de un mundo bastante insólito dentro de un ciberespacio bastante extraño...
No sé porque me he acordado ahora de eso....
Feliz año a tí también y sí, ya he vuelto de mis vacances y prometo publicar algo en algún momento.

Rodi dijo...

Como siempre, tus posts son todo un descubrimiento, esa idea de la diferencia entre hombre y máquina de no saber cuando detenerse en un caso determinado me resulta muy interesante. Aunque cuantas veces me habré arrepentido de no saber parar a tiempo en algunas situaciones...

Saludos.