Una Introducción a la Teoría y Complejidad de la Computabilidad
Te has preguntado alguna vez: ¿Cuál es exactamente el dispositivo en el que estás leyendo este artículo? ¿Qué es una computadora? La ciencia de la computación se remonta a un tiempo mucho antes de que se pensara en estos modernos dispositivos informáticos. En una industria donde las preguntas más frecuentes giran en torno a los lenguajes de programación, marcos y bibliotecas, a menudo damos por sentado los conceptos fundamentales que hacen funcionar una computadora.
Pero estas computadoras, que parecen poseer un potencial infinito— ¿tienen alguna limitación? ¿Hay problemas que las computadoras no pueden resolver?
En este artículo, abordaremos estas preguntas alejándonos de los detalles de los lenguajes de programación y las arquitecturas de la computadora. Al comprender el poder y las limitaciones de las computadoras y los algoritmos, podemos mejorar la forma en que pensamos y razonar mejor sobre las diferentes estrategias.
La visión abstracta de la informática produce resultados que han resistido la prueba del tiempo, siendo tan valiosos para nosotros hoy como lo fueron cuando se desarrollaron inicialmente en la década de 1970.
Computabilidad
¿Qué es una computadora? ¿Qué es un problema?
En la escuela, a menudo se nos enseña un modelo mental de problemas y funciones que dice algo como esto:
_ Una función es un procedimiento que aplica a una entrada x para encontrar una salida f(x)._
Resulta que la definición matemática es diferente:
Una función es un conjunto de pares ordenados de modo que el primer elemento de cada par proviene de un conjunto X (llamado el dominio), el segundo elemento de cada par proviene de un conjunto Y (llamado co-dominio o rango) y cada elemento del dominio está emparejado con exactamente un elemento del rango.
Eso fue bastante. Pero, ¿qué significa eso exactamente?
Esta definición nos dice que una computadora es una máquina para funciones informáticas.
¿Por qué?
Porque las computadoras transforman la entrada arbitraria a alguna salida. En otras palabras, resuelven problemas. Las dos definiciones de funciones, la que conocemos muy bien y la formal, coinciden para muchos propósitos prácticos.
Sin embargo, la definición matemática nos permite llegar a conclusiones interesantes tales como la existencia de funciones no procesables (es decir, problemas sin solución):
Por qué no todas las funciones se pueden describir como un algoritmo.
Reglas del Juego
Para ayudar con nuestros argumentos, imaginemos a las computadoras como máquinas que tienen una entrada, desarrollan una secuencia de operaciones y después de un tiempo, dan una salida.
Vamos a llamar a la entrada alfabeto de la máquina, que es un set de secuencia de caracteres de algún conjunto finito. Por ejemplo, el alfabeto de la máquina puede ser binario (0s y 1s) o podría ser el juego de caracteres ASCII. Cualquier secuencia finita de caracteres es una cadena—por ejemplo “0110.”
Además, representaremos el resultado de una máquina como una decisión binaria de aceptación y rechazo que se entrega una vez que la máquina (con suerte) finaliza su cálculo. Esta abstracción se ajusta bien a la definición matemática de funciones anteriores.
Dados estos parámetros, es importante caracterizar un tipo más: una colección de cadenas de caracteres. Tal vez nos preocupamos por el conjunto de cadenas de caracteres que acepta una máquina, o tal vez estamos construyendo una máquina que acepta cadenas de caracteres en un determinado conjunto y no en otros, o tal vez estamos preguntando si es posible diseñar una máquina que acepte todo en algún conjunto particular y no en otros.
En todos estos casos, un conjunto de cadenas de caracteres se denomina lenguaje—por ejemplo, el conjunto de todas las cadenas binarias que representan números pares o el conjunto de cadenas que tienen un número par de caracteres. Resulta que los idiomas, como los números, pueden ser operados con los operadores como concatenación, unión, intersección y otros similares.
Un operador importante es el operador estrella Kleene que también se usa con expresiones regulares. Esto se puede considerar como la unión de todos los poderes posibles del lenguaje. Por ejemplo, si nuestro idioma A es el conjunto de cadenas de caracteres { ‘01’, ‘1’ }, entonces un miembro de A* es la cadena de caracteres ‘0101111’.
Contabilidad
La última pieza del rompecabezas antes de demostrar nuestra afirmación de que no todas las funciones son computables es el concepto de contabilización. Intuitivamente, nuestra prueba mostrará que hay más idiomas; es decir, más problemas que posibles programas para resolverlos. Esto funciona porque el tema de si una cadena de caracteres pertenece a un idioma (Sí/No) es en sí misma un problema.
Más precisamente, nuestra prueba afirma que el conjunto de posibles programas es infinitamente contable, mientras que el conjunto de idiomas sobre un alfabeto es infinitamente incontable.
En este punto, puedes estar pensando “La infinidad es una idea bastante extraña en sí misma, ¡ahora tengo que lidiar con dos de ellos!”
Bueno, no es tan malo. Un conjunto contablemente infinito es uno que se puede enumerar. Es posible decir: este es el primer elemento, este es el segundo elemento y así sucesivamente, eventualmente asignando un número a cada elemento del conjunto. Toma el conjunto de números pares, por ejemplo. Podemos decir que 2 es el primero, 4 el segundo, 6 el tercero y así sucesivamente. Tales conjuntos son contablemente infinitos o contables.
Sin embargo, con algunos conjuntos como los números reales, no importa cuán inteligente seas; simplemente no hay enumeración. Estos conjuntos son incontablemente infinitos o incontables.
Muchos Programas de Manera Contable
Primero queremos mostrar que el conjunto de programas de computadora es contable. Para nuestros propósitos, hacemos esto al observar que el conjunto de todas las cadenas de caracteres sobre un alfabeto finito es contable. Esto funciona porque los programas de computadora son cadenas de caracteres finitas.
La prueba es sencilla y no cubrimos los detalles aquí. El punto clave es que hay tantos programas de computadora como, por ejemplo, números naturales.
Para reiterar:
El conjunto de todas las cadenas de caracteres sobre cualquier alfabeto (Ej., Conjunto de todos los programas informáticos) es contable.
Incontablemente, Muchos Idiomas
Dada esta conclusión, ¿qué pasa con los subconjuntos de estas cadenas de caracteres? Preguntado de otra manera, ¿qué pasa con el conjunto de todos los idiomas? Resulta que este conjunto es incontable.
_El conjunto de todos los idiomas sobre cualquier alfabeto es incontable. _
Una vez más, no cubrimos la prueba aquí.
Consecuencias
Aunque pueden no ser inmediatamente aparentes, las consecuencias de la incontabilidad de los idiomas y la contabilización del conjunto de todos los programas informáticos son profundas.
¿Por qué?
Supongamos que A es el conjunto de caracteres ASCII; los caracteres ASCII son solo los necesarios para componer un programa de computadora. Podemos ver que el conjunto de cadenas de caracteres que representan, por ejemplo, los programas de JavaScript son un subconjunto de A* (aquí, * es el operador estrella de Kleene). La elección de JavaScript es arbitraria. Dado que este conjunto de programas es un subconjunto de un conjunto contable, tenemos que el conjunto de programas de JavaScript es contable.
Además, consideremos que para cualquier idioma L podemos definir alguna función f que evalúe a 1 si alguna cadena x está en L y 0 en caso contrario. Todas esas funciones son distintas. Debido a que existe una correspondencia 1:1 con el conjunto de todos los idiomas y porque el conjunto de todos los idiomas es incontable, tenemos que el conjunto de todas esas funciones es incontable.
Aquí está el punto en profundidad:
Como el conjunto de todos los programas válidos es contable pero el conjunto de funciones no lo es, entonces debe haber algunas funciones para las cuales simplemente no podemos escribir programas.
Todavía no sabemos cómo son estas funciones o problemas pero sabemos que existen. Ésta es una realización humillante porque hay algunos problemas por los cuales no hay solución. Consideramos que las computadoras son extremadamente poderosas y capaces sin embargo, algunas cosas están fuera de su alcance.
Ahora la pregunta es: “¿Cómo son estos problemas?” Antes de continuar describiendo estos problemas, primero debemos modelar la computación de forma generalizada.
Máquinas de Turing
Uno de los primeros modelos matemáticos de una computadora fue desarrollado por Alan Turing. Este modelo, llamado máquina de Turing, es un dispositivo extremadamente simple que captura por completo nuestra noción de computabilidad.
Conclusión
En este artículo nos adentramos en los ámbitos de la computabilidad y la complejidad, respondiendo grandes preguntas como “¿Qué es una computadora?”. Si bien los detalles pueden ser abrumadores, hay una serie de aprendizajes profundos que vale la pena recordar:
Hay algunas cosas que simplemente no se pueden calcular, como el problema de detención.
Hay algunas cosas que no se pueden calcular de manera eficiente, como los problemas en NPC.
Más importantes que los detalles son las formas de pensar sobre computación y problemas computacionales. En nuestra vida profesional e incluso en nuestro día a día, podemos encontrarnos con problemas nunca antes vistos y podemos usar herramientas y técnicas probadas para determinar el mejor curso de acción.
Artículo vía TopTal
Autor: Mehmet Bajin
