PROBLEMAS MATEMÁTICOS

El problema de la parada o problema de la detención para máquinas de Turing consiste en lo siguiente: dada una Máquina de Turing ${\displaystyle M}$ y una palabra ${\displaystyle w}$, determinar si ${\displaystyle M}$ terminará en un número finito de pasos cuando es ejecutada usando ${\displaystyle w}$ como dato de entrada. Alan Turing, en su famoso artículo "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936), demostró que el problema de la parada de la Máquina de Turing es indecidible (no computable o no recursivo), en el sentido de que ninguna máquina de Turing lo puede resolver.

Relevancia en la práctica[editar]

Al ejecutar un programa, este puede terminar después de un número finito de pasos o puede no terminar nunca. En la práctica, este último caso se manifiesta como programas que se quedan "trabados" o que entran a un bucle infinito. Por esta razón sería de gran utilidad resolver la siguiente pregunta en la práctica:

Existe un programa P, tal que, dado un programa cualquiera q y unos datos de entrada x, muestre como salida 1 si q con entrada x termina en un número finito de pasos o muestre como salida 0 si q con x entra a un bucle infinito.

Conocer si existe el programa P es, en términos resumidos, el problema de la parada.

Sin embargo hay que hacer notar que la sabiduría popular acerca de este problema hace pensar que nunca es posible demostrar que un programa termina. Esto es falso.

Lo que se afirma es que no existe una manera automática computable de saber si todos los programas del mundo terminan. No se niega que exista la prueba para programas concretos. De hecho, la construcción de pruebas para programas concretos es un paso obligatorio para demostrar su correctitud.

El procedimiento para construir estas pruebas no es automático; sin embargo, existen heurísticas que facilitan encontrar las pruebas de los programas. El área de conocimiento que estudia la construcción sistemática de pruebas se denomina Análisis de Terminación.

La evaluación o ejecución del programa con las entradas sin embargo no constituye una prueba de que siempre termine, sino de que en las circunstancias de la ejecución, terminó.

Irresolubilidad del problema[editar]

La irresolubilidad del problema se puede mostrar de varias formas, pero en esencia todas equivalen a un argumento diagonal de Cantor. A continuación se muestra el argumento en términos modernos de programación:

Supongamos que este problema sí se puede resolver algoritmicamente; entonces hay un programa, que llamaremos Termina, que cada vez que se le suministra el código de un programa p y sus datos de entrada x, hace un número finito de operaciones y responde "True" cuando el programa termina o "False" cuando el programa nunca termina. En lenguaje Python:

def Termina(p, x):
    #Supongamos que aquí se encuentra un código maravilloso que soluciona el problema de la parada
    #Esta función regresa True si p(x) termina o False en otro caso

Bajo la suposición de que existe este programa, se puede usar como subrutina de otro programa más grande, al que llamaremos "Diagonal" (en referencia a la diagonal de Cantor). Este programa recibirá como dato de entrada el código de un programa cualquiera w, y usará el programa Termina para decidir si el programa w termina cuando se le suministra ella misma como entrada (no hay nada de raro en esto, pues en la práctica hay programas como los compiladores se pueden suministrarse a sí mismos como dato de entrada). A continuación, Diagonal hace lo opuesto: Si w termina entonces Diagonal entra en un ciclo infinito y si w entra en un ciclo infinito entonces Diagonal termina. En lenguaje Python:

def Diagonal(w):
    if Termina(w, w):
        while True: pass #Esta instrucción es un bucle infinito

Resumiendo, el programa Diagonal está diseñado para tener la siguiente propiedad (entiéndase la flecha como "siempre y cuando"):

${\displaystyle {\it {{Diagonal}(w){\text{ termina}}\iff w(w){\text{ nunca termina}}}}}$

Como w puede ser el código de cualquier programa, particularmente puede ser el del mismo Diagonal:

def Diagonal(Diagonal):
     if Termina(Diagonal, Diagonal):
         while True: pass

En este caso se tiene ${\displaystyle w=Diagonal}$, y por lo tanto

${\displaystyle {\it {{Diagonal}({\it {{Diagonal}){\text{ termina}}\iff {\it {{Diagonal}({\it {{Diagonal}){\text{ nunca termina}}}}}}}}}}}$

Es decir que bajo la suposición de que existe el algoritmo Termina se llega a la paradójica conclusión de que hay una instrucción que termina siempre y cuando no termine. Como esta conclusión es absurda, entonces no puede existir el algoritmo Termina; es decir que es imposible resolver el problema de la parada algoritmicamente.

Demostración por construcción de máquinas de Turing[editar]

Es más común encontrar en los libros de texto la demostración anterior en términos de máquinas de Turing como sigue:

