La tesis de Church-Turing/La tesis

Origen

Como se ha comentado anteriormente, la tesis de Church permite definir un método tanto efectivo como mecánico que se puede utilizar tanto en las matemáticas como en la lógica. Sin embargo, no se ha podido encontrar una definición concisa y clara de los términos "efectivo"' y "mecánico" dentro de estas disciplinas.

Podemos afirmar que estamos ante un método o un procedimiento "efectivo" cuando verifica las siguientes condiciones:

• Está definido mediante un conjunto finito de instrucciones exactas. Cada una de las cuales se expresa mediante un número finito de símbolos.
• Si no existe ningún error, en un número finito de pasos, el procedimiento proporciona el resultado deseado.
• El procedimiento lo puede llevar a cabo cualquier ser humano, sin la ayuda de ningún tipo de máquina.
• Si se desea resolver no se necesita de ningún tipo especial de comprensión o de ingenio.

La tabla de verdad para la tautologicidad es un ejemplo típico de método de verdad. Sin embargo, si tenemos un número elevado de variables proposicionales no es posible utilizarlo; aunque en un principio, se podría aplicar a cualquier tipo de fórmula del cálculo proposicional. Se puede encontrar un método efectivo que nos permita encontrar los valores necesarios para dicha función matemática.

El concepto de método efectivo no verifica el requisito esencial de que el método no exija comprensión e ingenio, pues tal requisito permanece inexplicado, puesto que este concepto es intuitivo. Turing logró desarrollar un método formal que permitió reemplazar el predicado informal "puede ser calculado por medio de un método efectivo".

Church consiguió formalizar también dicho predicado. En principio, los predicados que tanto Turing como Church proponían reemplazar parecían muy diferentes, pero, sin embargo, eran equivalentes ya que seleccionaban el mismo conjunto de funciones matemáticas.

La tesis de Church se basa en la aseveración de que podemos encontrar un método, que satisfaga las condiciones de eficacia anteriormente expuestas, que nos permita obtener todos los valores de un determinado conjunto de funciones.

Como se ha dicho previamente en los orígenes de la computabilidad, Turing afirmó que un procedimiento computable es aquél que puede ser computado por una máquina de Turing. Es decir, si somos capaces de definir un método efectivo que obtenga los valores de una función matemática dada, entonces podremos encontrar una Máquina de Turing que sea capaz de computar dicho procedimiento.

A partir de lo anteriormente expuesto podemos deducir que un método efectivo es, en realidad, un programa reconocido por el modelo de máquina propuesto por Turing. De esta forma, si este enunciado es correcto entonces tenemos que encontrar un método efectivo o un programa para una máquina de Turing son conceptos equivalentes.

La formulación original de esta tesis se muestra a continuación:

Las máquinas de computación lógica (MCLs) pueden hacer cualquier cosa que podamos
describir como (un procedimiento) ‘puramente mecánico (Turing)

A este enunciado, añadió que:

Esto está bien establecido que es aceptado por muchos lógicos que ‘calculable
por medio de una MCL’ es el modo correcto de aludir a tales expresiones (Ibid)

Es necesario destacar, que el origen de la tesis de Church-Turing se encuentra en el hecho de que Turing deseaba demostrar que el problema de la decisión (Entscheidungsproblem), para el cálculo de predicados, carecía de solución, es decir, era insoluble. A continuación, se encuentra la resolución elaborada por Church para este problema.

Entendemos por Entscheidungsproblem un problema que consiste en encontrar un método efectivo que nos permita determinar si, dada una expresión representada mediante la notación del sistema (P), tanto para P como para no P podemos encontrar una solución que se encuentre dentro del sistema.

Por ejemplo, un método para realizar el cálculo proposicional es el de las tablas de verdad. Sin embargo, Turing demostró que, apoyándose en su tesis, dicho método para el cálculo de predicados no es posible. Para ello, dada una fórmula del cálculo de predicados, Turing demostró que no existía ninguna máquina de Turing, que en número establecido de pasos, nos permitiera determinar si se trata de un teorema del cálculo.

Meses antes Church había llegado a la misma conclusión. Para ello aplicó el concepto de ‘definibilidad-lambda’, en vez del concepto de computabilidad por una máquina de Turing. Lo más sorprendente de todo esto, radica en el hecho de que tanto Church como Turing llegaron a la misma conclusión de manera independiente.

Para señalar que existe un método efectivo que nos permite calcular los valores obtenidos por una función, Church utiliza la expresión “efectivamente calculable”. Church intenta definir este concepto apoyándose en la definición de función recursiva de enteros positivos (o, lo que es lo mismo, con una función lambda-definible de enteros positivos).

Enunciados

