Blog

Alonzo Church

Alonzo Church

Alonzo Church (14 de junio de 1903 – 11 de agosto de 1995), matemático y lógico estadounidense creador de la base de la computación teórica. Nacido en la ciudad de Washington, se diplomó en 1924 y obtuvo su doctorado en 1927 en la Universidad de Princeton, donde ejerció como profesor entre 1929 y 1967.

Read More

Autómata con pila

Autómata con pila

Un autómata con pilaautómata a pila o autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky.

Función computable

Las funciones computables son una formalización de la noción intuitiva de algoritmo y según la Tesis de Church-Turing son exactamente las funciones que pueden ser calculadas con una máquina de cálculo. La noción de la computabilidad de una función puede ser relativizada a un conjunto arbitrario de números naturales A, o equivalentemente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas con un oráculo por A o f. Tales funciones pueden ser llamadas A-computable o f-computable respectivamente. Antes de la definición precisa de una función computable los matemáticos usaban el término informal efectivamente computable.

Read More

Cracking

Tesis de Church-Turing

En teoría de la computabilidad, la tesis de Church-Turing formula hipotéticamente la equivalencia entre los conceptos de función computable y máquina de Turing, que expresado en lenguaje corriente vendría a ser “todo algoritmo es equivalente a una máquina de Turing“. No es un teorema matemático, es una afirmación formalmente indemostrable que, no obstante, tiene una aceptación prácticamente universal.

Read More