La tesis de Church-Turing/TextoCompleto

Introducción

En primer lugar vamos a introducir el concepto de teoría de la computabilidad, para ayudarnos a comprender este artículo.

Nociones Básicas acerca de la Teoría de la Computabilidad

La Teoría de la Computabilidad está compuesta por los siguientes niveles:

• Primer nivel: divide los problemas en tres clases:
  • Primer tipo:Problemas imposibles, no tienen solución.
  • Segundo tipo: Problemas ejecutables solo si disponemos de recursos ilimitados.
  • Tercer tipo:Problemas que se pueden ejecutarse sin necesidad de recursos ilimitados.
• Segundo nivel: se clasifican en función del tiempo que tardan en ejecutarse. Se conocen con el nombre de problemas indecidibles, impracticables o solucionables.
• Tercer nivel: comprende aquellos problemas que por ejemplo requiere un tiempo linealmente proporcional a su tamaño.

La incompletitud

Una de las preguntas que Hilbert planteó fue si las matemáticas eran completas, es decir: si cada proposición podía ser demostrada o refutada dentro de las matemáticas.

Gödel teorizó sobre la incompletitud de los sistemas axiomáticos, pero, tras varios intentos, fue Alan Turing quien apoyó esta teoría con la creación de su máquina, minuciosamente ideada para que pudiera interpretar cualquier algoritmo, y que sin embargo tenía problemas fuera de su alcance.

Para demostrar este hecho, bastaba con encontrar un sólo problema matemático que careciera de solución algorítmica.

La teoría de la computabilidad es conocida, también, como la teoría de las funciones recursivas. Esta disciplina contempla la existencia de procedimientos puramente mecánicos para resolver diferentes problemas.

Aunque esta teoría pertenece, principalmente, al campo de las matemáticas puras, es especialmente importante para aquellos que no son matemáticos. Este hecho se encuentra muy relacionado tanto con determinadas cuestiones filosóficas como con la teoría de los computadores digitales.

Algunos de los resultados que se encuentran englobados dentro de la teoría de la computabilidad son:

• La existencia de problemas absolutamente insolubles

• Teorema de la incompletitud de Gödel

La computabilidad Turing

Otro de los resultados más importantes de esta teoría es la existencia de las máquinas universales de Turing. Estos modelos teóricos simulan ser una máquina de Turing recibiendo en su entrada, todo lo relativo al modelo a imitar, sin embargo poseen un conjunto finito que no debe ser modificado.

La máquina puede recibir como información de entrada instrucciones o estados de la misma.

En 1930, la computabilidad Turing permitió clasificar las funciones para las que existen algoritmos. El dilema era saber si existían problemas no resolubles por la Máquina de Turing, porque carecían de solución algoritmica o por que esta no podía resolverlos.

Por tanto la cuestión es saber si la intuición humana supera o no la capacidad de una máquina de Turing.

Evolución Histórica

Introducción

En el año 1928 Hilbert y Ackermann publican un libro sobre la lógica de primer orden, proporcionando un conjunto de reglas para la realización de las deducciones lógicas. Demostraron además como la lógica de primer orden formalizaba parte de las matemáticas.

Uno de los mayores problemas de Hilbert y Ackermann era determinar si su inferencia era válida utilizando un algoritmo. Consistía en encontrar un algoritmo que validase la conclusión obtenida utilizando las reglas de Hilbert-Ackermann.

El principal problema de la lógica matemática recibe el nombre del "problema decisorio", ya que si se encuentra un algoritmo que determine si una inferencia es válida o no, esto permitiría resolver cualquier problema matemático utilizando simplemente la lógica de primer orden.

La siguiente ilustración muestra la evolución histórica de la teoría de la computabilidad:

Eje Cronológico

Comentario acerca del Procedimiento Decisorio

El procedimiento decisorio para un concepto es viable o soluble, si se puede encontrar un algoritmo computacional que, al aplicarlo a un objeto cualquiera en un número finito de pasos, nos permita clasificarlo como ejemplo o contraejemplo de tal concepto.

Si nos encontramos en el caso de que para un mismo concepto existen tanto pruebas positivas como negativas, se dice que dicho problema es soluble, de modo que para cualquier entrada al procedimiento computacional podemos clasificarlo como positivo o negativo.

Los conceptos en los que más nos vamos a centrar son la validez y la satisfacibilidad, mientras que los objetos de entrada van a constituir la notación de la lógica de primer orden.

Entscheidungsproblem

En 1928 durante un congreso internacional D. Hilbert planteó las siguientes cuestiones:

• ¿Las matemáticas son 'completas', esto es, cada afirmación matemática se puede probar?
• ¿Las matemáticas son 'consistentes', esto es, es posible probar paralelamente una afirmación y su negación?
• ¿Las matemáticas son 'decidibles', esto es, se puede encontrar un método definido aplicable a cualquier afirmación matemática, que nos de cómo resultado si es o no cierta la aseveración evaluada?

La intención de Hilbert era conseguir un modelo matemático formal, completo y consistente, en el que a través de un algoritmo, se pudiese determinar la veracidad o falsedad de cualquier proposición formal. Este problema recibió el nombre de “Entscheidungsproblem”, resolverlo significaría que para cualquier problema bien definido existiría un algoritmo capaz de resolverlo.

Teorema de la Incompletitud

En 1930 algunos investigadores determinan que es imposible resolver el problema de Hilbert. En el año 1931, Gödel publica el Teorema de la Incompletitud que demuestra que es imposible resolver el sistema propuesto por Hilbert en 1928.

"Todo sistema de primer orden consistente que contenga los teoremas de la aritmética, cuyo conjunto de axiomas sea recursivo no es completo"

Eje Cronológico 2

La idea genial de la demostración de Gödel se basa en la construcción de una técnica que puede ser comprobada por cualquier sistema descrito, pero no por el propio sistema.

Debido a este problema no es posible construir un sistema formal, en la lógica de primer grado, como pretendía Hilbert, a no ser que se tomase un conjunto no recursivo de axiomas.

