En Turing-maskin är en filosofisk konstruktion för hur en dator kan fungera, uppfann 1936 av Alan Turing, en berömd engelsk matematiker och logiker på 20-talet. Idéerna bakom Turing-maskinen är grunden för all modern mjukvara och hårdvara som existerade från och med 2011, även om de faktiska koncepten som Turing skapade aldrig användes för att bygga en verklig enhet vid den tiden, och uppfanns innan digitala datorer existerade i någon verklig form. Principerna på vilka en Turing-maskin fungerar inkluderar en uppsättning kontroller för in- och utdata, maskinen för att bearbeta data i någon form och en uppsättning etablerade regler för hur denna data behandlas av maskinen.
Genialiteten bakom Alan Turings upptäckt var att varje konsekvent grupp av symboler som representerar meningsfull information, såsom matematiska symboler eller bokstäver som utgör ett språk, kunde bearbetas mekaniskt av en maskin om de fick en ordentlig uppsättning regler för deras bearbetning. Detta skulle resultera i skapandet av mekaniska enheter som kan ställas logiska frågor för komplexa problem och snabbt komma med opartiska svar. Turing-maskinen var en föregångare i detta avseende till en datoralgoritm, som är en sammanställd lista över datorinstruktioner som centrala bearbetningsenheter (CPU) i datorer förlitar sig på för att fungera från och med 2011.
Designen för Turing-maskinen var förenklad enligt moderna datorstandarder på 21-talet, och dess fysiska funktion hade opraktiska tillämpningar, men idéerna som den byggdes på hade en solid grund. Maskinen bestod av ett band eller ett band med intryckta symboler på, som kunde avläsas av ett huvud när tejpen fördes över den. När symbolerna lästes, skulle de anropa vissa tillstånd i maskinen, vilket skulle styra bandets rörelse och påverka utmatningsvärdena som produceras av maskinen. Analogen med moderna datorsystem från 2011 skulle vara att bandet representerar datorprogramkod eller algoritmer, läsaren är CPU:n och utdata skulle vara display- och överföringssystem som monitorer, högtalare och skrivare, nätverkstrafik och mer.
Idéerna bakom Turing-maskinen sågs som en grundläggande funktion för att utföra vilken serie beräkningar som helst och kunde också jämföras med hur den mänskliga hjärnan fungerar. Turing själv och andra på sin tid trodde att Turing-maskinen kunde anpassas för att utföra praktiskt taget alla typer av tänkbara beräkningar och fungera som en universell maskin för att lösa alla mänskliga problem. Problemet som snart uppstod med konceptet är dock känt som en Turing tarpit, och hänvisar till det faktum att även om vilken självständig uppsättning symboler som helst kan bearbetas av en Turing-maskin, får en sådan maskin att ge meningsfulla svar på frågor bygger helt och hållet på allt mer komplexa och flerskiktiga uppsättningar av behandlingsregler.
Datavetenskapen stötte snart på problem med hur mjukvaru- och hårdvarusystem baserade på Turing-maskinens principer kunde fastna i meningslösa beräkningar som kallas programloopar. Logiska begränsningar ledde till anpassningar av Turing-maskinens principer, såsom den för kvant- och probabilistiska Turing-maskiner. En probabilistisk Turing-maskin använder idén om att flera band körs i maskinen samtidigt för att producera olika resultat parallellt, som sedan viktas mot varandra baserat på sannolikheten för vilket resultat som med största sannolikhet är korrekt. Sådana maskiner skulle dra slutsatser på ett sätt som liknar hur fuzzy logic-mjukvara fungerar i avancerade styrsystem från och med 2011.
En kvantdator baserad på Turingmaskinens princip skulle ha ett band av oändlig längd med celler av symboler i ett evigt obestämt tillstånd tills den lästs. Detta skulle tillhandahålla en form av parallell bearbetning som skulle vara mycket överlägsen databehandlingsprocedurer som användes i datorer från och med 2011. Quantum Turing-maskiner erbjuder möjligheten att lagra flera värden i individuella minnesceller tills de nås, vilket standardlogikbaserade datorer inte kan do.