Problema de clasificación algorítmica

Abstract

In 1910 Bertrand Russell and Alfred North Whitehead published the books Principia Mathematica, where an axiomatization of set theory is exposed, with the thesis that it derives all true mathematics. In 1931 Kurt Gödel proved an unavoidable limitation on formal theories that included that set forth in Principia Mathematica. On the other hand, in 1930, Alonzo Church introduced the Lambda Calculus and in relativimente simple and equivalents, that formalize to the notion of algorithm. Around 1936 both independently demonstrated a stronger limitation for the algorithms. His theorem shows a problematic that appears on any classification of the algorithms. Limitations in computability and limitations in formal theories have a very similar nature, and this is perhaps not very surprising given that Turing inspired the Gödel test to prove the first limitation, in 1936.

En 1910 Bertrand Russell y Alfred North Whitehead publicaron los libros Principia Mathematica, donde se expone una axiomatización de la teoría de conjuntos, con la tesis de que ésta se derivan todas las verdaderas matemáticas. En 1931 Kurt Gödel probó una limitación inevitable en las teorías formales que incluían a aquella expuesta en Principia Mathematica. Por otro lado, en 1930, Alonzo Church introdujo el Cálculo Lambda y en relativimente simples y equivalentes, que formalizan a la noción de algoritmo. Alrededor de 1936 ambos demostraron, de manera independiente, una limitación más fuerte para los algoritmos. Su teorema muestra una problemática que se aparece sobre cualquier clasificación de los algoritmos. Las limitaciones en computabilidad y las limitaciones en las teorías formales tienen una naturaleza muy parecida, y esto quizá no es muy sorprendente dado que Turing inspiro en la prueba de Gödel para probar la primera limitación, en 1936.