Seleccionar un conjunto no recursivo de axiomas supone un gran problema puesto que se desconoce la manera de verificar si una fórmula es o no un axioma y por tanto si una fórmula podemos tratarla o no como un axioma, o lo que es lo mismo, si una demostración es o no válida.

Se podría pensar en sistemas inductivos más potentes que la lógica de predicados de primer orden. Una versión posterior del Teorema de Incompletitud de Gödel lo descarta:

"Ningún sistema deductivo que contenga los teoremas de la aritmética, y con los axiomas recursivamente enumerables puede ser consistente y completo a la vez." (Generalización del Teorema de completitud de Gödel).

Esta afirmación nos indica que resulta imposible encontrar un sistema formal completo y consistente para realizar afirmaciones matemáticas. Trabajos posteriores reafirmaron esta posibilidad.

El aspecto más relevante en el Teorema de Incompletitud de Gödel, tiene su irmportancia al dar origen a Teoría de la Computabilidad. Los pasos seguidos son:

1. Se indica un número, numeración de Gödel, mediante el cual se asigna un entero positivo, que es un código a cada fórmula bien formada del sistema (fbf). El lector puede pensar en programa si lo desea.

1. Una sucesión finita de fórmulas bien formadas de modo que la fbf o sucesiones finitas de fbfs se recuperen fácilmente a partir del número de código. Gracias a este código los enunciados referentes a valores de enteros positivos pueden considerarse como enunciados referentes a números de expresiones, o incluso a las propias expresiones.

Esta última idea fue utilizada a posteriori para codificar algoritmos con enteros positivos y, de esta forma poder lograr un algoritmo cuyas entradas fuesen enteros positivos y extenderlo a algoritmos cuyas entradas fuesen otros algoritmos.

Tarski fue también un personaje importante que colaboró siempre en esta misma línea, llegando formalmente a conclusiones como que la verdad o veracidad de un sistema aritmético sólo podría ser probado fuera de él.

Calculabilidad efectiva

En 1936, surgen de un modo casi simultáneo varios modelos distintos del concepto de calculabilidad efectiva. Corresponden a los trabajos de Kleene, Church, Turing y Post. Tanto Kleene como Post trabajaban sobre problemas que eran indecibles mientras que, Church y Turing, además demostraron que el "Entscheidungsproblem" era un problema indecidible.

Eje Cronológico 3

Church propone como definición de función efectivamente calculable la función-definible. Empleó la notación del "cálculo lambda" para poder expresar de un modo estándar cualquier fórmula matemática. Su origen es de 1923-1933 Church lo introdujo para fundamentar las matemáticas.

Gracias a ello, los teoremas pueden expresarse como la transformación de cadenas de símbolos en otras, usando un conjunto de reglas formales en cálculo lambda.

Años más tarde se demostró que este sistema resultaba inconsistente. La posibilidad de expresar mediante elementos o términos del sistema las funciones numéricas resultó una idea muy atractiva tanto para Church como para sus colaboradores. Church define una función "efectivamente calculable" como función-definible en 1934.

Durante el transcurso de ese mismo año, Gödel había seguido estudiando la idea de Herbrand de que una función $f$ podía definirse como un conjunto de ecuaciones entre términos, incluyendo tanto a la misma función así como una serie de símbolos para funciones previamente definidas. Gödel dio forma a esta idea determinando que cada valor de la función f tenía que obtenerse sustituyendo en las ecuaciones las variables por números y, los términos sin variables, por valores que ya se habían probado que designaban. Permitiendo definir la clase de "las funciones recursivas de Herbrand-Gödel".

Enunciado de la tesis de Church

En 1936, Church logra demostrar que tanto las funciones-definibles como las funciones recursivas de Herbrand-Gödel son equivalentes. Conjetura que este tipo de funciones son las únicas funciones calculables utilizando, para ello, un algoritmo a través de la tesis que lleva su nombre:

"La clase de las funciones que pueden ser calculadas mediante un algoritmo coincide con la clase de las funciones recursivas." (Tesis de Church).

Apoyado en esta tesis junto a la definición de función definible, encontró varios ejemplos de problemas cuya resolución era irresoluble llegando a manifestar que el ‘Entscheidungsproblem’ era uno de estos problemas.

Meses más tarde Kleene llegó a la misma conclusión que Church pero sus ejemplos de problemas irresolubles tenían su base en el concepto de función recursiva.

Enunciado de la tesis de Turing

La tercera de las definiciones de función calculable tiene su origen en el matemático inglés Alan Turing, que fue durante un tiempo alumno de Von Neumann, y que leyó los argumentos de Hilbert durante sus estudios en Cambridge. En 1936 Turing publicó uno de sus trabajos más importantes: "Números Computables: Una Aplicación al Entscheidumgsproblem".

Archivo:Eje cronologico 4.png

El objetivo de Turing era el de enfrentarse al problema planteado por Hilbert (el Entscheidumgsproblem) utilizando para ello el concepto abstracto de una máquina, una máquina teórica. El motivo de este acercamiento a la realidad era el de simplificar los cálculos al máximo, describiendo una serie de procedimientos básicos, a los que puede reducirse cualquier otro.

Turing describía en su artículo que a través de su máquina había conseguido caracterizar de un modo matemático el número de funciones calculables, usando para ello un algoritmo, este hecho se conoce como:

La clase de las funciones que pueden ser calculadas mediante
un método definido coincide con la clase de las funciones
calculables mediante una Máquina de Turing
(Tesis de Turing). 

Turing expuso su tesis como un teorema demostrado, utilizando su concepto de máquina teórica, logro demostrar que existen funciones que no son calculables o resolubles por un método definido y en concreto que el ‘Entscheidungsproblem’ era uno de estos problemas.

Cuando Turing elaboró su artículo, desconocía los trabajos sobre las funciones definibles y calculables de los trabajos de Church-Kleene, así que cuando tuvo noticias de los mismos, los incluyó en su apéndice en el que demostraba usando su máquina que los conceptos de función-definible y función-calculable, eran equivalentes.

