¿Qué es un algoritmo?

A principios del siglo XX los matemáticos estaban fascinados por la pregunta: ¿Cuántas matemáticas podemos hacer? … no usando nuestros sentimientos o intuiciones, sino sólo reglas muy muy cuidadosamente, osea usando un algoritmo.

A final de toda esta cuestión y para que nuestra respuesta tenga algo de sentido tenemos que pensar, ¿Qué entendemos por un programa o algoritmo?

---

Alan Turing

Y aquí es donde Alan Turing entra en escena con su noción de una máquina de Turing.

Alan Turing es el hombre que debemos agradecer por un mundo libre de Nazis y lleno de computadoras.

En 1936, Alan Turing publicó un artículo titulado «Computables Numbers, with a Application to the Entscheidungs problem», en el que presentaba la noción de una máquina universal (más tarde llamada «máquina universal de Turing» y luego «máquina de Turing») capaz de computar cualquier cosa que sea computable. El concepto central de la computadora moderna se basó en el papel de Turing.

Deja que te lo explique de otra manera, el en su cabeza pensó en una maquina que pudiera calcular todo aquello que fuera calculable… sin crearla…Antes siquiera de que existiera la primera computadora moderna.

---

Máquinas de Turing

Como podemos leer, Alan es uno de los grandes padres de la computación, y realizo muchísimo trabajos en grandes áreas, así que por ahora nos centraremos en uno de ellos. Su documento «Computables Numbers, with a Application to the Entscheidungs problem»

Como parte de su prueba tenía que trabajar con la noción de cualquier algoritmo posible o cualquier máquina posible. Él tenía que llegar a una forma muy general de como los algoritmos o programas o máquinas trabajan.

Aquí es donde su noción de la máquina de Turing entra. La forma en que Turing describió a estas máquinas es algo como esto:

Tienes una manera de escribir información en forma codificada: Su manera era pensar en una cinta que sea lo largo que sea necesario, esta se divide en cuadrados y cada uno de los cuadrados hay un cero o uno  o podemos tener algunos espacios.

Ahora lo que hace nuestra máquina es que mira la cinta un cuadrado a la vez.

Así que se podría imaginado como una pequeña caja corriendo por encima de la cinta, quizás en las ruedas pequeñas, mirando.

Esta cuenta codifica nuestro problema solucionado (una vez que la máquina de Turing haya terminado) lo que una máquina de Turing hace es realmente sencillo:

Operación

En cualquier momento en el tiempo está en un estado particular y está mirando un cuadrado en la cinta, y tiene un libro de registro, un libro de programas. Y eso lo dice que hacer.

Forma A:

Si por ejemplo estás en el número de estado 23, Y está mirando un cero, entonces borrar el cero, lo cambia a uno, muévete un cuadrado a la derecha, y pasar al estado número 359.

O si estás en la número 359 y usted está mirando una deje ese uno como es, mueva un cuadrado a la izquierda y pasar al estado número veinte.

Son puras instrucciones sencillas.

Forma B de Entenderlo:

Este programa basicamente de dice a la máquina que operación hacer, toda máquina Turing debería tener un inicio, ese esta denotado por:

Y las operaciones o «instrucciones» más bien tienen esta sintaxis:

Básicamente dice:

Digito1 / Digito 2, Dirección

Ya sabemos que los Dígitos puedes ser: {1,0} y las direcciones: {L(izquierda) , R(derecha) y .(Quédate ahí)}

Así en lenguaje natural la instrucción se lee:

«Si Digito1 es tu dígito actual, continua leyendo, sino para, si continuas leyendo cambia tu estado actual por Digito2 y avanza en Dirección, finalmente estas en el estado q1.»

Si sigues esta idea puedes ver como la máquina va avanzando siguiendo el diagrama:

Esa qh significa Halt, que en español quiere decir «parado» es el paso en el que se dice que se terminaron de ejecutar todas las instrucciones y nuestra máquina a terminado su trabajo y se quedará ahí.

Lo que la máquina hace, es que comienza con un cierto patrón de unos y ceros. Esa sigue estas reglas un cuadrado a la vez, transformando esa cadena de unos y ceros en una cadena diferente de unos y ceros.

Y eventualmente ( y con suerte) la máquina se mueve en un estado de parada.

Está terminado, está hecho. Y lo que queda en la cinta es la respuesta a nuestro problema, codificados como unos y ceros. Eso es un simple proceso, pero resulta que es el esencia de la computación.

Lo que sea cualquier computadora puede hacer, podría en teoría ser hecho por ese sistema mirando a los unos y ceros en una cinta.

Así que por eso decimos que Turing al llegar con su idea de máquinas de Turing, en efecto, surgió un plan para los modernos ordenadores digitales.

Básicamente hacen lo que hacen las máquinas de Turing.

