Re: [escepticos] **Omega por aqui es una marca de vinagre

[Juan Lupión <juan@...>]

At 13:59 30/04/01 +0200, you wrote:
> Dado mis carencias matematicas, mi desconcierto es peor que el tuyo.
> El tema parece interesante, espero que los matematicos y fisicos de la lista
> nos hechen un poco de luz .
> Creo que los expertos en computacion nos pueden explicar razones mas
> corrientes para que un ordenador se "cuelgue" , sin recurrir a nada 
> misterioso.

No se trata de los "cuelgues" a los que nos tiene acostumbrado Windows,
creo que el texto de la noticia de "La Nación" peca de inexacto.
Se trata del conocido Problema de la Parada, en inglés "The Halting problem"

Es sencillo escribir un programa que no termine nunca, cualquier informático
puede hacerlo (y de hecho lo habrá hecho involuntariamente alguna vez).
Sin embargo lo que no es sencillo es, dado un programa cualquiera y unos datos
de entrada para este programa, averiguar si el programa acaba o no (o sea,
se "cuelga"). De hecho es una tarea tan poco sencilla que Turing demostró
que es imposible escribir un programa que sirva como "comprobador de cuelgues"
de otros programas. (Turing usaba como modelo de computador una abstracción
teórica conocida comúnmente como Máquina de Turing)

Hasta aquí lo que la teoría de computación dice. Cómo un matemático ha
logrado extraer un número probabilístico de todo este asunto, lo ignoro.


Para más información, he buscado algunos recursos en Google, en inglés
y de tratamiento más bien árido:

http://www.cs.washington.edu/homes/csk/halt.html

http://www.netaxs.com/people/nerp/automata/halting0.html