Introducción a la teoría de la computabilidad y la complejidad
Publicado: 2022-03-11¿Alguna vez te has preguntado: ¿Cuál es exactamente el dispositivo en el que estás leyendo este artículo? ¿Que es una computadora?
La ciencia computacional se remonta a mucho antes de que se imaginaran estos dispositivos informáticos modernos. En una industria donde las preguntas más frecuentes giran en torno a los lenguajes de programación, los marcos y las bibliotecas, a menudo damos por sentado los conceptos fundamentales que hacen que una computadora funcione.
Pero estas computadoras, que parecen poseer un potencial infinito, ¿tienen alguna limitación? ¿Hay problemas para los que no se pueden usar las computadoras?
En este artículo, abordaremos estas preguntas alejándonos de los detalles de los lenguajes de programación y las arquitecturas informáticas. Al comprender el poder y las limitaciones de las computadoras y los algoritmos, podemos mejorar nuestra forma de pensar y razonar mejor sobre 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
¿Que es una computadora? ¿Qué es un problema?
En la escuela, a menudo nos enseñan un modelo mental de problemas y funciones que es algo como esto:
Una función es un procedimiento que se 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 tales que el primer elemento de cada par es de un conjunto X (llamado dominio), el segundo elemento de cada par es de un conjunto Y (llamado codominio o rango), y cada elemento de el dominio está emparejado con exactamente un elemento del rango.
Eso fue todo un bocado. Pero, ¿qué significa eso exactamente?
Esta definición nos dice que una computadora es una máquina para computar funciones.
¿Por qué?
Porque las computadoras transforman entradas arbitrarias en alguna salida. En otras palabras, resuelven problemas. Las dos definiciones de funciones, la que nos es tan familiar y la formal, coinciden para muchos efectos prácticos.
Sin embargo, la definición matemática nos permite llegar a conclusiones interesantes como la existencia de funciones no computables (es decir, problemas irresolubles):
Porque no todas las funciones pueden describirse como un algoritmo.
Reglas del juego
Para ayudar a elaborar nuestros argumentos, imaginemos las computadoras como máquinas que toman alguna entrada, realizan una secuencia de operaciones y, después de un tiempo, dan alguna salida.
Llamaremos a la entrada el alfabeto de la máquina; es decir, un conjunto de cadenas de caracteres de algún conjunto finito. Por ejemplo, el alfabeto de la máquina puede ser binario (0 y 1) o puede ser el conjunto de caracteres ASCII. Cualquier secuencia finita de caracteres es una cadena, por ejemplo, "0110".
Además, representaremos la salida de una máquina como una decisión binaria de aceptación-rechazo, entregada una vez que la máquina (con suerte) termine su cálculo. Esta abstracción encaja bien con la definición matemática de funciones anterior.
Dados estos parámetros, es importante caracterizar un tipo más: una colección de cadenas. Tal vez nos interese el conjunto de cadenas que acepta alguna máquina, o tal vez estemos construyendo una máquina que acepte cadenas en un determinado conjunto y no en otros, o tal vez nos estemos preguntando si es posible diseñar una máquina que acepte todo en algunos conjunto particular y no otros.
En todos estos casos, un conjunto de cadenas 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 operarse con operadores como concatenación, unión, intersección y similares.
Un operador importante es el operador estrella de Kleene que también se usa con expresiones regulares. Esto puede pensarse como la unión de todos los poderes posibles del lenguaje. Por ejemplo, si nuestro lenguaje A es el conjunto de cadenas { '01', '1' }, entonces un miembro de A* es la cadena '0101111'.
contabilidad
La última pieza del rompecabezas antes de probar nuestra afirmación de que no todas las funciones son computables es el concepto de contabilidad. Intuitivamente, nuestra prueba mostrará que hay más idiomas; es decir, más problemas que programas posibles para resolverlos. Esto funciona porque la cuestión de si una cadena 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 incontablemente infinito mientras que el conjunto de idiomas sobre un alfabeto es incontablemente infinito.
En este punto, puede estar pensando: “El infinito es una idea bastante extraña en sí misma; ¡ahora tengo que lidiar con dos de ellos!”
Bueno, no es tan malo. Un conjunto numerable infinito es aquel que se puede enumerar. Es posible decir que este es el primer elemento, este es el segundo elemento, y así sucesivamente, eventualmente asignando un número a cada elemento del conjunto. Tome 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.
Contablemente muchos programas
Primero, queremos mostrar que el conjunto de programas de computadora es contable. Para nuestros propósitos, hacemos esto observando que el conjunto de todas las cadenas sobre un alfabeto finito es numerable. Esto funciona porque los programas de computadora son cadenas finitas en sí mismos.
La prueba es sencilla, y no cubrimos los detalles aquí. La conclusión clave es que existen tantos programas de computadora como, digamos, números naturales.
Reiterar:
El conjunto de todas las cadenas sobre cualquier alfabeto (p. ej., el conjunto de todos los programas de computadora) es contable.
Innumerables idiomas
Dada esta conclusión, ¿qué pasa con los subconjuntos de estas cadenas? Preguntado de otra manera, ¿qué pasa con el conjunto de todos los idiomas? Resulta que este conjunto es incontable.
El conjunto de todas las lenguas sobre cualquier alfabeto es incontable.
Una vez más, no cubrimos la prueba aquí.
Consecuencias
Aunque pueden no ser evidentes de inmediato, las consecuencias de la incontabilidad de los lenguajes y la contabilidad del conjunto de todos los programas de computadora 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 que representan, digamos, programas JavaScript, es 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 JavaScript es contable.
Además, consideremos que para cualquier lenguaje 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 estas funciones son distintas. Como hay una correspondencia 1:1 con el conjunto de todos los lenguajes y porque el conjunto de todos los lenguajes es incontable, tenemos que el conjunto de todas esas funciones es incontable.
Aquí está el punto profundo:
Dado que el conjunto de todos los programas válidos es contable pero el conjunto de funciones no lo es, debe haber algunas funciones para las que simplemente no podemos escribir programas.
Todavía no sabemos cómo son estas funciones o problemas, pero sabemos que existen. Esta es una lección de humildad, porque hay algunos problemas para los que no hay solución. Consideramos que las computadoras son extremadamente poderosas y capaces, pero algunas cosas están incluso fuera de su alcance.
Ahora la pregunta es: "¿Cómo son estos problemas?" Antes de continuar describiendo tales problemas, primero debemos modelar el cálculo 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 completamente nuestra noción de computabilidad.
La entrada a la máquina es una cinta en la que se ha escrito la entrada. Usando un cabezal de lectura/escritura, la máquina convierte la entrada en salida a través de una serie de pasos. En cada paso, se toma una decisión sobre si y qué escribir en la cinta y si moverla hacia la derecha o hacia la izquierda. Esta decisión se basa exactamente en dos cosas:
El símbolo actual debajo de la cabeza, y
El estado interno de la máquina, que también se actualiza a medida que se escribe el símbolo
Eso es todo.
universalidad
En 1926, Alan Turing no solo desarrolló la máquina de Turing, sino que también tuvo una serie de otras ideas importantes sobre la naturaleza de la computación cuando escribió su famoso artículo, "Sobre los números computables". Se dio cuenta de que un programa de computadora en sí mismo podría considerarse entrada a una computadora. Con este punto de vista, tuvo la hermosa idea de que una máquina de Turing podría simular o ejecutar esa entrada.
Si bien hoy en día damos por sentadas estas ideas, en la época de Turing, la idea de una máquina universal de este tipo fue el mayor avance que permitió a Turing desarrollar problemas irresolubles.
Tesis de Church-Turing
Antes de continuar, examinemos un punto importante: sabemos que la máquina de Turing es un modelo de computación, pero ¿es lo suficientemente general? Para responder a esta pregunta, recurrimos a la tesis de Church-Turing, que da crédito a la siguiente afirmación:
Todo lo computable es computable por una máquina de Turing.
Mientras Turing desarrolló la máquina de Turing como modelo de computación, Alonzo Church también desarrolló un modelo de computación conocido como cálculo lambda. Estos modelos son poderosos, porque ambos describen la computación y lo hacen de una manera igual a cualquiera de las computadoras de hoy o cualquier computadora de todos los tiempos. Esto significa que podemos usar una máquina de Turing para describir los problemas irresolubles que buscamos, sabiendo que nuestros hallazgos se aplicarían a todas las computadoras posibles del pasado, el presente y más allá.
Reconocimiento y Decidibilidad
Tenemos que cubrir un poco más de fondo antes de describir concretamente un problema irresoluble, a saber, los conceptos de reconocedores de lenguaje y decisores de lenguaje.
Un idioma es reconocible si hay una máquina de Turing que lo reconoce.
y
Un lenguaje es decidible si hay una máquina de Turing que lo decide.
Para reconocer un idioma, una máquina de Turing debe aceptar todas las cadenas del idioma y no debe aceptar nada que no esté en el idioma. Puede rechazar o hacer un bucle en dichas cadenas. Para ser un decisor, una máquina de Turing siempre debe detenerse en su entrada, ya sea aceptando o rechazando.
Aquí, la idea de detenerse en la entrada es fundamental. De hecho, vemos que los decisores son más poderosos que los reconocedores. Además, un problema es solucionable, o dicho de otro modo, una función es decidible sólo si existe una máquina de Turing que decida el lenguaje descrito por la función.
indecidibilidad
Si alguna vez ha escrito un programa de computadora, seguramente debe conocer la sensación de sentarse allí y ver cómo la computadora hace girar sus ruedas cuando se ejecuta el programa. No sabe si el programa está tardando demasiado o si hay algún error en el código que provoca un bucle infinito. Es posible que incluso se haya preguntado por qué el compilador no verifica el código para ver si se detendría o se repetiría para siempre cuando se ejecuta.
El compilador no tiene tal verificación porque simplemente no se puede hacer. No es que los ingenieros compiladores no sean lo suficientemente inteligentes o carezcan de recursos; es simplemente imposible verificar un programa de computadora arbitrario para determinar si se detiene.
Podemos probar esto usando la máquina de Turing. Las máquinas de Turing se pueden describir como cadenas, por lo que hay un número contable de ellas. Supongamos que M 1 , M 2 , etc. forman el conjunto de todas las máquinas de Turing. Definamos la siguiente función:
Aquí, <M> es la sintaxis para "codificación de cadena de M", y esta función representa el problema de generar 1 si M i se detiene al aceptar M j como entrada y generar 0 de lo contrario. Tenga en cuenta que M i debe detenerse (es decir, ser un decisor). Esto es necesario ya que deseamos describir una función indecidible (es decir, un problema irresoluble).
Ahora, definamos también un lenguaje L que consiste en codificaciones de cadenas de máquinas de Turing que NO aceptan sus propias descripciones:
Por ejemplo, alguna máquina M 1 puede generar 0 en la entrada <M 1 > mientras que otra máquina M 2 puede generar 1 en la entrada <M 2 >. Para probar que este lenguaje es indecidible, preguntamos qué hace M L , la máquina que decide el lenguaje L, cuando se le da su propia descripción <M L > como entrada. Hay dos posibilidades:
M L acepta <M L >
o
M L rechaza <M L >
Si M L acepta su propia codificación, eso significa que <M L > no está en el idioma L; sin embargo, si ese fuera el caso, entonces M L no debería haber aceptado su codificación en primer lugar. Por otro lado, si M L no acepta su propia codificación, entonces <M L > está en el idioma L, por lo que M L debería haber aceptado su codificación de cadena.
En ambos casos, tenemos una paradoja, o en términos matemáticos, una contradicción, demostrando que el lenguaje L es indecidible; por lo tanto, hemos descrito nuestro primer problema irresoluble.
Problema de detención
Si bien el problema que acabamos de describir puede no parecer relevante, se puede reducir a problemas irresolubles adicionales de importancia práctica, sobre todo el problema de detención:
El lenguaje de las codificaciones de las máquinas de Turing que se detienen en la cadena vacía.
El problema de la detención se aplica a la pregunta de por qué los compiladores no pueden detectar bucles infinitos anteriores. Si no podemos determinar si un programa termina en la cadena vacía, ¿cómo podríamos determinar si su ejecución daría como resultado un ciclo infinito?
En este punto, puede parecer que simplemente agitamos nuestras manos para llegar a una conclusión simple; sin embargo, en realidad nos dimos cuenta de que ninguna máquina de Turing puede decir si un programa de computadora se detendrá o permanecerá en un bucle para siempre. Este es un problema importante con aplicaciones prácticas, y no se puede resolver en una máquina de Turing o cualquier otro tipo de computadora. Un iPhone no puede resolver este problema. Un escritorio con muchos núcleos no puede resolver este problema. La nube no puede resolver este problema. Incluso si alguien inventara una computadora cuántica, aún no podría resolver el problema de la detención.
Resumen
En nuestro examen de la teoría de la computabilidad, hemos visto cómo hay muchas funciones que no son computables en ningún sentido ordinario de la palabra mediante un argumento de conteo. Definimos con precisión lo que entendemos por computación, remontándonos a la inspiración de Turing a partir de su propia experiencia con lápiz y papel para formalizar la máquina de Turing. Hemos visto cómo este modelo puede calcular cualquier cosa que pueda hacer cualquier computadora hoy o prevista para el mañana, y nos dimos cuenta de una clase de problemas que no son computables en absoluto.
Aún así, la computabilidad tiene un inconveniente. El hecho de que podamos resolver un problema no significa que podamos resolverlo rápidamente. Después de todo, ¿de qué sirve una computadora si su computación no va a terminar antes de que el sol se convierta en una nova en decenas de millones de años en el futuro?
Dejando atrás las funciones computables y los lenguajes, ahora discutimos la complejidad de la computación, examinando la computación eficiente y el famoso problema P vs. NP.
Complejidad
Lento vs rápido
Los científicos informáticos reconocen una variedad de clases de problemas, y dos clases que nos interesan incluyen problemas que las computadoras pueden resolver rápida o eficientemente conocidos como P y problemas cuyas soluciones pueden verificarse rápidamente pero no pueden obtenerse rápidamente conocidos como NP .
Por ejemplo, suponga que usted es responsable de desarrollar algoritmos para un servicio de citas en línea y alguien plantea la pregunta: "¿Todos pueden tener una cita?" La respuesta se reduce a emparejar individuos compatibles de modo que todos estén emparejados. Resulta que hay algoritmos eficientes para resolver este problema. Este problema está en el conjunto P .
Bueno, ¿y si quisiéramos identificar la camarilla más grande entre nuestros usuarios? Por camarilla, nos referimos a la red más grande de individuos que son todos compatibles entre sí. Cuando el número de usuarios es bajo, este problema se puede resolver rápidamente. Podemos identificar fácilmente, digamos, una camarilla con 3 usuarios. Sin embargo, a medida que comenzamos a buscar camarillas más grandes, el problema se vuelve cada vez más difícil de resolver. Este problema está en el conjunto NP .
Definiciones formales
P es el conjunto de problemas que son resolubles en tiempo polinomial. Es decir, el número de pasos computacionales está acotado por una función polinomial con respecto al tamaño del problema. Sabemos que el mensaje "¿Todos pueden tener una cita?" La pregunta, también conocida como problema de coincidencia bipartita, está en P .
NP es el conjunto de problemas que son verificables en tiempo polinomial. Esto incluye todos los problemas en P, por supuesto; sin embargo, no sabemos si esta contención es estricta. Conocemos problemas que son eficientemente verificables pero no eficientemente solucionables, pero no sabemos si el problema es realmente intratable. El problema de la camarilla es uno de esos problemas. Sabemos que podemos verificar la solución de manera eficiente, pero no sabemos con certeza si podemos resolver el problema de manera eficiente.
Por último, NP-completo es el conjunto de problemas que son los problemas más difíciles en NP . Se les conoce como los más difíciles porque cualquier problema en NP puede transformarse eficientemente en NPC . Como resultado, si alguien identificara una solución eficiente a un problema en NPC , entonces toda la clase de NP sería absorbida por P. El problema de la camarilla también está en NPC .
Así, llegamos al problema de P vs. NP . Muchos informáticos y matemáticos creen firmemente que P y NP no son iguales. Si lo fueran, las implicaciones serían más que profundas. Gran parte de la infraestructura digital actual se basa en el hecho de que hay problemas en NP que no están en P . Si ese no fuera el caso, entonces los métodos criptográficos, por ejemplo, colapsarían de la noche a la mañana, permitiendo que una persona que posee una solución eficiente para un problema de NPC subvierta incluso los protocolos de seguridad más estrictos.
Sutilezas de Trazabilidad
Para los novatos en informática, la diferencia entre los problemas de emparejamiento y camarilla puede no parecer gran cosa. De hecho, la diferencia entre un problema en P y un problema en NP puede ser muy sutil. Ser capaz de notar la diferencia es importante para cualquiera que diseñe algoritmos en el mundo real.
Considere el problema del camino más corto. Dadas dos ubicaciones, el objetivo es identificar el camino más corto entre ellas. Un iPhone calcula esto en cuestión de milisegundos. Este es un problema tratable computacionalmente.
Por otro lado, considere el problema del viajante de comercio, donde el objetivo es visitar un subconjunto de posibles destinos que terminan en el origen mientras viaja la menor distancia posible. Este problema es similar al problema del camino más corto pero es NP-completo; también explica por qué la logística de la cadena de suministro es una industria de miles de millones de dólares.
De hecho, podemos ser aún más sutiles. En lugar de preguntar por el camino más corto (P), podemos preguntar por el camino más largo sin ciclos. Resulta que el problema de la ruta más larga también es NP-completo.
Hay muchos más ejemplos de esta distinción sutil, incluida la identificación de cubiertas de vértices en gráficos bipartitos frente a gráficos generales o la satisfacción de fórmulas booleanas con dos frente a tres literales por cláusula. El punto es que no es inmediatamente obvio si un problema está en P o NP, y es por eso que el análisis del tiempo de ejecución es una habilidad crítica. Si el algoritmo que se debe diseñar es para un problema en P, entonces sabemos que hay una solución eficiente. Si, por otro lado, el problema está en NP, entonces tenemos un caso sólido para argumentar en contra de buscar una solución, porque el algoritmo, en general, simplemente tardaría demasiado en resolver el problema.
Resumen
En este examen de complejidad, definimos las clases de problemas P y NP. P representa informalmente problemas que pueden ser resueltos de manera eficiente por una computadora, mientras que NP representa aquellos que son verificables de manera eficiente.
Nadie ha podido demostrar que P no es igual a NP. Si estas dos clases de problemas son equivalentes, se conoce como el problema P vs. NP, y es el problema abierto más importante en la informática teórica actual, si no en todas las matemáticas. De hecho, en el año 2000, el Clay Math Institute nombró el problema P vs NP como una de las siete preguntas abiertas más importantes en matemáticas y ofreció una recompensa de un millón de dólares por una prueba que determine la solución a este problema.
Conclusión
En este artículo, profundizamos 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 conclusiones profundas que vale la pena recordar:
Hay algunas cosas que simplemente no se pueden calcular, como el problema de la detención.
Hay algunas cosas que no se pueden calcular de manera eficiente, como los problemas en NPC.
Más importante que los detalles son las formas de pensar acerca de la computación y los 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 y verdaderas para determinar el mejor curso de acción.
Lecturas adicionales en el blog de ingeniería de Toptal:
- Cómo abordar la escritura de un intérprete desde cero