La cientificidad de la tesis de Church-Turing

La definición de la tesis de Church-Turing es un intento de capturar la idea intuitiva de computabilidad efectiva o "cosas que realmente se pueden calcular".

Se ha dicho que no es algo para ser probado o refutado, pero las suposiciones importantes que subyacen al trabajo científico en muchos campos de investigación se basan en alguna versión de la tesis, un caso importante es la suposición lingüística de que la semántica de los lenguajes naturales puede ser formalizarse de manera significativa .

Considerando que es infalsable, ¿debería darse a la tesis de Church-Turing un papel tan importante en la investigación científica?

EDITAR:

Gracias por la atención. En respuesta a algunas de las críticas que ha recibido la pregunta, me gustaría agregar que,

  1. En muchos, muchos trabajos de lingüística, psicología, ciencia cognitiva, filosofía y, obviamente, en la mayor parte de lo que es informática aplicada , se da un salto más o menos consciente de pensamiento-significado-comportamiento... a computable a Turing-computable . Es a este último paso al que me refiero en esta pregunta. Esta forma de pensar, aunque no refleja necesariamente nuestra mejor comprensión, aún disfruta de una popularidad significativa dentro de la comunidad científica (y sí, esta es solo mi percepción).
  2. La tesis de Church-Turing, al no ser del todo objetiva, aún puede ser debatida, objetada, incluso desacreditada y eventualmente considerada inútil (que creo que es lo que va a pasar, algún día), pero no estrictamente falsificada .
Nadie cree que se pueda formalizar la semántica de los lenguajes naturales. Incluso Davidson, quien creo que fue el más optimista en este sentido, lo trata como un ideal regulativo por el que debemos luchar en lugar de una suposición. Algo así como tratemos de formalizar tanto como podamos. La "ley" de la causalidad también es infalsable (y probablemente falsa), pero seguir buscando causas donde aún no se ha encontrado ninguna sigue siendo un buen lema para la ciencia. La legalidad o computabilidad efectiva son buenas metas porque tienen una gran utilidad para nosotros, siempre que no se desplomen en ilusiones.
"Nadie cree" es una declaración fuerte, especialmente en esta comunidad. Lo que creo es que esto es algo de lo que vale la pena hablar.
Pero usted lo llama "suposición importante que subyace al trabajo científico en muchos campos", lo cual no es. "Nadie" no es una exageración, véase Filosofía del lenguaje de Miller. Simplemente no se necesita como suposición para hacer lingüística de lenguajes naturales, o incluso para intentar formalizar aspectos de ella.
dicho de otro modo, las personas que asumen que la semántica de los lenguajes naturales se pueden formalizar corren el riesgo de que no se les tome en serio.
No estoy seguro de que haya caracterizado correctamente la TC. Fue Turing, y sólo Turing, quien captó la noción de "procedimiento efectivo" en términos formales. CT, si no me equivoco, dice que otros modelos, como el cálculo lambda, son equivalentes al modelo de Turing. eso es una cosa muy diferente. nunca se ha probado, pero eso no significa que no se pueda probar. sin embargo, todo el mundo cree que es verdad.
"muchos campos de investigación se basan en alguna versión de la tesis". ¿Puedes dar un ejemplo específico? No puedo pensar en uno.
@mobileink si lee la pregunta detenidamente, verá un ejemplo muy fácilmente. Es posible que usted (y otros) no estén de acuerdo en que este es un ejemplo válido, pero está ahí.
Podemos decir que la tesis de Church-Turing es una hipótesis; no podemos probarlo matemáticamente, porque establece la equivalencia entre un concepto "formal" y uno intuitivo. Por supuesto, se puede falsificar (y se han producido algunos intentos). Cómo ? mostrando un "procedimiento computacional" que es intuitivamente "mecánico" pero demostrando (de una manera matemática precisa) que no es, por ejemplo, computable por Turing.
Véase también esta publicación .

Respuestas (2)

Desea tener cuidado cuando usa la palabra ciencia en el contexto de falsabilidad. La falsabilidad es una propiedad de las teorías en las ciencias empíricas, es decir, ciencias que se basan en la observación de fenómenos del mundo real.

En este sentido, la tesis de Church-Turing no es un enunciado científico, es un enunciado de lógica y matemáticas. La lógica y las matemáticas son independientes de la observación y, por lo tanto, estrictamente hablando, no forman parte de la ciencia. 2+2=4 independientemente de si la mecánica newtoniana es correcta o si la relatividad de Einstein es correcta. (ab)²= a² - 2ab + b² sin importar si la tierra es plana o redonda, o hay 25 planetas en el sistema solar o solo 4.

En algunas otras definiciones , las matemáticas y la lógica son ciencias, pero usando el criterio de falsificación de demarcación, no lo son.

En cuanto al hecho de que la tesis de Church-Turing se utilice en diversas ciencias empíricas, guarda con ellas la misma relación que cualquier teorema o conjetura de las matemáticas.