Tras un estudio exhaustivo se ha podido comprobar que existen diversas versiones de la tesis de Church-Turing. Esto se debe a que, cuando Turing enunció su tesis no lo hizo de manera formal y concisa, sino que esta tesis es bastante ambigüa. Esto ha provocado que los científicos que la han utilizado o la han leído, la hayan interpretado de manera diferente.

La formulación original de la tesis de Church se muestra a continuación:

"A function of positive integers is effectively calculable only if recursive."

Es decir, una función de enteros positivos es efectivamente calculable sólo si es recursiva.

A continuación, vamos a comentar brevemente tres de los enunciados más extendidos y utilizados que hemos encontrado:

• "Todo algoritmo o procedimiento efectivo es Turing-computable"

Esta es una de las versiones más aceptadas, puesto que constituye el resultado derivado de la revisión de los trabajos de A. Church y A. Turing.

En esta versión, se afirma que los algoritmos o procedimientos efectivos, elaborados tanto por un ser humano como por una máquina, pueden ser captados por una máquina de Turing.

Por tanto, en esta interpretación presentamos la Máquina de Turing como un modelo abstracto de un ordenador, puesto que es capaz de ejecutar el mismo conjunto de instrucciones que un computador.

• "Every function which World naturally be regarded as computable can be computed by a Turing machine"

Es decir, si una función es computable entonces puede ser computada por una máquina de Turing.

Sin embargo, al enunciar la tesis de Church de esta forma nos encontramos con un gran problema: no podemos demostrar formalmente la tesis de Church-Turing, puesto que para ello tendríamos que construir hipercomputadoras cuyos resultados "se consideren computables".

No podemos expresar una máquina de Turing mediante un programa y viceversa. Es decir, no podemos encontrar o definir un lenguaje de programación lo suficientemente genérico que nos permita expresar cualquier tipo de algoritmo.

• "Cualquier cosa que es intuitivamente computable puede ser computada por una máquina de Turing"

Se usa la palabra "tesis" en lugar de "teorema" ya que el concepto de ser computable es algo informal, sin embargo que el concepto de máquina de Turing es formal y preciso.

Aquí nos encontramos con un gran problema, puesto que la idea de la Máquina de Turing no es equivalente a cada una de las definiciones de "computabilidad" existentes.

• "Todos los procesos mentales se derivan de un substrato computable."

Esta versión un tanto reduccionista es claramente equivalente al enunciado original. Pero esta vez no se achaca a la máquina de Turing de imitar el pensamiento humano, sino que es a la mente humana a quien se tilda de poder abarcar sólo el proceso de resolución desde un punto de vista algorítmico.

Conclusiones

La tesis de Church-Turing ha conseguido definir de forma bastante clara, concisa y no ambigüa el concepto de "algoritmo".

Todas las personas son capaces de planificar una o varias tareas que, posteriormente, llevará a cabo una persona o máquina. A partir de esta afirmación, vamos a considerar que un algoritmo es un conjunto finito de instrucciones que se han definido para poder llevar a cabo una tarea determinada, en un número determinado de pasos.

Según la tesis de Church-Turing, el concepto de algoritmo que poseen los seres humanos y las definiciones formales de dicha palabra, utilizadas en las ciencias de la computación, son equivalentes.

Si realizamos un planteamiento más moderno, consideraremos un algoritmo como cualquier programa pueda ejecutar un ordenador. No resulta necesario escoger un tipo determinado de ordenador para realizar la demostración, ya que si dado un algoritmo diseñado en un computador, lo ejecutamos sobre otro ordenador el segundo siempre puede emular al primero. Es decir, el segundo ordenador actuaría como un intérprete.

Se dice que los algoritmos son universales ya que siempre es posible definir, independientemente del lenguaje de programación, un intérprete que ejecute un programa escrito en dicho lenguaje.

Sin embargo, no todos los computadores consumen la misma cantidad de recursos a pesar de que todos pueden realizar las mismas tareas. Estas son algunas de las razones que llevan las personas a escoger entre unas computadoras y otras.

La Tesis de Church-Turing, ¿Se puede considerar como una tesis?

Todavía no se ha podido demostrar, con argumentos sólidos, que la tesis de Church sea falsa, por lo que se asume que es totalmente verdadera.

El principal problema con el que nos encontramos al intentar rebatir esta tesis es que los conceptos de “algoritmo” y de “procedimiento efectivo” no se encuentran perfectamente definidos dentro de ninguna teoría matemática.

Además, estos conceptos resultan difíciles de definir, de tal forma que la enunciación escogida sea unánimemente aceptada.

En nuestro caso, vamos a definir un procedimiento efectivo o algoritmo como un conjunto finito de instrucciones ordenadas que se pueden ejecutar en un número determinado de pasos. En principio, un algoritmo podría ser llevado a cabo por cualquier ser humano utilizando para ello, únicamente, un lápiz y un papel.

