Técnicas básicas de computabilidad

Abstract

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.