Por este motivo tanto la tesis de Turing como la de Church son similares, al fin vienen a decir lo mismo, y se fusionan: La tesis de Turing afirma que el conjunto de las funciones computables coincide con el número de las funciones que puede calcular la máquina de Turing. Ambas tesis Turing y Church, son equivalentes. Por eso nos referimos a ambas tesis como tesis de Church-Turing.

Por supuesto para llegar a esta conclusión es necesario previamente obtener una definición de función computable. Surgieron otras definiciones de funciones computables que resultaron ser equivalentes a la de Turing, entre ellas destaca la teoría de funciones recursivas y el cálculo lambda desarrollado por Church entre los años 1932 y 1941. Su objetivo era el de captar el aspecto computacional de las funciones. No usaba la definición tradicional de pares dato-resultado, su interés se centraba en la transformación desde el dato de partida hasta el resultado.

Desde un punto de vista sencillo el cálculo lambda consiste en una gramática de términos y unas reglas de transformación entre los mismos, representando estas funciones. La característica más importante del cálculo lambda consiste en que una gramática puede aplicarse a sí misma, se pueden definir funciones recursivas sin usar tener que usar recursividad.

A pesar de lo que pueda parecer en un principio no surge ningún tipo de paradojas o inconsistencias. La tesis de Church-Turing consiste en afirmar que las funciones computables son aquellas que pueden ser expresadas a través del cálculo lambda. Turing logró la equivalencia entre su máquina teórica y este cálculo en 1937.

Archivo:Eje cronologico 5.png

A raíz de las máquinas de Turing ha surgido una rama en la informática teórica con el nombre de 'Teoría de la Computabilidad'. Mientras que el cálculo lambda supone la base teórica del paradigma de programación funcional.

El trabajo de Post era el delimitar una frontera entre los procedimientos formales y el entendimiento para desarrollar las matemáticas. Post utiliza los sistemas deductivos normales para crear un modelo de procedimientos efectivo.

Permiten deducir sucesiones finitas de símbolos como consecuencia de otras sucesiones de símbolos finitas, utilizando un conjunto de reglas y axiomas. Post señaló en su artículo, que en estos sistemas se podrían encontrar situaciones de indecibilidad e incompletitud.

Post desconocía el trabajo realizado por Turing, aunque conocía el trabajo de Church-Kleene. Esto es patente en el hecho de que el modelo procedimental efectivo que definió Post es diferente del de Turing.

Progresos de Kleene

En 1938, Kleene fue el primero que se dio cuenta de que había funciones parciales originadas por algoritmos que nunca finalizaban, a partir de ellos se pueden obtener todos los resultados anteriores. El estudio de funciones parcialmente calculables ha sido esencial para el posterior desarrollo de ésta materia. Estos estudios son fundamentales para la demostración del teorema del punto fijo y el teorema de recursión de Kleene de 1952.

Archivo:Eje cronologico 6.png

Posteriormente se demostró que tanto lo que podía calcular un sistema formal como una máquina de Turing eran equivalentes:

En los sistemas deductivos donde el conjunto de reglas de producción, y el conjunto de axiomas sea recursivamente enumerable, una función(parcial) aritmética es 'calculable' si y solo si es una función (parcial) 'recursiva'.

El primer paso en la teoría computacional

La tesis de Church-Turing es considerada como el primer axioma en la teoría de la computación, permitiendo comenzar a estudiar los problemas resolubles mediante un algoritmo.

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.

Interpretaciones

En esta sección se van a explicar algunas de las diversas interpretaciones que tiene la tesis de Church-Turing.

Principio Church-Turing-Deutsch

En general, la tesis de Church se considera un postulado sobre matemáticas. Esta idea proviene del hecho de que dicha tesis describe el subconjunto de las matemáticas que puede ser computado; por el contrario, la Tesis Extendida de Church-Turing define el subconjunto de las matemáticas que puede ser automatizado incuestionablemente.

En 1985, Deutsch afirma que la tesis de Church es demasiado general en comparación con algunos de los principios físicos conocidos. Deutsch propone referirse a las "funciones que de manera natural sean consideradas computables" como "funciones que puedan ser computadas por un sistema físico real", ya que de esta forma lo que se quiere expresar es mucho más concreto. Todo esto le permitió introducir la concepción del diseño de una máquina de Turing.

La idea anteriormente expuesta es innovadora e interesante ya que para nosotros no es fácil entender que algo "considerado computable de forma natural" no pueda ser computado por la naturaleza. De esta manera, Deutsch convierte la tesis en un principio llamado "Principio de Church-Turing-Deutsch" cuyo enunciado se muestra a continuación:

"Todos los sistemas físicos finitos comprensibles pueden ser simulados por una máquina de computación universal que opere en pasos finitos".

Por último, la extensión de este principio al caso cuantitativo (al que nos referiremos como “CTDP Extendido”) es sencilla:

"Todo sistema físico finito puede ser simulado por una máquina de Turing, cuyo coste es equivalente al coste polinomial"

Esta es una de las implicaciones más importantes de la Tesis de Church-Turing. Principalmente, nos vamos a fijar en la siguiente consecuencia: a partir de este momento, dado un conjunto de leyes físicas perfectamente definidas mediante el uso de experimentos, seríamos capaces de deducir a partir del CTDP, como una consecuencia directa de estas leyes, que todos los sistemas definidos mediante reglas se pueden simular usando para ello una máquina de Turing.

Es necesario destacar, que las interpretaciones clásicas de la Tesis de Church no alcanzan esta conclusión.

Tesis Física de Church-Turing (PCTT)

El enunciado de la tesis física de Church-Turing (PCTT) se muestra a continuación:

"Every function that can be physically computed can be computed by a Turing machine"

Una posible traducción podría ser: cualquier función que pueda ser físicamente computable, puede ser computada por una máquina de Turing.

En 2002 este teorema fue refutado por Willem Fouché, puesto que descubrió que las máquinas de Turing no pueden obtener todos los valores posibles, unidimensionales, de los números racionales.

Strong Church-Turing thesis (SCTT)

En 1997, Bernstein y Vazirani expusieron la tesis Strong Church-Turing (SCTT), cuyo enunciado se muestra a continuación:

"Any ‘reasonable’ model of computation can be efficiently simulated on a probabilistic Turing machine".

Es un misterio que la tesis original de Church-Turing sea equivalente a esta interpretación, aunque Turing negó dicha coincidencia.

Los estudios actuales sugieren que este enunciado es falso, puesto que no es posible capturar todas las formas de computación tanto existentes como posibles mediante un algoritmo. Por ejemplo, los protocolos interactivos no son algoritmos.

Uno de las principales razones de que se llegara a la conclusión de que dicho enunciado era falso, fue que Peter Shor demostró que el problema de factorizar los números primos se puede resolver usando un ordenador cuántico, mientras que no es posible encontrar una solución al mismo problema usando una máquina probabilística de Turing.

Las razones para por las que se acepta de forma general la “Tesis Mítica de Turing” se pueden examinar en el momento en que se estableció la Informática como una disciplina independiente en 1960. Para poder entender mejor estas razones, vamos a identificar y examinar las tres principales quejas:

• Conjetura 1: Todos los problemas computables están basados en una función. Razón: La adopción de los principios matemáticos para los conceptos fundamentales de la computación, identifican el concepto de computabilidad con la computación de funciones, al igual que con la Máquinas de Turing.

• Conjetura 2: Todos los problemas computables pueden ser descritos mediante un algoritmo. Razón: La adopción de algoritmos como conceptos generales y centrales de la Informática.

• Conjetura 3: Los computadores procesan los algoritmos. Razón: se concibe el concepto de un algoritmo para hacerlo más práctico.

Tesis de Church-Turing Extendida (ECT)

Esta tesis afirma que la máquina de Turing es tan eficiente como un computador. Es decir, si alguna función es computable por algún dispositivo hardware para una entrada de tamaño n, entonces dicha función es computable por una máquina de Turing en (T(n))k para algún k fijo (dependiente del problema).

La Tesis de Zuse-Fredkin

Esta tesis fue enunciada formalmente en 1960 por Zuse y Fredkin. A continuación, se muestra la idea principal de la misma:

"El universo es un autómata celular"

Si una persona considera que la tesis de Church es verdadera entonces no puede encontrar ninguna razón que le indica que la tesis de Zuse-Fredkin es falsa, y viceversa.

En primer lugar, partimos de que si somos capaces de probar la tesis de Zuse-Fredkin, entonces podremos deducir de manera inmediata la tesis de Church-Turing. El argumento es el siguiente:

• Si el universo es una autómata celular universal (UCA, Universal Cellular Automaton), obviamente, nos encontraremos con procesos computacionales pequeños, lo que nos permitirá llegar a la conclusión de que disponemos de una serie de algoritmos que actúan sobre una región específica del espacio/tiempo del autómata.

• Por otro lado, cada UCA es capaz de simular cualquier otra máquina abstracta computacional, incluyendo a la Máquina Universal de Turing.

A continuación, vamos a analizar un poco la tesis de Church-Turing para determinar por qué su aparición corrobora la tesis de Zuse-Fredkin.

La tesis de Church-Turing intenta demostrar que cada función matemática computable tiene una representación isomórfica (es decir, se encuentra representado mediante un algoritmo) en un dispositivo computacional, llamado UTM.

La tesis de Zuse-Fredkin dice, en su mayoría, lo mismo como, por ejemplo, que el Universo es un dispositivo computacional que se puede considerar como una gran máquina computacional que podemos llamar Autómata Celular (CA).

También podemos decir que la tesis de Zuse-Fredkin está expuesto indirectamente un ‘hint’ directo (o, incluso, un “corolario físico”) expuesto en la tesis de Church-Turing. ¿Por qué?

A continuación, se muestra la razón propuesta:

• Toda la física, que conocemos actualmente, no es nada más que un intento por “comprender” la Realidad, para lo que se utiliza una fórmula que consiste en construir una serie de “modelos matemáticos” (o “teorías”) que explican los fenómenos que se producen en el Universo.

Pero, por otro lado, podemos decir que cualquier “fórmula” o “teoría” puede ser representada (de acuerdo con la tesis de Church) mediante una UTM.

La única forma que conocemos para “estudiar” (o “comprender”) la Realidad se basa en utilizar modelos o teorías matemáticas; he aquí la gran idea de la tesis de Zuse-Fredkin de que el Universo es una especie de dispositivo computacional, denominado, autómata celular.

La Tesis M

La tesis M dice:

Todo aquello que pueda ser calculado por una máquina (en caso de que se trabaje con datos finitos de acuerdo a un número finito de instrucciones) es computable por una máquina de Turing.

La tesis M por sí misma admite dos interpretaciones:

• Si la frase "puede ser generado por una máquina" se interpreta en sentido estricto como “puede ser generado por una máquina que se base en las leyes físicas del mundo actual”.
• Si la frase anterior se interpreta en sentido más amplio, de tal forma que nos abstrajéramos de si la máquina abstracta en cuestión puede o no existir en el mundo actual.

Si escogemos la segunda interpretación, entonces la tesis M es falsa. Es fácil describir máquinas abstractas, o ‘hipercomputadoras’ , que generan funciones no computables por una máquina de Turing, por ejemplo Abramson, Copeland y Proudfoot, Stewart.

Todavía no se puede determinar si la primera interpretación de la tesis M es o no cierta. Las especulaciones que se realicen sobre la posibilidad de que existan procesos físicos cuyo comportamiento se parezca a funciones no computables por la máquina de Turing se remonta al menos a las últimas cinco décadas; algunos ejemplos son: Doyle, Geroch y Hartle, Hogarth, Kreisel, etc.

De hecho, ésta es la verdadera tesitura o dilema en la veracidad de la Tesis de Church-Turing. Nosotros los humanos y nuestra computabilidad intuitiva no seríamos lo importante en el enunciado de la tesis si no nos consideráramos el ente computacionalmente más complejo. La indicación de que el superconjunto de las computabilidades no tiene porqué residir en el cerebro humano es un acierto de la tesis M.