Corre el riesgo de insinuar que la informática no es una ciencia.
La informática teórica no es una ciencia empírica, es definitivamente una rama de las matemáticas. Comenzó como una rama de las matemáticas, cuando Turing se dispuso a resolver uno de los problemas de Hilbert. Pero ahora me has hecho tropezar con una pregunta más interesante...
No creo que eso sea correcto. Un teorema de matemáticas se puede demostrar a partir de los primeros principios. La tesis de CT no es un teorema y no puede demostrarse lógicamente. Es una declaración de una creencia sobre el mundo. No podría haber dos cosas en el mundo más diferentes y dispares que un teorema matemático y la tesis de Church-Turing.
@ user4894 Nunca dije que fuera un teorema. La tesis de Church-Turing es el mismo tipo de enunciado que los enunciados de las matemáticas en el sentido del tenedor de Hume , es decir, son relaciones de ideas, no de hechos sobre el mundo. Está confundiendo la tesis original de Church-Turing con la versión física actualizada de la tesis de David Deutsch , que es una declaración de hechos sobre el mundo.
¿Consideras las matemáticas una ciencia empírica?
lo siento, se suponía que estaba dirigido a @ user4894
Estoy de acuerdo en que CSIS no es una ciencia empírica. Pero "definitivamente una rama de las matemáticas" es otra historia. El concepto de computación se basa en la noción intuitiva de "procedimiento efectivo", y no veo ninguna razón para tratarlo como un concepto matemático.
@mobileink Creo que entiendo lo que entiendes: el procedimiento efectivo es más un artefacto humano que una verdad independiente, ¿es por eso que no estás de acuerdo? Pero también lo es la transformada de Fourrier, o la factorización de la matriz LU, pero esos siguen siendo objetos matemáticos sobre los que se pueden establecer teoremas, no objetos físicos, ver aquí
ahí la parte donde lo dices, y la parte donde lo retiras, como dijo una vez un famoso. la geometría también se basa en intuiciones derivadas de la experiencia de vivir en el espacio, así como la computación se basa en intuiciones derivadas de la experiencia vivida de calcular. entonces, ¿por qué este último no debería ser tan matemático como el primero? una respuesta posible: la teoría de la computación es un modelo matemático de algo no matemático. pero supongo que se podría decir lo mismo de Euclides, la geometría y el espacio.
Me inclino a pensar en las matemáticas, la lógica y la computación como puntos de vista diferentes de una cosa. hay problemas para coronar a cualquiera de ellos y tratar a los demás como derivados. ¿Quizás son en última instancia independientes?
@AlexanderSKing La tesis clásica de CT dice que un TM puede calcular cualquier cosa que un ser humano pueda calcular de manera efectiva . Esa es una declaración explícita sobre el mundo . Las declaraciones de matemáticas NO son declaraciones sobre el mundo. Por eso no estoy de acuerdo contigo. en.wikipedia.org/wiki/Church%E2%80%93Turing_tesis
@mobileink Math a menudo se inspira en el mundo real. Pero un teorema matemático no se trata del mundo. La TC trata explícitamente del mundo en cuanto se refiere a las capacidades de los seres humanos. Los teoremas matemáticos son sólo consecuencias formales de axiomas y reglas de inferencia. No son necesariamente sobre el mundo. La tesis de CT es explícitamente sobre el mundo. Esta es una gran distinción y que Alexander S King no tiene.
@ user4894 wikipedia puede no ser la fuente definitiva, pero incluso usa la frase "ser humano siguiendo un algoritmo" para lo que se aplica en el mundo real. Para mí, esta restricción adicional es la clave para interpretar CT como un resultado formal, aunque uno que pueda reflejar cosas "en el mundo real" (es decir, encarna una formalización particular de lo que es un algoritmo) y puede representar una restricción real en lo que puede suceder "en el mundo real" (tal vez esto sea representativo de lo que es posible ala Deutsch).
@ user4894 Los UTM son objetos matemáticos, λ-calculus es un sistema formal, es decir, un conjunto de objetos matemáticos, las funciones recursivas generales de Gödel son objetos matemáticos. La CT clásica es una conjetura de que una propiedad de estas tres clases de objetos matemáticos también se aplica a un conjunto más grande de objetos matemáticos. La TC clásica es problemática porque esta clase más general no está bien definida, no por la naturaleza empírica de la tesis. Estoy de acuerdo con usted en que se puede interpretar que tiene consecuencias empíricas, pero luego se convierte en la tesis Deutsch-CT, no en la CT clásica.
@AlexanderSKing No soy un experto, así que tendré que dejarlo como ya dije. Leí atentamente el artículo de la SEP plato.stanford.edu/entries/church-turing . La palabra "humano" aparece 48 veces. Es difícil no leer todo esto sin llegar a la conclusión de que CT está muy mal redactado; o bien es de hecho una declaración sobre el mundo.
@ user4894: tendremos que estar de acuerdo en no estar de acuerdo. ver R. artículo de soare sobre la historia del concepto de computabilidad en people.cs.uchicago.edu/~soare/History para una refutación de su afirmación por parte de uno de los principales académicos en el campo.
@Dave Vea mi respuesta a Alexander S. King. El artículo de SEP sobre CT usa la palabra "humano" 48 veces. Entiendo que CT habla de un humano ejecutando un algoritmo mecánicamente; pero aún así, siempre es un humano. Con esa definición, es difícil imaginar incluso a un platónico que afirme que existe un procedimiento efectivo sin humanos. Puede que exista un algoritmo en el reino platónico de las abstracciones, pero no hay ningún ser humano para ejecutarlo. CT tiene un carácter muy diferente a un teorema matemático. Pero no soy un experto, así que no puedo agregar más a lo que he dicho.

