Otros ¿En qué nos basamos para decir que la tesis de Church-Turing es verdadera?

[Everett IV]

¿En qué nos basamos para decir que la tesis de Church-Turing es verdadera? Lo digo porque que sólo las funciones recursivas tengan un algoritmo, no lo veo nada claro. Nadie hace algoritmos pensando que esos algoritmos se puedan representar con las funciones que asignan a un valor su máximo y las otras...que ahora no recuerdo, pero mi intuición no llega hasta ahí.

[pod]

Re: ¿En qué nos basamos para decir que la tesis de Church-Turing es verdadera?

No soy un experto en el tema, ni mucho menos, y si cometo cualquier error agradeceré corrección. Pero por lo que he leído sobre el tema la tesis de Church-Turing viene a significar lo siguiente: el conjunto de funciones que una máquina de Turing (ie, un ordenador) puede calcular es igual al conjunto de funciones que un ser humano puede calcular con papel y lápiz (ignorando cualquier límite de recursos). La implicación es en dos sentidos:

1) Un ordenador (máquina de Turing para ser más exactos) puede calcular cualquier cosa que un humano puede calcular con lápiz y papel. Bastaría con programar los mismos pasos.

2) Una persona con lápiz y papel puede calcular cualquier cosa que una máquina de Turing pueda calcular, aunque necesite mucho más tiempo.

Estas dos cosas pueden parecer de sentido común, el problema es que lo que puede calcular "un ser humano con papel y lápiz" es una definición muy informal. No se pueden hacer demostraciones matemáticas estrictas a partir de algo tan informal. A partir de ahí, lo que se ha intentado es formalizar el concepto de computabilidad de una función.

Históricamente, al parecer la conjetura surgió cuando Church y Turing demostraron que las siguientes definiciones de computabilidad son equivalentes: el concepto de "función general recursiva" (Gödel i Herbrand, 1933), "cálculo lambda" (Church, 1936) y computable por una máquina de Turing (1936). Posteriores definiciones de compatibilidad también resultaron ser equivalentes. Eso les llevó a plantear su hipótesis.

Desde aquél entonces, todos los intentos de expandir el concepto de computabilidad (es decir, encontrar funciones que sean computables por un nuevo método pero no por una máquina de Turing) han fracasado. Es decir, todos los intentos de dar una definición más general de computabilidad ha resultado que abarcaban exactamente el mismo conjunto de funciones que las máquinas de Turing; o que el cálculo lambda; o que las funciones generales recursivas. Por eso, ahora universalmente se considera que la tesis es correcta, por bien que nunca podrá ser demostrada por estar basada en un concepto informal.

Alternativamente, hay quien plantea leer la tesis al revés: utilizarla para definir lo que significa que una función sea computable. Según esta corriente, cualquier función computable es aquella que una máquina de Turing puede calcular. Esto estaría respaldado por lo anterior, todos los trabajos en computabilidad han resultado ser equivalentes a la máquina de Turing.

[Everett IV]

Re: ¿En qué nos basamos para decir que la tesis de Church-Turing es verdadera?

Entonces no se puede demostrar que algún día se fabrique un ordenador que calcule funciones no recursivas. Pero eso tendría repercusiones enormes, para el primer teorema de incompletitud de Gödel por ejemplo, pod. Carlos Ivorra, un profesor de la Universidad de Valencia, afirma en su libro http://www.uv.es/ivorra/Libros/Logica2.pdf que la tesis de Churc es metamatemática, pero a mí no me parece tan obvia como cosas que si son metamatemáticas, que la suma y el producto de números naturales es conmutativo. Si me pudieras dar alguna pista de por qué se acepta metamatemáticamente.

Saludos