Turingmaskin

En Turingmaskin är en teoretisk modell för att utföra beräkningar. Den utvecklades av matematikern Alan Turing år 1936. Syftet med Turingmaskinen är att betrakta algoritmiska lösningars gränser. En Turingmaskin konstrueras för att lösa ett givet problem, medan den universella Turingmaskinen kan lösa vilket problem som helst. Man kan alltså tänka sig Turingmaskinen som ett datorprogram som utför ett visst program, medan den universella Turingmaskinen kan tänkas som programmerbar. Enligt Church-Turings hypotes kan alla tänkbara beräkningsprocesser utföras av en Turingmaskin. Med andra ord är det den mest kraftfulla beräkningsmekanismen som existerar. Denna tes är inte i strikt matematisk mening bevisad, men allmänt accepterad som sann. Teorierna som Alan Turing skapade, samt den teoretiska Turingmaskinen, har haft en stor betydelse i utvecklingen och konstruktionen av de första datorerna. Alla moderna datorer kan dessutom simuleras med en Turingmaskin. Alan Turings teorier har också en viktig roll inom den matematiska logiken.