Concept
vignette|Une représentation artistique d'une machine de Turing. Les machines de Turing sont un modèle de calcul. L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique. C'est une branche de la science informatique et la science formelle. Plus généralement, le terme est utilisé pour désigner des domaines ou sous-domaines de recherche centrés sur des vérités universelles (axiomes) en rapport avec l'informatique. L'informatique théorique se caractérise par une approche par nature plus mathématique et moins empirique de l'informatique et ses objectifs ne sont pas toujours directement reliés à des enjeux technologiques. De nombreuses disciplines peuvent être regroupées sous cette dénomination diffuse dont : la théorie de la calculabilité, l'algorithmique et la théorie de la complexité, la théorie de l'information, l'étude de la sémantique des langages de programmation, la logique mathématique, la théorie des automates et des langages formels. Dans cette section, nous donnons une histoire de l'informatique théorique en nous appuyant sur différentes sources : l'hommage à Maurice Nivat dans le bulletin de la SIF, l'histoire du CRIN, le livre Models of Computation de John E. Savage. vignette|Alan Turing à l'âge de 16 ans. Les logiciens Bertrand Russel, David Hilbert et George Boole furent des précurseurs de l'informatique théorique. Mais cette branche de l'informatique a surtout vu le jour à partir des travaux d'Alan Turing et Alonzo Church en 1936, qui ont introduit les modèles formels de calculs (les machines de Turing et le lambda calcul). Ils ont montré l'existence de machines universelles capables de simuler toutes les machines du même type, par exemple les machines de Turing universelles. En 1938, Claude Shannon montre que l'algèbre booléenne explique le comportement des circuits avec des relais électromécaniques. En 1945, John von Neumann introduit la notion d'architecture de von Neumann à la base des ordinateurs. En 1948, Claude Shannon publie A Mathematical Theory of Communication, fondateur de la théorie de l'information.