Podemos encontrar multitud de ejemplos que se ciñen a esta definición, por ejemplo, el cálculo de la media aritmética de una serie finita de números. Sin embargo, a partir de nuestros conocimientos actuales no podemos definir claramente el concepto de “instrucción precisa” y, tampoco, podemos encontrar la lógica precisa para ejecutar las instrucciones.

Todo esto refuerza y da más importancia al concepto de máquina de Turing. Se trata de una máquina teórica que nos permite identificar los algoritmos o procedimientos efectivos. Aquí encontramos la principal razón por la que esta tesis está importante hoy en día.

Breve Estudio del Éxito de la Tesis

A lo largo de los años se ha intentado definir de manera clara y concisa:

• El concepto de computabilidad
• El cálculo lambda
• Las máquinas de registros
• Los sistemas de Post
• La lógica combinatoria
• Los algoritmos de Harkov

Todos estos sistemas reciben el nombre de Turing-completos porque son capaces de computar el mismo conjunto de funciones que una máquina de Turing.

Además, todos estos sistemas definen de manera equivalente el concepto de algoritmo, lo que contribuye a reforzar la creencia de que la tesis de Church-Turing es cierta, aunque no se pueda demostrar formalmente.

Es necesario destacar, que esta tesis todavía no se ha podido demostrar y que se trata, únicamente, de una mera definición y no de un teorema.

Actualmente, se están realizando diversos estudios para intentar refutar este enunciado, como por ejemplo el de las ARNN. Pero dichos estudios carecen, todavía, de unos fundamentos sólidos que permitan afirmar rotundamente que la tesis de Church es falsa, puesto que para demostrar esto sería necesario encontrar un método, universalmente aceptado, que no pudiera reconocer una máquina de Turing.

Analizando detenidamente la importancia e impacto que ha tenido esta tesis en gran cantidad de campos de todo tipo, podemos decir que el éxito de la misma se encuentra en la propuesta de una super tesis que la extiende. Además, se cree que es posible cambiar la representación, tanto de una función computable como de cualquier modelo de computación, que pueda ser simulado (paso por paso) por una máquina de Turing, utilizando simplemente para ello una transformación polinomial.

Según la tesis de Church-Turing si no podemos resolver un problema mediante una máquina de Turing, entonces no seremos capaces de encontrar ningún tipo de máquina algorítmica que resuelva dicho problema. Por tanto, deducimos que tanto las máquinas de Turing como los sistemas algorítmicos tienen la misma capacidad computacional.

Esta tesis ha tenido una relevancia e importancia mundial, revolucionando el campo de la computabilidad, hasta el punto de que la mayoría de la gente supone que es cierta.

Asimismo, este enunciado ha colocado las bases de la Inteligencia Artificial (IA), puesto que consideramos que todo tipo de proceso intelectual puede ser simulado mediante un ordenador, es decir, por una máquina de Turing (la MT nos permite solucionar problemas de carácter algorítmico).

¿Podemos considerar la Mente como una Máquina de Turing?

Algunos científicos consideran que el funcionamiento del cerebro es similar al de una Máquina de Turing. Para que esto fuera posible, debería ocurrir que las neuronas del cerebro siempre reaccionaran de la misma forma ante una determinada función de entrada.

La neurología todavía no ha podido demostrar que esta hipótesis sea cierta. Poco a poco se van realizando grandes avances en esta dirección, debido a que el funcionamiento de las neuronas es un tema bastante delicado, del que actualmente no poseemos un gran conocimiento y que, seguramente, se encuentra profundamente influenciado por las fluctuaciones cuánticas.

Si la mente se comportara como un sistema lógico, entonces ¿podríamos considerarlo como una máquina de Turing? Sí puesto que todas las Máquinas de Turing funcionan como sistemas lógicos, pero no todos los conceptos que nos permiten procesar los sistemas lógicos son, necesariamente, máquinas de Turing.

Además, las funciones de nuestra mente forman parte de la definición de “algoritmo efectivo”. Esto nos permite intentar probar, de manera lógica, que nuestra mente es equivalente a una máquina de Turing que posee una cinta circular.

Nuestras mentes deberían ser Máquinas Equivalentes-Plus (Te+); es decir, deberíamos ser capaces de realizar todas las funciones de una máquina de Turing, más algunas funciones adicionales tales como, por ejemplo, la intuición, la apreciación de matices, …

Los trabajos actuales están intentando incorporar algunas funcionalidades adicionales. En la mayoría de los casos dichas funcionalidades no afectan a la lógica de la máquina, por lo que no podremos obtener Máquinas Turing Equivalentes-Plus.