Al no estar, al igual que la Tesis de Church-Turing, debidamente formalizada, la literatura sobre la teoría computacional de la mente humana contiene numerosas proposiciones equivalentes o similares a la tesis M, todas ellas basadas en los trabajos de Turing o Church.

Algunos investigadores opinan que la tesis M (o alguna otra equivalente) debería caracterizar, de manera informal, el concepto de procedimiento efectivo de tal forma que se pueda modificar para que sea equivalente al concepto tratado. Esta acción afecta muy especialmente a la magnitud de los procedimientos efectivos, y al hecho de que puedan ser computados por una máquina.

Para cada error cometido, el espacio conceptual que no parece contener los modelos mecánicos de la mente que no son equivalentes para las máquinas de Turing. Todavía es posible que la psicología descubra la necesidad de emplear los modelos de la percepción humana que sobrepasan a las máquinas de Turing.

Es necesario destacar que en algunos casos, es importante que el autor haga una mención especial a otros anteriores. En esta línea, se recuerda que en la literatura técnica la palabra ‘computable’ se relaciona, con frecuencia, con la definición de calculabilidad efectiva.

Por supuesto, se dice que una función es computable si y sólo si podemos encontrar un método efectivo para encontrar sus valores. De acuerdo con esto, una formulación común de la tesis de Church-Turing en la literatura técnica y en los libros suele ser:

"All computable functions are computable by Turing machine"

Algunos corolarios exponen la siguiente idea:

Por supuesto, las funciones no son computables en sentido absoluto: las funciones que no son computables por la máquina de Turing, no podrán ser computadas ni en el pasado, ni en el presente ni en el futuro por una máquina real (Boolos and Jeffrey). Esto es equivalente de nuevo a la tesis M, en el sentido de que «máquina» se refiere a «máquina real».

Dada la definición de ‘computable’ como ‘efectivamente calculable’, la tesis de Church-Turing afirma que si una función F no es computable por una máquina de Turing entonces no es computable por ninguna máquina.

Por supuesto, la decisión tomada para definir el término ‘computable’ y su aceptación del concepto de efectividad no establece la validez de la tesis M. Aquéllos que hayan optado por esta decisión terminológica han sido, simplemente, prevenidos para que describan una máquina que refute la tesis M como una función computable.

La palabra ‘mecánico’, también, en términos técnicos, se relaciona estrechamente con la efectividad y, como ya se señaló anteriormente, ‘mecánico’ y ‘efectivo’ se pueden usar indistintamente (Gandy, en 1988, estructuró la historia del uso de la palabra ‘mecánico’). Por supuesto, los siguientes postulados se pueden encontrar en la literatura técnica:

Turing propuso que una clase concreta de máquinas abstractas que podrían ejecutar algunos de los procedimientos computables ‘mecánicos’ (Mendelson).

Si reflexionamos sobre la idea anterior, observamos como remarca los atributos de Turing, no para la tesis M, pero sí para la tesis de Church-Turing.

La tesis M no es, sólo, una tesis problemática que esta relacionada estrechamente con la tesis de Church. Desafortunadamente, un error común en los escritores modernos en computabilidad consiste en mantener que los resultados de Turing, se encuentran vinculados de alguna manera con la mente humana, e incluso con cualquier sistema físico o biológico, de tal forma que pueden ser simulados mediante una máquina de Turing.

Por ejemplo, la entrada reciente de Turing en Una Compañía para la Filosofía contiene la siguiente declaración:

Podemos depender de una máquina de Turing que capture las relaciones
funcionales del cerebro”, ya durante mucho tiempo “estas relaciones entre
las entradas y las salidas se encuentran funcionalmente bien-formadas, de
tal forma que pueden ser descrito mediante…relaciones matemáticas… de
tal forma, que sabemos que alguna versión específica de una máquina de
Turing será capaz de representarlas” (Guttenplan).

Searle llegó a una conclusión similar:

¿Es posible simular el comportamiento del cerebro humano mediante una
máquina?

La respuesta parece ser… de manera irrefutable “SI”… Interpretada de manera normal, la pregunta quiere decir:

¿Existe alguna descripción del cerebro que se parezca a la descripción que
podríamos hacer de una simulación computacional de las operaciones del
cerebro?

A partir de la tesis de Church, según la cual cualquier procedimiento que pueda ser simulado (paso por paso) por un computador digital, resulta trivial que la respuesta a la pregunta es claramente afirmativa (Searle 1992:200).

Asimismo, Johnson-Laird y Churchlands expusieron lo siguiente:

Si es posible garantizar que la tesis de Church-Turing es correcta y, además, estamos seguros de que es así entonces:

• Si pensamos que el funcionalismo es falso, entonces tendríamos que plantearnos la construcción de una máquina que verificara esto.
• Por el contrario, si defendemos el funcionalismo entonces tendríamos que creer que la conciencia, en esencia, es tan sólo un proceso computacional.

La tesis de Church-Turing expone que si el tiempo es computable, entonces se puede computar mediante una máquina de Turing. Asumiendo que es posible computar el cerebro, entonces podemos simular este principio mediante un ordenador (Churchland and Churchland 1983:6).

Como previamente se ha mencionado, Churchaland and Churchland parece creer, erróneamente, que los "resultados hacen referencia… a que un computador digital, sólo muestra los programas correctos, con suficiente tiempo y memoria, puede… mostrar alguna forma sistemática de responder a las etapas" de Turing (1990:26). No existe explicación alguna a cerca de las restricciones de hablar de "patrones sistemáticos" que son efectivamente calculables.

La tesis de Church-Turing no contempla que el cerebro (o la mente, o la consciencia) pueda ser modelada por un programa de una máquina de Turing, sin contradecir la conjetura que cree que el cerebro (o la mente, etc) es científicamente explicable.

Cada uno de los autores citados parecen asumir como la verdad de un cierre de la tesis M, que denominaremos tesis S, cuyo enunciado se muestra a continuación:

"Any process that can be given a mathematical description (or that is scientifically describable or scientifically explicable) can be simulated by a Turing machine."

Como la tesis M, ni la tesis de Church-Turing propiamente llamada ni ningún resultado probado por Turing o Church enlaza con la tesis S. Esto se produce cuando la tesis no se acepta totalmente, cuando se hace referencia al mundo real.

