Maquinas de Turing

Abstract

Los conceptos de algoritmo y computador universal son definidos desde la lente de la informática teórica y en particular, a partir de las definiciones realizadas por Alan Mathison Turing, en su celebre articulo “On computable numbers, with an application to the Entscheidungsproblem” (Sobre números computables, con una aplicación al problema de la decisión). Para ello, nos situamos en el contexto histórico adecuado, ilustramos los conceptos tanto desde sus definiciones formales como informales y finalmente, describimos la solución obtenida por Turing al problema de la decisión.