La teoria de la computabilidad
Páginas: 2 (389 palabras)
Publicado: 28 de mayo de 2010
TEORIA DE LA COMPUTABILIDAD
La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con unamáquina de Turing.
El origen de los modelos abstractos de computación se encuadra en los años '30 (antes de que existieran los ordenadores modernos), para el trabajo de los lógicos Alonzo Church,Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan Turing. Estos trabajos iniciales han tenido una profunda influencia, tanto en el desarrollo teórico como en abundantes aspectos de la práctica de lacomputación; previendo incluso la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes porestructuras formales basados en reglas de producción.
El punto inicial de estos primeros trabajos fueron las cuestiones fundamentales que David Hilbert formuló en 1900, durante el transcurso de uncongreso internacional.
Lo que Hilbert pretendía era crear un sistema matemático formal completo y consistente en el cual, todas las aseveraciones fueran planteadas con precisión. Su intención eraencontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal. Al problema en cuestión se le denominó Entscheidungsproblem. En caso de que Hilbert hubiesecumplido su objetivo, cualquier problema bien definido se resolvería simplemente al ejecutar dicho algoritmo.
Pero fueron otros los que mediante una serie de investigaciones mostraron que esto no eraposible. En contra de esta idea K. Gödel sacó a la luz su conocido Primer Teorema de Incompletitud. Este viene a expresar que todo sistema de primer orden consistente que contenga los teoremas de laaritmética y cuyo conjunto de axiomas sea recursivo no es completo. Gödel construyó una fórmula que es satisfactoria pero que no puede ser probada en el sistema. Como consecuencia, no es posible encontrar...
La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con unamáquina de Turing.
El origen de los modelos abstractos de computación se encuadra en los años '30 (antes de que existieran los ordenadores modernos), para el trabajo de los lógicos Alonzo Church,Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan Turing. Estos trabajos iniciales han tenido una profunda influencia, tanto en el desarrollo teórico como en abundantes aspectos de la práctica de lacomputación; previendo incluso la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes porestructuras formales basados en reglas de producción.
El punto inicial de estos primeros trabajos fueron las cuestiones fundamentales que David Hilbert formuló en 1900, durante el transcurso de uncongreso internacional.
Lo que Hilbert pretendía era crear un sistema matemático formal completo y consistente en el cual, todas las aseveraciones fueran planteadas con precisión. Su intención eraencontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal. Al problema en cuestión se le denominó Entscheidungsproblem. En caso de que Hilbert hubiesecumplido su objetivo, cualquier problema bien definido se resolvería simplemente al ejecutar dicho algoritmo.
Pero fueron otros los que mediante una serie de investigaciones mostraron que esto no eraposible. En contra de esta idea K. Gödel sacó a la luz su conocido Primer Teorema de Incompletitud. Este viene a expresar que todo sistema de primer orden consistente que contenga los teoremas de laaritmética y cuyo conjunto de axiomas sea recursivo no es completo. Gödel construyó una fórmula que es satisfactoria pero que no puede ser probada en el sistema. Como consecuencia, no es posible encontrar...
Leer documento completo
Regístrate para leer el documento completo.