Alan Turing pubblica “On Computable Numbers, with an Application to the Entscheidungsproblem”, un lavoro fondamentale in cui introduce la celebre “Macchina di Turing”: un modello matematico che permette di formalizzare il concetto di computabilità. Una pietra miliare nella storia della matematica e dell’informatica, destinata a gettare le basi teoriche dell’informatica moderna.

La Macchina di Turing in pratica descrive il funzionamento di una macchina capace di eseguire istruzioni e risolvere problemi attraverso algoritmi. È composta da un nastro ( teoricamente infinito) suddiviso in celle, una testina che legge e scrive simboli e un insieme di regole che stabiliscono le operazioni da compiere.

La sua intuizione più importante è quella della macchina universale, capace di simulare qualsiasi altra macchina di Turing, anticipando il principio dei Computer programmabili moderni: i Computer attuali infatti funzionano in modo simile, cambiando il programma per svolgere compiti diversi. È un’idea fondamentale per il concetto di Computer programmabile.

Questo modello ha posto le basi teoriche dell’informatica, contribuendo a definire il concetto di algoritmo e i limiti di ciò che un Computer può calcolare.

La Macchina di Turing è quindi uno dei fondamenti teorici dell’informatica moderna, nonostante sia nata come modello astratto e non come Computer fisico.