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

Abstract

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.