La tesis S toma, como entradas, las sensaciones que percibimos como falsas; las cuales se pueden relacionar fácilmente con la tesis M. Cualquier dispositivo u órgano que procese internamente pueden ser descrito completamente mediante el concepto de funciones efectivamente calculables, por lo que pueden ser simulados perfectamente mediante un programa que se pueda ejecutar en una máquina de Turing (se determina que las salidas de los dispositivos u órganos son Turing-computables). Es decir, también se puede expresar como un número computable, en opinión de Turing); pero cualquier dispositivo u órgano del que podamos obtener una descripción matemática mediante una función que no sea efectivamente calculable no puede ser tampoco simulada.

Como Turing mostró, hay un número infinito de funciones no computables. Los ejemplos de la lógica son las famosas funciones de parada de Turing (descritos en la entrada de la máquina de Turing) y la función D, cuyo dominio se encuadró en las fórmulas bien formadas del cálculo de los predicados y cuyos valores, D(x), son 1 o 0 en función de que X es, o no es, deducible del axioma de los predicados lógicos de Bernays-Hilbert-Ackermann.

Implicaciones

Tras estudiar en profundidad la tesis de Church-Turing, nos encontramos con que existen diversas implicaciones filosóficas bastante interesantes e importantes. Además, podemos encontrar cuestiones que nos permiten vincular la tesis de Church con la física y con la construción de hipercomputadoras.

Si aplicamos los principios físicos, podemos encontrarnos con que esta tesis tiene diversos significados:

• Consideramos que nuestro Universo es, en realidad, una máquina de Turing. En este caso, no seríamos capaces de concebir ni de imaginar ningún tipo de máquina cuyo poder computacional fuera mayor que el de una máquina de Turing y, que además, no sea capaz de procesar funciones no recursivas. O, lo que es lo mismo, estamos limitando la capacidad de cómputo de nuestra máquina al universo en el que estamos trabajando.

• Si consideramos que el Universo no es una máquina de Turing (o, lo que es equivalente, no es posible computar la leyes que rigen el universo) entonces podremos construir una máquina cuyo poder computacional sea mayor que el de una máquina de Turing.

• Por último, podemos concebir el Universo como una Hipercomputadora. En este caso, podríamos construir máquina más eficaces que las máquinas de Turing utilizando, únicamente, los resultados de dicha hipercomputadora: el universo o la naturaleza. Sin embargo, para que esto pudiera ser realidad se tendría que verificar que el universo es continuo y que, además, hace uso de dicha propiedad.

Otras Máquinas

En este apartado se va a proceder a describir una serie de máquinas que

• o bien surgieron como intento de ampliar el poder computacional de la Máquina de Turing clásica
• o bien surgieron como pasatiempo y luego se demostraron computacionalmente equivalentes a la Máquina de Turing

Máquinas Cuánticas

En 1985, Deutsch presentó eldiseño de la primera Máquina Cuántica basada en una máquina de Turing. Para poder hacer esto, Deutsch enunció la tesis de Church de manera diferente dando lugar al denominado "Principio de Church-Turing-Deutsch".

A partir de este momento, diseña la primera máquina cuántica de Turing, cuya estructura es muy similar a la de una máquina de Turing clásica. Podemos definir una máquina cuántica, como una máquina formada por una serie de estados finitos, en la que destacan tres componentes:

• Una unidad de memoria finita
• Un procesador finito
• Un cursor

La siguiente ilustración muestra el esquema de una máquina cuántica:

Los QuBits (tal como se muestran en la ilustración anterior) nos permiten representar, que en esta máquina, el procesador está formado por un número finito de estados.

El juego de instrucciones de esta máquina, está formado por los cambios que se realizan sobre los QuBits de control (hay que tener en cuenta, que a veces esto puede depender del QuBit que se esté procesando en un momento dado sobre la cinta). Además, esta máquina sólo puede realizar una instrucción por unidad de tiempo.

La unidad de memoria es similar a la cinta de memoria de una máquina de Turing tradicional. La única diferencia entre ambas radica en el hecho de que, por cada elemento de la cinta de la máquina cuántica, tenemos un QuBit. Por tanto, podemos decir que el alfabeto de esta nueva máquina está formado por el espacio C2 del QuBit.

Finalmente, podemos definir el cursor como el elemento que nos permite comunicar la unidad de memoria y el procesador. Para almacenar su posición dentro de la cinta utilizamos una variable entera. Es necesario resaltar, que el cursor sólo puede procesar un elemento de la cinta por unidad de tiempo.