Supongamos que el problema de la parada tiene solución. Es decir, supongamos que existe una máquina de Turing que es capaz de determinar si otra máquina de Turing parará (terminará) con una entrada determinada. Llamemos Termina a esta máquina. Esta máquina recibiría como entrada la cadena ${\displaystyle M,w}$, donde ${\displaystyle M}$ es la codificación de una máquina de Turing y ${\displaystyle w}$ es la codificación de la cadena que se le alimenta a ${\displaystyle M}$. La máquina ${\displaystyle Termina}$ terminará en un estado de aceptación si ${\displaystyle M}$ para ante la entrada ${\displaystyle w}$, y en otro caso terminará en un estado de rechazo, pero nunca entrará en un ciclo infinito.

Es posible crear una máquina Copia que al recibir una cadena cualquiera ${\displaystyle w}$ termine en un estado de aceptación con ${\displaystyle w,w}$ en su cinta. Ahora crearemos una máquina Diagonal que recibe de entrada una cadena ${\displaystyle w}$, que alegadamente será la codificación de una máquina de Turing ${\displaystyle M}$. Primero Diagonal utilizará la máquina Copiapara duplicar la cadena ${\displaystyle w}$, convirtiéndola en ${\displaystyle w,w}$. A continuación, Diagonal pasará este resultado a través de Termina para decidir si la máquina representada por ${\displaystyle w}$ para ante la cadena ${\displaystyle w}$ y realiza lo opuesto: Si Terminaacepta, entonces Diagonal entra en un bucle infinito (que consiste de un solo estado al que se regresa una y otra vez) y en otro caso, si Termina rechaza entonces Diagonal termina en estado de aceptación.

Resumiendo, la máquina Diagonal está diseñada para tener la siguiente propiedad:

Diagonal para ante la entrada ${\displaystyle w}$ ${\displaystyle \iff }$ la máquina codificada en ${\displaystyle w}$ no para ante la entrada ${\displaystyle w}$.

Por último, tomaremos la codificación de la máquina Diagonal, y la aplicaremos como entrada a la propia máquina Diagonal. Como ${\displaystyle w}$ es la codificación de Diagonal, de lo anterior se sigue que Diagonal para ante sí misma como entrada si y solo si Diagonal no para ante sí misma como entrada. Esta conclusión es paradójica, pero todas las máquinas que hemos usado en la demostración, exceptuando Termina, son construibles; por lo tanto la clave de la demostración se encuentra, por reducción al absurdo, en la supuesta existencia de la máquina Termina. Al ser imposible la existencia de tal máquina Termina, que resolvía el problema de la parada, el problema de la parada no puede ser solucionado por ninguna máquina de Turing.

El problema de los dos sobres, también conocido como paradoja del cambio, es un acertijo o paradoja lógico, filosófico y de probabilidad y matemáticas recreativas, de especial interés en teoría de la decisión y lainterpretación bayesiana de la probabilidad.

Una posible formulación del problema es la siguiente:

"Digamos que te dan dos sobres indistinguibles, cada uno de los cuales contiene una suma positiva de dinero. Un sobre contiene dos veces más que el otro. Puedes escoger un sobre y quedarte con cualquier cantidad que contenga. Escoges un sobre al azar, pero antes de abrirlo se te ofrece la posibilidad de tomar el otro sobre en su lugar."

Es posible argumentar que será ventajoso para ti cambiar los sobres, demostrando que el valor esperado de un cambio de sobres es mayor que la cantidad que tiene en tu sobre. Esto conduce al absurdo de que es beneficioso cambiar sobres indefinidamente.

Las razones para cambiar de sobres:

1. Sea A la cantidad que contiene mi sobre.
2. La probabilidad de que A sea el sobre con menos dinero es 1/2, y la de que sea el sobre con la cantidad mayor es también 1/2.
3. El otro sobre puede contener o bien 2A o bien A/2.
4. Si A es la cantidad menor entonces el otro sobre contiene 2A.
5. Si A es la cantidad mayor entonces el otro sobre contiene A/2.
6. Por lo tanto el otro sobre contiene 2A con probabilidad 1/2 y A/2 con probabilidad 1/2.
7. Por lo tanto el valor esperado de dinero en el otro sobre es
   
   ${\displaystyle {1 \over 2}2A+{1 \over 2}{A \over 2}={5 \over 4}A}$
   
8. Este valor es mayor que A, por lo tanto gano cambiando los sobres.
9. Después del cambio, puedo llamar B al contenido de mi sobre y razonar exactamente igual que antes.
10. Concluyo que lo más racional es cambiar de sobres una y otra vez.
11. Para ser racional, deberé entonces cambiar de sobres indefinidamente.
12. Dado que parece más racional limitarse a abrir un sobre, tengo una contradicción.

Explicación de la paradoja[editar]

A pesar de que en primera instancia parecería que el otro sobre es mejor siempre, se comete un error en la paradoja de los dos sobres al comparar A con un valor esperado ya que A es el valor efectivo del sobre y no el valor esperado de este, de hecho el valor esperado de los dos sobres es:

${\displaystyle {5 \over 4}A}$

 problema de Alhacén, aunque fue formulado en primer lugar por Tolomeo en el año 150 d.c.

