Tesis de Church

La tesis Church-Turing y sus malinterpretaciones
Tesis de Turing:
Cada vez que haya un método efectivo para obtener valores de una función, la función podrá ser
computada por una máquina de Turing.
La conversa:
Todo lo que una máquina de Turing computa es efectivamente computable.
Tesis de Church : Una función de enteros positivos es efectivamente calculable solo si es recursiva.
Laconversa:
Toda función recursiva de enteros positivos es efectivamente calculable.
Errores a la hora de interpretar la Tesis Church- Turing en la filosofía de la
mente:
*Creer que las máquinas de Turing pueden
- resolver cualquier problema que pueda ser resuelto por “instrucciones, reglas explícitamente
dadas, o procedimientos”, (The Oxford Companion to the Mind ( Gregory 1987: 784))-“computar cualquier función que cualquier computador, con cualquier arquitectura, pueda
computar.”( Dennett 1991: 215)
*Creer que “los resultados de Turing implican que un computador, dado el programa correcto,
suficiente memoria y suficiente tiempo, puede computar cualquier regla regida por una función
input-output. Esto es, puede mostrar cualquier patrón sistemático de respuesta a cualquierambiente” (Paul y Patricia Churchland 1990: 26)*Referir como una versión de la Tesis de Turing a aquella que plantea que una máquina de Turingpuede computar cualquier cosa que pueda ser computada por una máquina que trabaje con datos
finitos de acuerdo a un programa finito de instrucciones:
“Los modelos conexionistas… posiblemente desafían la tesis de Church que dice que
computaciones bien definidas sonsatisfechas por máquinas de Turing”. (Smolensky1988:3.)
*“Existe una formulación más general de la máquina que conecta un único conjunto de
funciones input-output, ésta puede ser llamada Tesis de Church”. ( Newell 1980: 150.)
*“El trabajo de Church y Turing fundamentalmente conecta computadoras con máquinas de
Turing. Los límites de las máquinas de Turing de acuerdo con la tesis Turing-Church,describe los
límites teóricos de todos los computadoras”. (McArthur 1991: 401.)
*“Es difícil ver cómo cualquier lenguaje que pueda ser actualmente procesados en un computador
físico pude hacer más de que lo que Fortran puede. La idea de que no existe tal lenguaje es
llamada la tesis de Church.” (Geroch y Hartle 1986: 539)

*“versión física” de la tesis de Turing-Church :
“cada sistemafísico, finitamente realizable puede ser simulado por una máquina de
cómputo de modelo universal operando con medios finitos” (Deutsch 1985: 99.)

Pero una tesis concerniente a la extensión de los métodos efectivo (Tesis de Turing) no implica que
concierna a la extensión de los procedimientos que las máquinas son capaces de hacer, incluso
máquinas actuando de acuerdo con “reglasexplícitamente dadas”.
Estas posturas en realidad están afirmando una tesis que llamaré M.
Tesis M:Cualquier cosa que pueda ser calculada por una máquina (que trabaje con datos finitos de acuerdo
con un programa finito de instrucciones) es Turing-computable.
Esta tesis admite 2 interpretaciones de acuerdo a si la frase “puede ser calculada por una
máquina” es tomada:
-En sentido amplio que abstrae lacuestión de si la máquina nocional pudiera existir o no en el
mundo actual. Bajo esta interpretación la tesis M es falsa.
-En el sentido estrecho de “puede ser calculada por una máquina que se atenga a las leyes de la
física (si no a las limitaciones materiales) del mundo actual.
Que la versión estrecha de la tesis M sea verdadera o no es una cuestión empírica abierta. Se
especula que puedahaber procesos físicos – y de este modo, potencialmente, operaciones
maquinales- cuyo comportamientos se atengan a funciones no computables por la máquina de
Turing.
¿Puede una máquina ejecutar un procedimiento que no sea mecánico? Puede parecer
autocontestable. Sin embargo esto es lo que se pregunta cuando se cuestiona la tesis M.
Otro tipo de errores de interpretación de la tesis...