Y usamos esta idea para evaluar la fuerza de los modernos programas de computador. Cuando un programa de computadora puede hacer lo que una máquina de Turing puede hacer, lo llamamos «Turing completa». Y es la cima de la jerarquía de la fuerza del programa.

Así que el programa más fuerte que podemos obtener hace exactamente uno que haga lo que una máquina de Turing puede hacer. Nunca hemos encontrado una forma de calcular más cosas que las que podríamos hacer con una máquina de Turing.

---

Máquina Universal de Turing

De forma más abstracta podemos decir que una máquina de Turing es como una caja negra, de este estilo:

Así que para evitar tener que desarrollar una nueva máquina para cada operación (lo cual resultaría incontable) se desarrolló la «Máquina Universal de Turing»

Que tenía una entrada P que le diría como tenía que comportarse y esta máquina para el mundo exterior serviría exactamente igual que una máquina de Turing normal, si de esas que te encuentras todos los días.

---

El Problema de la Parada «The Halting Problem»

Hay también un problema muy famoso relacionado con el bueno de Turing y de como en la solución de ese problema, Alan Turing casi inadvertidamente inventó la computadora digital moderna.

Así que empezamos de nuevo al principio del Siglo XX, donde los matemáticos tenían planteado este problema:

En lógica estamos interesado en encontrar  la respuesta a la pregunta: «¿Estas premisas implican esta conclusión? 

Las premisas son los bits con los que comienzas, son los pedacitos que sabemos en el principio (osea los supuestos) y la conclusión es el a lo que quieres llegar.

Hay una prueba llamada Halting que nos diría si las premisas conducen a las conclusiones por medio de la lógica. Es decir ¿Hay una manera automática de averiguar si lo hacen o si no lo hacen? , así que ese es el problema, se llama el también el Problema de Decisión.

Los matemáticos querían saber hay una respuesta al problema de la decisión para la lógica de primer orden (Ese es el tipo de lógica que aprendes en Filosofía o matemáticas en la universidad).

Alan Turing fue uno de los primeros en descubrir que la lógica de primer orden no es decidiste, es decir puede probar automáticamente si las premisas llevan a la conclusión.

Para probar esto es realmente difícil (conceptualmente) porque tenemos que ser capaz de demostrar no hay ningún programa posible que pueda darnos la respuesta.
Pero, ¿cómo lo haces hacemos ¿Cómo se muestra algo de todos los programas posibles que puedan existir?

Turing surgió con una brillante solución, su idea es algo así:

Supongamos que tenemos un programa y vamos a dibujar como una caja negra, (una de las maquinas de Turing)

Esta máquina va a tomar unas premisas y conclusiones y te dice que las premisas llevan a la conclusión de manera automática, es decir resulte el problema de Halting.

Ahora aquí hay otra pregunta que podemos hacer, que es equivalente:

¿Alguna vez el programa terminará?

Veamos todos los posibles programas que existen y sólo pensemos en ellos como cajas negras y por el momento lo único que nos interesa saber es si algún día pararan de «correr».

No nos importa que respuesta nos den estos programas, simplemente saber si nos darán una respuesta.

Si no terminara nunca de «ejecutarse» el programa significa que quedo atrapado en un bucle infinito. Nunca sabríamos si va a termina hoy, mañana o nunca.

Lo asombroso resulta en que nuestro problema lógico: ¿Estas premisas implican esta conclusión? es muy similar a este Problema de Detención.

La parte inteligente de la prueba de Turing es que para mostrar que es imposible que existe una máquina, no importa lo compleja que sea que resuelva el problema de la Parada… Pero ¿Cómo lo hizo?

---

La solución de Turing

Supongamos que tenemos una máquina o un programa que soluciona el problema, no nos preocupemos de como lo hace, simplemente lo hace.

Esta máquina recibe dos entradas, un programa y un «entrada de programa» y nos regresa un «si» si en algún momento el programa P se detendrá dado la entrada I, y un «no» si… si no (obvio).

Usando H como base podemos crear esta nueva máquina en la que si el resultado es verdadero entonces haremos que se quede en un bucle para siempre y si la respuesta es no, entonces regresamos un «si parará».

La magia ocurre cuando alimentas a H+ con H+

Así que la pregunta que ahora estoy haciendo es que estoy haciendo es preguntarle a la máquina:  ¿H + se parará con la entrada H+?

Y aquí es donde todo va mal porque si H+ detiene recibimos una respuesta afirmativa, pero entonces inmediatamente entra en un bucle infinito, y por consiguiente no se detiene.

Por otro lado si recibimos un «no se detiene» de H entonces la máquina nos devuelve un «Si se detiene» y se detiene.

No es que hayas entendido mal, es que es una paradoja, no tiene sentido, pero lo que muestra es que empezamos suponiendo que podemos resolver el problema y hemos terminado con una paradoja, por lo tanto la suposición era mala.

Resulta que no hay máquina posible, ningún programa posible que resuelva el Problema de la Parada.