Distintos planteamientos del problema[editar]

• Geométrico: Dados dos puntos cualesquiera del interior de un círculo situado en un plano, debe determinarse un punto de la circunferencia, de forma que los dos segmentos que lo unen a los dos puntos dados, formen ángulos iguales con la normal a la circunferencia en el punto buscado.
• Geométrico: Deducir un triángulo isósceles inscrito en una circunferencia, cuyos lados iguales pasan por dos puntos dados interiores a la circunferencia.
• Mecánico: Encontrar el punto en el borde de una mesa de billar circular hacia el que hay que lanzar una bola para alcanzar a la otra.
• Óptico: Su aplicación principal en óptica es la de solucionar el problema siguiente: "Dada una fuente de luz y un espejo esférico, encontrar el punto del espejo donde la luz se verá reflejada para el ojo de un observador dado". También es conocido como el problema de la determinación del "Punto brillante" de un espejo.
• Analíticamente, significa la resolución de una ecuación de cuarto grado.²​³​¹​

Ecuaciones del problema[editar]

Las ecuaciones involucradas son las siguientes:⁴​

• DATOS DEL PROBLEMA:

• Puntos por los que deben pasar los rayos de luz:

${\displaystyle P_{1}=(x_{1},y_{1})}$

${\displaystyle P_{2}=(x_{2},y_{2})}$

• Circunferencia de radio r, con centro en el origen:

${\displaystyle x^{2}+y^{2}=r^{2}}$

• Punto buscado de la circunferencia, solución del problema:

${\displaystyle A=(x,y)}$

• RESOLUCIÓN DEL PROBLEMA:

El punto A es la intersección de las dos curvas siguientes:

• Hipérbola:

${\displaystyle H(x^{2}-y^{2})-2Kxy+(x^{2}+y^{2})(hy-kx)=0}$

${\displaystyle (}$siendo${\displaystyle :\;H=x_{1}y_{2}+x_{2}y_{1}\ ;\ K=x_{1}x_{2}-y_{1}y_{2}\ ;\ h=x_{1}+x_{2}\ ;\ k=y_{1}+y_{2})}$

• Círculo:

${\displaystyle x^{2}+y^{2}=r^{2}}$

Quedan entonces determinadas las ecuaciones que permiten resolver el problema, buscando los valores donde se anula la última función con las condiciones siguientes:

${\displaystyle [1]\ -r\leq x\leq r}$

${\displaystyle [2]\ y=\pm {\sqrt {r^{2}-x^{2}}}}$

${\displaystyle [3]\ H(x^{2}-y^{2})-2Kxy+r^{2}(hy-kx)=0}$

La resolución numérica de cada caso concreto (para valores determinados de r, P₁ y P₂) puede encontrarse mediante algún procedimiento de aproximaciones sucesivas, tanteando con los valores de x comprendidos entre -r y r.

Sumas de potencias[editar]

Este problema llevó a Alhacén a deducir una fórmula para sumar cuartas potencias, donde anteriormente solo las fórmulas para la suma de cuadrados y de cubos habían sido planteadas. Su método puede ser fácilmente generalizado para encontrar la fórmula de la suma de cualquier potencia entera, a pesar de que no llegó a plantear la generalización de su fórmula (quizás porque solo necesitaba la cuarta potencia para calcular el volumen del paraboloide en el que estaba interesado). Utilizó su resultado de la suma de potencias enteras para calcular lo que actualmente se llamaría una integración, donde las fórmulas para las sumas de segundas y cuartas potencias le permitieron calcular el volumen de un paraboloide.⁵​

Influencia[editar]

Alhacén solucionó el problema utilizando secciones cónicas y una comprobación geométrica. Matemáticos posteriores como Christiaan Huygens, James Gregory, Guillaume de l'Hôpital, Isaac Barrow, y muchos otros, intentaron encontrar una solución algebraica al problema, utilizando varios métodos, incluyendo métodos analíticos de geometría y derivación por números complejos.⁶​ Una solución algebraica al problema fue finalmente encontrada en 1997 por el matemático de Oxford Peter M. Neumann.⁷​ Recientemente, los investigadores de los Mitsubishi Electric Research Labs (MERL) investigadores Amit Agrawal, Yuichi Taguchi y Srikumar Ramalingam solucionaron la extensión del problema de Alhazen al caso general de espejos rotacionales simétricos cuádricos, que incluyen los tipos hiperbólicos, parabólicos y elípticos.⁸​ Demostraron que el punto de reflexión del espejo puede ser determinado resolviendo una ecuación de octavo grado en el caso más general. Si la cámara (o el ojo del observador) se coloca en el eje del espejo, el grado de la ecuación se reduce a seis.⁹​ El problema de Alhazen también puede ser extendido a las refracciones a través de una bola esférica. Dada una fuente de luz y una esfera de índice de refracción conocido, el punto más cercano de la esfera desde el que la luz refractada alcanza el ojo del observador puede ser obtenido solucionando una ecuación de décimo grado.