Yuri Gurevich y Nachum Dershowitz, de Microsoft Research, publicaron hace unos días un paper demostrando la Tesis de Church-Turing (primero haciendo una axiomatización que le permita luego realizar la demostración formal). El paper se puede encontrar aquí y parece ser muy interesante.
Por otra parte, este post en el blog de Scott Aaronson es realmente divertido. El mismo hace referencia a la devolución que el Foundations of Computer Science (FOCS) le dio a Alan Turing en respuesta a su paper “On computable numbers …“, ahora absolutamente clásico (70 años después se lo sigue estudiando, y sigue siendo la base de muchas investigaciones).
julio 19, 2007 at 12:51 pm
the author proves a lemma stating that there exists a “universal machine” (a machine able to simulate any other machine given a suitable choice of input). the claim that this lemma could have “practical” applications is clearly exaggerated
¡¡genial!!