Teoría de la Computación : Lenguajes Formales, Autómatas y Complejidad / Glenn Brookshear

El concepto de proceso computacional, también llamado proceso algorítmico o algoritmo, es fundamental para la ciencia de la computación. Al ejecutar estos procesos, los computadores son capaces de resolver problemas; por el contrario, un computador no puede resolver un problema que no tenga una solución algorítmica. Así, cualquier limitación de las capacidades de los procesos computacionales es también una limitación de las capacidades de una máquina computadora. Este texto es una introducción al estudio de los procesos computacionales. Nuestro objetivo es explorar el alcance de estos procesos utilizando métodos matemáticos rigurosos, y al mismo tiempo relacionar los resultados teóricos con aspectos de interés práctico. Comenzaremos con un estudio teórico de 1 a s técnicas de reconocimiento de patrones que asociamos en lo general con los aspectos prácticos del procesamiento de lenguajes y en lo particular con la construcción de compiladores. Esto nos llevará a ciertos límites aparentes con respecto al poder de los procesos computacionales y luego a un estudio teórico de la computabilidad. Una vez más, no sólo veremos los aspectos teóricos; encontraremos que existen muchos problemas que teóricamente tienen una solución algorítmica, aun cuando no cuenten con soluciones algorítmicas prácticas. Para ser más precisos, muchos de los problemas que en teoría pueden resolverse con algoritmos requieren tal cantidad de recursos (en lo que se refiere a tiempo o espacio de almacenamiento) que, desde el punto de vista práctico, se debe considerar que aún no tienen solución. Por lo tanto, nuestro estudio concluirá con una exploración de los trabajos de investigación actuales encaminados a identificar aquellos problemas que tienen soluciones prácticas. Para motivar aún más nuestro estudio de la computabilidad, comparemos a un físico que resuelve problemas utilizando las leyes físicas descubiertas por Isaac Newton con un programador que resuelve problemas expresando sus soluciones en un lenguaje de programación. Existen varios problemas que el físico puede resolver dentro del marco newtoniano; sin embargo, también existen problemas para los cuales las leyes físicas de Newton son demasiado restrictivas y, para darles solución, el físico debe emplear las leyes más generales de la teoría de la relatividad de Einstein. La ciencia de la física incorpora la búsqueda de leyes más poderosas con las cuales explicar fenómenos físicos cada vez más complejos. No obstante, sin importar los principios fundamentales sobre los cuales se apoya su estudio, existirá un límite para las preguntas que pueden responder los físicos. Por ejemplo, si suponemos que la teoría de la gran explosión es verdadera, es poco probable que los físicos puedan explorar alguna vez la porción del universo que yace más allá de la distancia que ha viajado la luz desde la explosión. Como punto de comparación, existen varios problemas que el programa- dor de computadores puede resolver utilizando un lenguaje de programación determinado, pero este lenguaje quizá imponga limitaciones a los problemas que el programador puede resolver. ¿Es posible superar estas limitaciones desarrollando lenguajes de programación más poderosos? Además, como sucede con la teoría de la gran explosión, ¿existe algún punto en el cual la adición de características a un lenguaje de programación, o el cambio a otro lenguaje, no incremente el poder de solución de problemas del programador? Estas preguntas son parte medular de nuestro estudio.