Surgimiento de la teoría de la computación

Surgimiento de la teoría de la computación

NOMBRE DEL ALUMNO: MEJIA RUIZ ANGEL EDUARDO

NOMBRE DEL PREOFESOR: GUTIERREZ GIRALDI OFELIA

NOMBRE DE LA MATERIA: LENGUAJES Y ATÓMATAS I

[pic 1]

INTRODUCCION

El nacimiento de la lógica propiamente dicho está directamente relacionado con el nacimiento intelectual del ser humano. La lógica emerge como mecanismo espontáneo en el enfrentamiento del hombre con la naturaleza, para comprenderla y aprovecharla. Poncairé destaca cinco etapas o revoluciones en ese proceso que se presentan entre dos grandes tópicos: del rigor y la formalidad, a la creatividad y el caos. Las etapas se identifican como: Revolución Matemática, Revolución Científica, Revolución Formal y Revolución Digital además de la próxima y prevista Revolución Lógica.

La teoría de la computación comienza propiamente a principios del siglo XX, poco antes que las computadoras electrónicas fuesen inventadas. En una época donde los matemáticos se preguntaban si había una forma única que resolviera todos los problemas matemáticos existentes.

Algunos de estos modelos formales fueron propuestos por precursores como Alonzo Church (cálculo Lambda), Kurt Gödel (funciones recursivas) y Alan Turing (máquina de Turing). Se ha mostrado que estos modelos son iguales en el sentido de que pueden simular los mismos algoritmos, aunque lo hagan de maneras diferentes

Alonzo Church(cálculo Lambda)

En las primeras décadas de este siglo seguramente se consideraba imprescindible para un lógico que se presentara un sistema lógico propio. Church creó el cálculo lambda tomando como base el concepto de función y distinguiendo claramente entre el valor de una función para un argumento, F(x) y la propia función λxF(x).

El elegir este concepto como base fue un gran acierto por su parte, pero el distinguir en el lenguaje los valores de la función misma lo fue aún mayor. Si a esto añadimos la característica de que una función anide otra, el lenguaje está preparado para expresar la recursión. De hecho, a diferencia de los sistemas axiomáticos fundacionales, la existencia de 2 modelos matemáticos ( en este caso son funciones) no se postula, sino que son generados por las propias reglas de formación de expresiones. Este lenguaje es tan compacto y tan adecuado para expresar funcionalidad que se convirtió en lenguaje de programación. Se le contribuye la inspiración para crear el lenguaje LISP, desarrollado por John Mc Carthy al cálculo lambda. El cálculo lambda, aun que llevaba varios años circulando, no aparece en la prensa hasta principios de los cuarenta. A comienzo de los treinta Church ya sabía que tanto la función del siguiente como la suma eran λ-definibles, pero fue su alumno Kleene quien fue gradualmente lo amplia que era la clase de funciones definibles mediante lambda y estos resultados constituyeron parte de su tesis. Este es el origen de la teoría de la recursión. Sin embargo los resultados de esta investigación los llevaron más lejos de lo esperado.

...