Muchas veces nos encontramos con situaciones en las que se produce aquello del “efecto bola de nieve”. 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
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”.
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.
Fuente: http://antropicos.blogspot.com/2008/01/saber-cuando-parar.html
Alan Turing
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”.
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.
Fuente: http://antropicos.blogspot.com/2008/01/saber-cuando-parar.html