Máquinas con Oráculo (O-Machines ó MTO's)

En primer lugar vamos a proporcionar una definición de la palabra "oráculo". Tanto en la teoría de la complejidad como en la de la computabilidad, se define la palabra oráculo como una especie de "caja negra", cuya principal característica es que nos permite computar una función concreta de una sola vez.

De esta forma, seríamos capaces de encontrar una función que pudiera solucionar un problema NP-completo como, por ejemplo, el de la suma de un subconjunto. Incluso, podríamos descubrir que nos encontramos ante una función no computable (es decir, no recurrente) como, por ejemplo, el problema de la parada.

Las máquinas de Turing con oráculo nos permiten resolver, utilizando para ello información adicional, diferentes tipos de problemas.

Realmente, este tipo de máquinas representan un intento de Turing por añadirle mayor poder computacional a su máquina original (la Máquina de Turing), puesto que las Máquinas con Oráculo nos permiten resolver problemas que carecen de solución algorítmica.

En esencia, la MTO es una máquina de Turing, conectada a un oráculo, cuya principal característica es que está capacitada para determinar si un elemento pertenece o no a un conjunto específico de números naturales.

Esta máquina posee tres estados especiales:

• Estado llamada
• Estado-1
• Estado-0

Además, está formada por un elemento adicional, un símbolo especial que actúa de marcador: μ. Para poder usar su oráculo la máquina debe escribir, en dos recuadros de la cinta el marcador y, entre ambos el símbolo que se desea verificar. Una vez hecho esto, se pasará al estado de estado llamada. A partir de este momento,

1. Se envía una petición al oráculo.
2. La máquina finaliza en el estado-1 si el número escrito pertenece al conjunto oráculo y, en caso contrario, finaliza en el estado-0.

La siguiente ilustración muestra el funcionamiento del oráculo de una O-Machine:

Archivo:Simulacion funcionamiento maquina oraculo.png

A partir de los conceptos introducidos anteriormente, intuitivamente podemos afirmar que una MTO puede resolver el problema de la parada. Para ello, basta con facilitarle el alfabeto correspondiente a dicho problema. Este tipo de máquinas nos permite descubrir si para una determinada entrada n, la máquina se va a detener o no:

• Si no se detiene entonces la salida de la Máquina con Oráculo debe ser cero.
• Si se detiene retornará el resultado pertinente.

El problema de la parada se suele utilizar en la teoría de la recursión, puesto que nos permite describir los diferentes niveles de computabilidad existentes. De esta manera si podemos computar un conjunto en una MTO con un determinado oráculo, que denotaremos por la letra H, entonces podemos decir que es computable en H o recursiva en H.

Podemos considerar una máquina de Turing como un caso particular de una O-Machine. Para ello basta con imaginar una máquina de Turing con un oráculo vacío. Por tanto, este tipo de máquinas incrementan, de manera obvia, el poder computacional de una máquina de Turing clásica. Además, las MTO’s permiten computar todas las funciones recursivamente enumerables.

Una de las principales características de las Máquinas con Oráculo es que son capaces de computar una determinada función definida en el dominio de los números naturales. Sin embargo, no es posible encontrar una MTO que pueda procesar todas las funciones definidas en el dominio de los números naturales.

Esta paradoja se debe a que una Máquina Oráculo está formada por una Máquina de Turing clásica (es decir, una máquina de Turing formada por una serie tanto de transiciones finitas como de estados) y un oráculo (es decir, un conjunto, posiblemente, infinito de números). Esto nos permite trivializar la computación que ha sido generalizada, es decir, si pudiéramos elegir el oráculo en función de la definición de la función, entonces podríamos usar el oráculo para realizar búsquedas infinitas de símbolos.

A pesar de esta limitación, la noción de O-Machine resulta interesante y presenta unos fundamentos sólidos, puesto que nos permite resolver funciones utilizando para ello un oráculo determinado.

Máquinas de Turing Probabilísticas (MTP)

Las máquinas de Turing probabilísticas se utilizan, en la teoría de la complejidad computacional, principalmente para detallar las diferentes clases de complejidad existentes.

Se trata de máquinas no deterministas que toman decisiones basándose también en el azar. De manera informal, podemos definir una Máquina de Turing Probabilística (MTP) como una máquina en el que las decisiones se toman en base a una determinada probabilidad. Por simplicidad, podemos asumir que en, cada paso, la máquina tiene únicamente dos estados a los cuales se les asocia una probabilidad de ½. Este hecho, implica que al computar un problema de tamaño k obtenemos una probabilidad de 2-k (Herken, 1994).

Es decir, cada transacción tiene asociada la misma probabilidad, tal como se muestra en la siguiente figura:

Archivo:Maquinas probabilisticas.png

Podemos observar como cada posible estado tiene asociado una probabilidad. Además, la suma de estas probabilidades siempre debe sumar uno.

Cabe destacar que las MTP’s nos permiten resolver rápidamente problemas que en una máquina de Turing tradicional tardarían mucho tiempo en resolverse. Sin embargo, debemos resaltar que una MTP no aumenta el tamaño de las clases de las funciones que se pueden computar.

Asimismo, una MTP puede simular el funcionamiento de una Máquina de Turing para lo cual tendrá que simular, uno a uno, todos los posibles caminos correspondientes a los diferentes valores que se pueden obtener (Giuliano Benenti, 2004; Gill, 1974).

Leew, Moore, Shannon y Shapirio propusieron el primer modelo de MTP en 1955; en seguida, empezaron a surgir otros trabajos como el de Rabin en 1963 o el de Gill en 1974.

También podemos definir las Máquinas de Turing Probabilísticas como máquinas deterministas. Para ello deberemos añadir la instrucción write, de tal forma que el valor de la escritura quede distribuido, de manera uniforme, en el alfabeto que reconoce la máquina.

Como consecuencia de este hecho, una MTP puede proporcionarnos un resultado estocástico, es decir, dado un programa para la máquina, al que le asociamos una determinada entrada, puede ocurrir que el programa se ejecute en diferentes tiempos o, incluso, que no llegue a parar; y aunque parezca increíble, puede que durante una ejecución acepte una determinada entrada y no la admita durante la siguiente.

Por tanto, podemos concluir que podemos definir de diferentes formas la entrada a una MTP. Las clases de complejidad que incluyen RP, Co-RP, BPP y ZPP hacen referencia a dichas formas. Además, como es necesario restringir la máquina a usar tiempo logarítmico (en vez de polinómico que es lo habitual), es necesario definir una serie de clases análogas llamadas RL, Co-RL, BPL y ZPL. Si incluimos ambas restricciones obtendremos las clases RLP, Co-RLP, BPLP y ZPLP.

Es importante destacar que el modelo de cálculo que utilizan los computadores cuánticos es substancialmente probabilístico.

Esta es una forma de definir una MTP. Sin embargo, otros autores proponen otras definiciones.

Por ejemplo, Song Yan (Yan, 2002) define una MTP como una MT no determinista que contiene una serie de estados especiales llamados “coin-tossing states”. Para cada uno de estos estados se determinan dos estados posibles. Sin embargo, este concepto no resulta muy diferente de la definición que hemos utilizado anteriormente.

Giuliano Beneti define una máquina similar a la que utiliza Yan donde cada posibilidad tiene asociada una probabilidad de ½, de tal forma que cada estado tiene una probabilidad P de ser elegido y 1-P de no ser escogido. Esta máquina resulta difícil de simular.

Ja Mika Hirvensalo (Hirvensalo, 2004) y Colin P. Williams (Williams y Clearwater 1999), consideran una version más genérica de la MTP donde a partir de cada uno de los estados por los que pasa la máquina podemos obtener una serie de estados a los que nos podemos desplazar cuya suma de las probabilidades asociadas es uno. Una vez más, esta concepción de MTP no es muy diferente de la que hemos comentado originalmente.

El juego de la vida

Otro sistema del mismo poder de computación que la máquina de Turing es el juego de la vida.

En 1970, Conway publicó un pasatiempo que se ha hecho famoso. El juego de la vida es un juego donde no existen jugadores. Está formado por una malla bidimensional donde se coloca la información: los bits. Originalmente, se trataban de células que podían estar vivas (1) o muertas (0), ya que en un principio tan sólo era un juego.

Archivo:Juego vida1.png

Se realizan una serie de transiciones en el que las células pasan de un estado a otro. Las acciones que pueden darse en la malla son:

En una celda vacía puede:

• Aparecer una nueva => nace una célula
• Siga la celda vacía => no ocurre nada

En una celda ocupada:

• Desaparece la célula => muere
• Permance => sobrevive

El funcionamiento de este juego tiene tres puntos claves:

• un estado inicial (la colocación de las células al comienzo)
• unas reglas, que ahora veremos
• un estado final (si para)

En esta máquina las reglas que dominan los nacimientos y muertes no están determinados por un 'programa' externo ni por un algoritmo que se guarde independientemente de los datos. El comportamiento está implícito en la colocación de las células:

• Una célula nace si tiene 'exactamente' tres vecinas
• Una céluda muere si tiene menos de dos vecinas (de 'soledad')
• Una céluda muere si tiene más de tres vecinas (de 'superpoblación')

Que se puede codificar como 23/3 (Vecinas para sobrevivir/Vecinas para nacer). Existen variantes posteriores que modifican estos parámetros con la intención de que la máquina simule o no determinados comportamientos. Existe un conjunto de parámetros, por ejemplo, que hace que la máquina pueda contener patrones que se replican.

Pero volvamos a lo importante. Es una máquina teórica con el poder de computación de la máquina de Turing. A pesar de ello, no debemos expresar el problema como un autómata finito. Debemos expresarlo como una 'población inicial'. No se sabe si esto se acerca más o no al pensamiento humano o si podría considerarse un avance en la inteligencia artificial, pues lo único medianamente claro es la asunción de que la Tesis de Church-Turing sea cierta. Hasta que no se demostrara formalmente tal extremo (y parece complicado) será difícil establecer cuál es el mecanismo exacto para trasladar un pensamiento sobre una resolución (un algorítmo en un procesador especial: la mente) a su homólogo en una máquina teórica.

No debería ni tiene a priori que entenderse que este proceso sea más fácil de llevar a cabo sobre una Máquina de Turing, una máquina URM, o un juego de la vida. Arquitecturas de computadores (como la máquina de Von Neumann) en las que se apoyan paradigmas de muy alto nivel son abstracciones a la especificación formal de algoritmos cuya facilidad de uso no se ha comparado nunca con la que tuvieran posibles arquitecturas y paradigmas sobre el juego de la vida.

El mero hecho de que la capacidad intelectual humana esté materialmente presente en el funcionamiento de millones de neuronas de funcionamiento similar pero independiente y paralelo puede hacer pensar que esta aproximación sea más natural. De hecho, el mismo nombre tiene la palabra «vida», en alusión al espectáculo de ver evolucionar el juego, en el que parece verse una población evolucionar.

Entonces: la tesis de Church-Turing acercaría la equivalencia entre el poder computacional de esta máquina de la vida (el mismo que el de una MT) y el poder computacional humano. La propia concepción del juego asemejaría el funcionamiento de la máquina al del cerebro humano a primera vista más que la Máquina de Turing. ¿No estaremos perdiendo la oportunidad de atacar muchos problemas por otras vías?

Esperando que los avances por ese sentido llegaran, tendríamos que conformarnos con lo que actualmente aporta el juego de la vida. El estado inicial es el 'programa' que queremos que el juego de la vida ejecute. Se pueden construir patrones sobre esta malla: existen numerosos y documentados que generan sucesiones de números primos, puertas lógicas, sumadores, contadores,...

Como siempre, lo más divertido son los bucles infinitos, los patrones que no dejan de crecer o no se estabilizan. Probablemente lo más interesante, es si la concepción de que los datos evolucionan según su disposición y unas reglas simples en vez de según únicamente reglas complicadas puede ser útil para:

• estudios sociológicos
• estudios económicos
• cambios en el paradigma de programación
• replanteamiento de problemas hasta ahora sin solución conocida...
• o para muchos, un simple entretenimiento

Este applet en java permite ver una simulación del juego.

Referencias

1. http://cala.unex.es/cala/epistemowikia/index.php/Tesis de Church-Turing/La tesis de Church-Turing
2. http://www.dc.fi.udc.es/~grana/TALF/computabilidad.pdf
3. http://www.monografias.com/trabajos6/coriz/coriz.shtml
4. Turing y el computador (Marzo-2006)
5. La Informática como Ciencia Teórica (Marzo-2006)
6. La Tesis de Church Turing (Marzo-2006)
7. http://www.alu.us.es/s/sjromcas/documentos/c3.pdf(Marzo-2006)
8. Alonzo Church (Marzo-2006)
9. http://juanfc.lcc.uma.es/EDU/EP/trabajos/T205.Problemas%20no%20algoritmizables.pdf (Marzo-2006)
10. Máquinas Cuánticas (Marzo-2006)
11. Notas Filosóficas (Mayo-2006)
12. Zuse-Fredkin (Mayo-2006)
13. Máquinas Probabilísticas (Junio-2006)
14. http://www.faq-mac.com/mt/archives/014196.php (Junio-2006)
15. http://decsai.ugr.es/~castro/MCII/node3.html (Junio-2006)
16. http://www.kriptopolis.org/node/239 (Junio-2006)
17. wikipedia (Junio-2006)
18. http://www.cai.org.ar/revista/goedel.htm (Junio-2006)