¿Qué algoritmos sí podemos programar?

Sean algunos algoritmos

• Árbol generador de peso mínimo
• Regresiones
  
• Cadena común más larga
• Page Rank
• Runge-Kutta
• Recorrido de un grafo por profundidad (DFS)

Y los algoritmos fueron...

Sabemos que los algoritmos existen y que la implementación de algunos es sencilla de encontrar en internet. Intuitivamente sabemos que podemos pensar en un algoritmo y con suficiente abstracción podemos implementarlo en algún lenguaje de programación.

Un día quizá después de programar suficiente (o no) nacen las preguntas ¿qué algoritmo no puedo programar? ¿existe siquiera alguno que no pueda programar? Tengo este algoritmo ¿es posible programarlo?

Dentro de la computación teórica existe el concepto de computabilidad, éste se encarga de estudiar lo anterior.

Máquina de Turing (MT)

Es una propuesta de Alan Turing hecha en 1936 en su artículo "On computable numbers, with an application to the Entscheidungsproblem", es un modelo teórico de computación en el cual están basadas todas las computadoras de forma directa o indirecta.

Decimos que todas las computadoras están basadas en este modelo ya que, todos los modelos "razonables" de cómputo que se han encontrado hasta ahora son equivalentes a estas máquinas.

Esto quiere decir que si el modelo A es equivalente al modelo B, cualquier algoritmo implementado en A puede ser implementado en B y viceversa, dicho de otra forma el modelo A y el modelo B tienen la misma capacidad de cómputo.

En el diagrama anterior se muestran algunas equivalencias entre los modelos más conocidos, algunas implementaciones que se han hecho de los modelos y bajo qué modelo trabajan algunas aplicaciones conocidas. 

Visto de otro modo, también ilustra que cada programa implementado en cada lenguaje de programación es equivalente a una máquina de Turing. 

 

Algo que me parece interesante recalcar es que, aunque *de verdad* se ha intentado crear modelos de cómputo nuevos, no equivalentes a las MT y razonables, todos los encontrados hasta ahora han resultado ser equivalentes.

 

Lo anterior quizá pase porque de alguna forma nuestro pensamiento forma ideas que en esencia tienen la misma "estructura".

 

Quizá gracias a esa estructura es que nuestros algoritmos "pensados" son independientes a cualquier modelo de cómputo, es decir esa estructura nos permite implementarlos en cualquier lenguaje de programación que podamos pensar.

 

Y si un día crees que algún algoritmo tuyo es no implementable en X o Y lenguaje de programación, puede que seguramente sólo te falta creatividad de traducción (upsi, honey), ya que matemáticamente "debes" de poder implementarlo, porque la "equivalencia" existe.

 

Ahora, dado que todas nuestras computadoras, hasta ahora, son equivalentes a estas máquinas nos importa saber qué podemos y qué no podemos hacer con las MT ya que el modelo regirá todo lo que podamos programar o no.

Computabilidad

Decimos que algo es computable si existe una máquina de Turing que pueda realizar esa tarea.

 

Por ejemplo, sabemos que el algoritmo DFS es computable ya que existe una MT que puede ejecutarlo.

No computable

Luego, dada la definición anterior sabemos que algo no es computable si no existe una MT tal que pueda ejecutar al algoritmo.

 

 

Dentro del sistema formal de las matemáticas existen paradojas, estos son objetos inherenetemente contradictorios, que además sirvieron de inspiración para crear objetos no computables.

 

El problema del paro

Supongamos que se desea construir un programa que nos diga si dado un programa éste termina en un número finito de pasos cuando tiene una entrada particular.

 

 

Supongamos que existe un algoritmo llamado "termina", tal que recibe el código fuente de otro programa, digamos p y una entrada particular para p, llamémosle "in". El objetivo de "termina" es indicar si el programa p termina con la entrada particular "in"

Afirmación: 

El algoritmo anterior es un problema no computable, es decir no existe un programa en ningún lenguaje de programación que pueda resolverlo. Más formalmente no existe una MT que pueda resolver el problema del paro.

La demostración de la afirmación anterior es muy famosa, se hace por contradicción suponiendo que existe una máquina M que resuelve el problema y llegando a una paradoja.

Y como en esta casa somos gente civilizada y creemos en el principio de tercer excluido, creemos que la demostración es cierta.

Reducciones al problema del paro

Que sea imposible crear dicho programa nos habla sobre la existencia de problemas no computables, problemas que jamás podrán ser programados ni resueltos con lo que tenemos hasta ahora.

Una vez que conocemos un problema no computable, podemos hallar más problemas de este tipo demostrando que existen problemas que son equivalentes a él.

También podemos saber si un problema es computable o no a través de intentar reducirlo a un problema no computable.

Finalmente...

Toda vez que se dijo lo anterior, llegan a la luz las primeras limitaciones de las MT y las limitaciones con las que habremos de lidiar hasta que el conocimiento humano logre escalar un poco más.

Y no se trata de decir que las MT son insuficientes, se trata de decir que tal vez hay más, más que la humanidad todavía no conoce, no por nada el último premio nobel de Física, Roger Penrose, propone que la autoconsciencia, eso que nos permite entendernos como un ser y tener inteligencia, es un proceso no computable que se lleva acabo en el cerebro.

Entonces... Quizá sí, casi cualquier algoritmo en el que puedas pensar es programable en cualquier lenguaje de programación y en caso de que no, escribes un paper. 

 

 

 

 

Instagram (alerta nuevo post): https://www.instagram.com/mathandcss/

 

**El post debe entenderse como una explicación informal, parcial y que omite muchos detalles con fines informativos.**

Bibliografía

- A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Volume s2-42, Issue 1, 1937, Pages 230–265, https://doi.org/10.1112/plms/s2-42.1.230

- Roger Penrose. (1989). La nueva mente del emperador. Oxford University Press.

- J. C. Martin (2011), Introduction to Languages and the Theory of Computation, McGrawHill.

- C. Moore, S. Mertens (2011), The Nature of Computation, Oxford University Press.