Tesis de Church para la máquina de Turing

En 1936, Alonzo Church creó un método denominado cálculo lambda en el que los números de Iglesia están bien definidos, es decir, la codificación de números naturales. También en 1936, Alan Turing creó las máquinas de Turing (anteriormente llamadas modelo teórico para máquinas), que se utilizan para manipular los símbolos de cuerdas con la ayuda de una cinta.

Tesis de Church Turing: La
máquina de Turing se define como una representación abstracta de un dispositivo informático, como el hardware de las computadoras. Alan Turing propuso las Máquinas de Computación Lógica (LCM), es decir, las expresiones de Turing para las Máquinas de Turing. Esto se hizo para definir los algoritmos correctamente. Entonces, Church creó un método mecánico llamado ‘M’ para la manipulación de strings mediante el uso de la lógica y las matemáticas.

Este método M debe pasar las siguientes sentencias:

• El número de instrucciones en M debe ser finito.
• La salida debe producirse después de realizar un número finito de pasos.
• No debe ser imaginario, es decir, se puede realizar en la vida real.
• No debería requerir ninguna comprensión compleja.

Usando estas declaraciones, Church propuso una hipótesis llamada tesis de Turing de Church que se puede enunciar como: «La suposición de que la noción intuitiva de funciones computables puede identificarse con funciones recursivas parciales».

En 1930, esta declaración fue formulada por primera vez por Alonzo Church y generalmente se la conoce como la tesis de Church o la tesis de Church-Turing. Sin embargo, esta hipótesis no puede ser probada.

Las funciones recursivas pueden ser computables después de tomar las siguientes suposiciones:

1. Todas y cada una de las funciones deben ser computables.
2. Sea ‘F’ la función computable y después de realizar algunas operaciones elementales a ‘F’, se transformará en una nueva función ‘G’, entonces esta función ‘G’ se convierte automáticamente en la función computable.
3. Si alguna función que sigue las dos suposiciones anteriores debe declararse como función computable.