La tesis de Church-Turing es una tesis no demostrable, en lugar de un teorema, porque es una afirmación de que nuestra comprensión informal y no teórica de lo que cuenta como efectivamente computable está completamente capturada por lo que es computable por una máquina de Turing, o equivalentemente. , por una función recursiva general. El término hipercomputadora se usa para denotar un dispositivo informático que puede calcular cosas que no son computables por Church-Turing, por lo que otra forma de expresar la tesis es que es la afirmación de que no hay hipercomputadoras.

La afirmación de que no hay hipercomputadoras no es infalsable, pero una afirmación negativa como esta solo puede respaldarse (no probarse) haciendo nuestro mejor esfuerzo para diseñar una hipercomputadora y demostrando que es irrealizable. Se han propuesto varios modelos teóricos de hipercomputación, pero no se ha encontrado que ninguno sea factible de realizar.

Uno podría ir más allá y argumentar que para implementar una hipercomputadora, tendría que operar de una manera que sea consistente con las leyes de la física, y dado lo que sabemos actualmente sobre física, esto es intrínsecamente inverosímil. Una hipercomputadora tendría que basarse en una física extraña: incluso más extraña que la mecánica cuántica, ya que las computadoras cuánticas son consistentes con Church-Turing. Una computadora analógica ideal podría ser potencialmente una hipercomputadora, pero tendría que ser capaz de procesar números reales con una precisión infinita, lo que no es consistente con la imagen del universo que nos ofrece QM.

Por lo tanto, no es irrazonable aceptar que la tesis de Church-Turing es correcta y basar el trabajo científico en ella, aunque no podamos demostrarlo.

"El término hipercomputadora se usa para denotar un dispositivo informático que puede calcular cosas que no son computables por Church-Turing" No estoy seguro acerca del término "hipercomputación", pero tengo un dispositivo que calcula regularmente cosas que no son computables por un Máquina de Turing. a veces se le llama "entrada-salida".
No estoy seguro de por qué hiciste este comentario. Las máquinas de Turing (o funciones recursivas para el caso) pueden tener entrada y salida. Las hipercomputadoras son dispositivos teóricos putativos que pueden calcular cosas que no son computables por las máquinas de Turing.
Las máquinas de Turing no hacen io. esto es bien conocido.
Está utilizando entrada/salida de una manera extraña. El estado inicial de una cinta TM generalmente se considera su entrada y el estado final su salida. El mismo Turing usó los términos entrada y salida de esta manera para describir el funcionamiento de una MT, y otros lo han hecho desde entonces. Sería difícil explicar los conceptos de una TM universal, o el problema de la detención, sin hacer referencia a la entrada...
Si se refiere a algo más fuerte, como la capacidad de una máquina para permitir que un proceso externo reescriba su cinta mientras se realiza un cálculo, entonces tal máquina no sería una TM, pero aún sería muy polémico afirmar que no es equivalente a ninguna TM. Entonces, decir "las máquinas de Turing no hacen IO" en este fuerte ya que es cierto, pero no se sigue que usted "tenga un dispositivo que calcula regularmente cosas que no son computables por un TM".
Quise decir io en el sentido ordinario de la programación. printf no es una función computable de Turing. véase, por ejemplo, el trabajo de Peter Wegner sobre computación interactiva cs.brown.edu/~pw
Conozco el trabajo de Wegner, pero todavía considero que sus afirmaciones de haber refutado la tesis de Church-Turing son muy polémicas. No parecen haber logrado ningún consenso dentro de la comunidad de la teoría de la computabilidad. Hay una entrada en la parte de Ciencias de la Computación Teórica de Stack Exchange que cubre este problema: cstheory.stackexchange.com/questions/12377/…
jaja justo estaba leyendo ese hilo! En realidad, creo que Robert Soare es una mejor referencia, ver esp. su artículo sobre la historia de la computabilidad en people.cs.uchicago.edu/~soare/History
La cientificidad de la tesis de Church-Turing
RespuestasAquíPolítica de privacidad1y, 0v