Los programas While: bases para una teoría de la computabilidad

La Teoría de la Computabilidad estudia los límites teóricos de los sistemas computacionales. Uno de sus objetivos centrales consiste en clasificar los problemas en computables e incomputables, donde llamamos computable a un problema si admite solución informática. Para desarrollar estos resultados el modelo abstracto de computador más utilizado históricamente es la Máquina de Turing. Los estudiantes de Ingeniería Informática pueden percibir cierta lejanía entre el modelo teórico y los computadores reales por lo que es más adecuado utilizar un modelo más cercano a la programación como son los programas-while. Los Programas-while permiten resolver los mismos problemas que las máquinas de Turing, pero en cambio son mucho más sencillos de utilizar, sobre todo para personas que tienen una experiencia previa en la informática real, pues toman la forma de lenguaje imperativo clásico. Este texto además utiliza los Programas-while aprovechando sus ventajas y reformulándolos de manera que la computación quede definida en términos de manipulación de símbolos arbitrarios, algo que está mucho más en concordancia con la realidad informática. Además de explicar en detalle qué son los programas while y cómo se utilizan, se justifica por qué no es necesario incorporar otras instrucciones o tipos de datos.

Técnicas básicas de computabilidad

La Teoría de la Computabilidad es una disciplina encuadrada en la Informática Teórica que tiene como objetivo establecer los límites lógicos que presentan los sistemas informáticos a la hora de resolver problemas mediante el diseño de algoritmos. Frente a las disciplinas y técnicas que día a día amplían el campo de aplicabilidad práctica de los computadores, esta teoría establece una serie de barreras insalvables por ninguna tecnología digital de procesamiento de la información. Los métodos propios de la Teoría de la Computabilidad pueden ser extraordinariamente complejos, sin embargo, existe un núcleo de resultados fundamentales que son abordables mediante técnicas más asequibles, y que tienen la virtud de reflejar razonablemente el concepto central de indecidibilidad computacional. Este informe incluye una descripción de los conceptos y técnicas que configuran ese núcleo básico de la Teoría. Su propósito es dar cuenta de la primera batería de resultados relacionados con la incomputabilidad de algunos problemas conocidos y relevantes en Informática. Los resultados se presentan utilizando como estándar de programación los programas-while, incluyéndose una explicación detallada y sistemática de la técnica de Diagonalización, además de resultados tan importantes como la tesis de Church-Turing, la función universal o el problema de parada.