Macchina di Turing: modello classico e quantistico

In questo elaborato viene discusso il modello teorico computazionale conosciuto come macchina di Turing, formulato nella sua versione classica da Alan Turing nel 1936, dando il via alla moderna teoria computazionale. Viene esposta anche la sua versione nel contesto della teoria quantistica, seguendo principalmente il lavoro del fisico David Deutsch che nel 1985 formalizza la macchina di Turing quantistica, primo modello computazionale basato sui risultati della meccanica quantistica. Si analizzano le principali proprietà di un calcolatore quantistico universale, mettendo in mostra come sia possibile ottenere generazioni di numeri casuali, simulare sistemi fisici arbitrari e sfruttare il principio di sovrapposizione degli stati per effettuare computazioni parallele.