La Tesis De Church-Turing

Fue formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX, y a pesar de que existen múltiples formulaciones equivalentes, se utilizara una formulación simple y aceptada como dicha tesis, que se obtiene a partir de las revisiones conjuntas entre Alonzo Church y Alan M. Turing de sus respectivos trabajos:

Puesto que se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, es decir:

• Todo lo que es computable (entendiéndose computable como "Lo que se puede tomar en cuenta o evaluar") es Turing-computable.

Eso implica que las máquinas de Turing realmente capturan la noción de lo que es un algoritmo o un procedimiento efectivo llevado a cabo por un humano o por una máquina.

La tesis

Aunque originalmente la tesis que Alonzo Church formulara dice:

• Una función de enteros positivos es efectivamente calculable sólo si es recursiva.

Versión de la Tesis de Church-Turing más utilizada: Todo algoritmo o procedimiento efectivo es Turing-computable.

Otra versión simplificada de la anterior es:

• Todo lo que es computable es Turing-computable.

Origen de la tesis

Modelos equivalentes a la máquina de Turing MT son: máquinas de Turing con una cinta infinita hacia una dirección, máquinas de Turing con una cinta infinita hacia ambas direcciones, máquinas de Turing con múltiples cintas, máquinas de Turing con múltiples pilas, máquinas de enumeración, entre

...