PUBLICACIONES

Sociedad Colombiana de Matemáticas:Publicaciones
Lecturas Matemáticas
Volumen 27 [Especial] (2006)Páginas 161--174
Artículos Matemáticos

Sobre dos teoremas de incompletez de Chaitin

Carlos Mario Parra,Johany A. Suárez
Universidad Nacional de Colombia, Medellín, Colombia

Resumen. Impulsadas por el Programa de Hilbert y la necesidad de clarificar los métodos del razonamiento matemático, las investigaciones sobre los fundamentos de la matemática condujeron al descubrimiento del fenómeno de incompletez. Mediante la noción de complejidad algorítmica de un objeto, es posible obtener una nueva gama de resultados que exhiben la generalidad y relevancia de dicho fenómeno. En este artículo bosquejamos las nociones básicas de aleatoriedad e información y proponemos otra definición de la complejidad de un sistema formal, lo cual nos permite ofrecer pruebas alternativas de dos resultados clásicos de incompletez, debidos a G. Chaitin.

Abstract. Inspired by the so called Hilbert Program and the necessity to clarify the methods of mathematical reasoning , the research on the foundations of mathematics led to the discovery of the Incompleteness phenomenon. Using the notion of algorithmic complexity of an object it is possible to obtain a new array of results that exhibit the ubiquity and relevance of such a phenomenon. In this paper we sketch the basic notions of Information and Randomness and propose another definition of the complexity of a formal system, which allows us to give alternative proofs of two classical incompleteness theorems by G. Chaitin.

* Publicacion del número especial con el apoyo de Colciencias para el XV Congreso Nacional de Matemáticas


Palabras claves. Algorithmic Complexity, Incompleteness, Chaitin computer

Codigo AMS. Primary: 68Q30. Secondary: 03D10

Archivo completo : Formato [PDF] (355 K).