Una macchina di Turing è un costrutto filosofico su come potrebbe funzionare un computer, inventato nel 1936 da Alan Turing, un famoso matematico e logico inglese del XX secolo. Le idee alla base della macchina di Turing sono la base per tutti i moderni software e sistemi hardware esistenti a partire dal 20, sebbene i concetti reali creati da Turing non siano mai stati utilizzati per costruire un dispositivo reale all’epoca e siano stati inventati prima che i computer digitali esistessero in qualsiasi forma reale. I principi su cui funziona una macchina di Turing includono una serie di controlli per i dati di input e output, la macchina per elaborare i dati in qualche forma e una serie di regole stabilite su come questi dati vengono elaborati dalla macchina.
Il genio dietro la scoperta di Alan Turing era che qualsiasi gruppo coerente di simboli che rappresentano informazioni significative, come simboli matematici o lettere che compongono un linguaggio, potrebbe essere elaborato meccanicamente da una macchina se dotato di un adeguato insieme di regole per la loro elaborazione. Ciò comporterebbe la creazione di dispositivi meccanici a cui potrebbero essere poste domande logiche per problemi complessi e fornire rapidamente risposte imparziali. La macchina di Turing è stata un precursore in questo senso di un algoritmo informatico, che è un elenco compilato di istruzioni per computer su cui le unità di elaborazione centrale (CPU) nei computer fanno affidamento per funzionare a partire dal 2011.
Il design della macchina di Turing era semplicistico per gli standard informatici moderni del 21° secolo, e la sua funzione fisica era poco pratica per quanto riguarda la sua implementazione, ma le idee su cui era costruita avevano solide fondamenta. La macchina consisteva in un nastro o nastro con simboli impressi su di esso, che poteva essere letto da una testina mentre il nastro veniva passato su di esso. Quando i simboli venivano letti, invocavano determinati stati nella macchina, che dirigevano il movimento del nastro e influenzavano i valori di output prodotti dalla macchina. L’analogo ai moderni sistemi informatici del 2011 sarebbe che il nastro rappresenta il codice o gli algoritmi del software del computer, il lettore è la CPU e l’output sarebbe sistemi di visualizzazione e trasmissione come monitor, altoparlanti e stampanti, traffico di rete e altro.
Le idee alla base della macchina di Turing erano viste come una funzione fondamentale per eseguire qualsiasi serie di calcoli e potevano anche essere paragonate a come funziona il cervello umano. Turing stesso e altri del suo tempo credevano che la macchina di Turing potesse essere adattata per eseguire praticamente qualsiasi tipo di calcolo immaginabile e agire come una macchina universale per risolvere tutti i problemi umani. Il problema che è sorto presto con il concetto, tuttavia, è noto come tarpit di Turing e si riferisce al fatto che, sebbene qualsiasi insieme di simboli autoconsistente possa essere elaborato da una macchina di Turing, far sì che tale macchina produca risposte significative a domande si basa interamente su insiemi di regole di elaborazione sempre più complessi e multistrato.
L’informatica incontrò presto problemi con il modo in cui i sistemi software e hardware basati sui principi della macchina di Turing potevano impantanarsi in calcoli privi di significato noti come cicli di programma. Le limitazioni logiche hanno portato ad adattamenti sui principi delle macchine di Turing, come quello delle macchine di Turing quantistiche e probabilistiche. Una macchina probabilistica di Turing utilizza l’idea di più nastri eseguiti contemporaneamente nella macchina per produrre risultati diversi in parallelo, che vengono quindi ponderati l’uno contro l’altro in base alla probabilità che il risultato sia più accurato. Tali macchine arriverebbero a conclusioni in modo simile a come il software di logica fuzzy opera nei sistemi di controllo avanzati a partire dal 2011.
Un computer quantistico basato sul principio della macchina di Turing avrebbe un nastro di lunghezza infinita con celle di simboli in uno stato perpetuo indeterminato fino alla lettura. Ciò fornirebbe una forma di elaborazione parallela che sarebbe di gran lunga superiore alle procedure di elaborazione dei dati utilizzate nei computer a partire dal 2011. Le macchine Quantum Turing offrono la possibilità di memorizzare più valori in singole celle di memoria fino all’accesso, cosa che i computer basati su logica standard non possono fare.