Problemas computables y no computables en TOC – Part 1

Problemas computables: está familiarizado con muchos problemas (o funciones) que son computables (o decidibles), lo que significa que existe algún algoritmo que calcula una respuesta (o salida) para cualquier instancia del problema (o para cualquier entrada a la función) en un número finito de pasos simples. Un ejemplo simple es la operación de incremento de enteros:

f(x) = x + 1 

Debería ser intuitivo que dado cualquier número entero x, podemos calcular x + 1 en un número finito de pasos. Dado que x es finito, puede representarse mediante una string finita de dígitos. Usando el método de suma (o algoritmo) que todos aprendimos en la escuela, podemos calcular claramente otra string de dígitos que representan el número entero equivalente a x + 1. Sin embargo, también hay problemas y funciones que no son computables (o indecidibles o no computables), lo que significa que no existe ningún algoritmo que pueda calcular una respuesta o salida para todas las entradas en un número finito de pasos simples. (Indecidible simplemente significa no computable en el contexto de un problema de decisión, cuya respuesta (o resultado) es «verdadero» o «falso»). 

Problemas no computables: un problema no computable es un problema para el cual no existe un algoritmo que pueda usarse para resolverlo. El ejemplo más famoso de no computabilidad (o indecidibilidad) es el problema de la detención . Dada una descripción de una máquina de Turingy su entrada inicial, determina si el programa, cuando se ejecuta en esta entrada, alguna vez se detiene (completa). La alternativa es que se ejecuta para siempre sin detenerse. El problema de la detención se trata de ver si una máquina alguna vez se detendrá cuando se le dé cierta entrada o si terminará de ejecutarse. Esta entrada en sí misma puede ser algo que se siga llamando a sí misma para siempre, lo que significa que hará que el programa se ejecute para siempre. Otro ejemplo de un problema no computable es: determinar si un programa de computadora se repite para siempre en alguna entrada. Puede reemplazar «programa de computadora» con «máquina o algoritmo de Turing» si conoce la máquina de Turing. 

Demostración de la computabilidad o no computabilidad –Podemos demostrar que un problema es computable describiendo un procedimiento y demostrando que el procedimiento siempre termina y siempre produce la respuesta correcta. Basta con proporcionar un argumento convincente de que tal procedimiento existe. No es necesario encontrar el procedimiento real (pero a menudo ayuda a que el argumento sea más convincente). Para mostrar que un problema no es computable, necesitamos demostrar que no existe ningún algoritmo que resuelva el problema. Dado que hay un número infinito de procedimientos posibles, no podemos enumerar todos los procedimientos posibles y mostrar por qué cada uno no resuelve el problema. En cambio, necesitamos construir un argumento que muestre que si existiera tal algoritmo, conduciría a una contradicción. El núcleo de nuestro argumento se basa en saber que el problema de la detención no es computable. Si se pudiera usar una solución a algún problema nuevo P para resolver el problema de la detención, entonces sabemos que P tampoco es computable. Es decir, no existe ningún algoritmo que pueda resolver P ya que si tal algoritmo existe, podría usarse para resolver también el problema de la detención, que ya sabemos que es imposible. La técnica de prueba en la que mostramos que una solución para algún problema P se puede usar para resolver un problema diferente Q se conoce comoreducción .Un problema Q es reducible a un problema P si una solución a P podría usarse para resolver Q. Esto significa que el problema Q no es más difícil que el problema P ya que una solución al problema Q conduce a una solución al problema P. 

Algunos ejemplos de problemas computables: estos son cuatro ejemplos simples del problema computable:

1. Cálculo del máximo común divisor de un par de enteros.
2. Cálculo del mínimo común múltiplo de un par de enteros.
3. Encontrar el camino más corto entre un par de Nodes en un gráfico finito.
4. Determinar si una fórmula proposicional es una tautología.

Algunos ejemplos de problemas computables: problema de entrada de estado. Considere el problema de determinar si una string ‘w’ se le da a alguna máquina de Turing ‘M’ entrará en algún estado ‘q’ (donde q pertenece a un conjunto de todos los estados en la máquina de Turing M y la string w no es igual a una cuerda vacía). ¿Es computable o no computable? 

Explicación: mostramos que el problema de entrada de estado no es computable al mostrar que es tan difícil como el problema de detención, que ya sabemos que no es computable. El problema de entrada de estado nos pregunta en una string dada w si comenzamos desde el estado inicial de la máquina de Turing, ¿llegará a un estado q? Ahora bien, este problema de entrada de estado se puede convertir en un problema de detención. El problema de detención es si nuestra máquina de Turing alguna vez se detiene, y el problema de entrada de estado pregunta lo mismo si esta máquina de Turing se detiene en algún estado q si le damos la string w como entrada a la máquina de Turing M. Entonces, el problema de entrada de estado no es computable como lo convertimos al problema de detención que ya sabemos que es un problema no computable. Entonces, de esta manera, podemos probar la no computabilidad.