Turingmaskin

En riktig Turingmaskin, byggd av amerikanen Mike Davis.
En riktig Turingmaskin, byggd av amerikanen Mike Davey.

en teoretisk dator som beskrevs 1936 av Alan Turing. Det var en ren tankekonstruktion. (1936 fanns inga datorer.) – En Turing­maskin mot­svarar ett modernt datorprogram, men när man talar om Turingmaskiner menar man ofta universella Turingmaskiner, som mot­svarar datorer. – Alan Turing beskrev maskinen i artikeln ”On computable numbers with an application to the Entscheidungsproblem” (länk). Artikeln handlade om ett matematiskt problem, stopproblemet, inte om datorer. Turing beskrev det som senare fick heta Turingmaskinen enbart för att göra ett matematiskt bevis åskådligt. Det var inte en beskrivning av något som Turing verkligen tänkte bygga. – Turing­­maskinen har en pappers­remsa som matas fram och tillbaka genom ett läs- och skrivhuvud enligt bestämda regler. Det finns flera upp­­sätt­ningar regler som kallas för tillstånd, och i reglerna ingår över­gångar från ett tillstånd till ett annat. Skriv­huvudet kan läsa, radera och skriva tecken på remsan. Man programmerar Turing­maskinen med tecken på remsan, och Turingmaskinen matar sedan, enligt reglerna, remsan fram och tillbaka, läser, raderar och skriver samt växlar till­stånd tills den kommer till en regel som säger ”stopp”. Då stannar maskinen och lösningen på pro­blemet kan avläsas på remsan. Detta är helt genomförbart, bortsett från de praktiska problemen med pappersremsan, pennan och radergummit. – I princip kan varje pro­blem som kan lösas med ett modernt dator­program också lösas av en mot­svarande Turing­maskin, men naturligt­vis är det ogörligt att använda en maskin med pappers­remsa. Man brukar därför simulera Turing­maskiner i datorer. (Se här.) Det är nämligen bra att öva sig på program för Turingmaskiner när man ska lära sig programmera. –– Se också finit tillstånds­maskin. –– Efter andra världskriget konstruerade Alan Turing en dator, ACE som till stor del baserades på de principer som Turing beskrev i sin artikel. – Turingmaskinen införde idén om lagrade program i datortekniken. Idén togs upp av John von Neumann i hans arkitektur för datorer, von Neumann-arkitekturen. Den är mindre sofistikerad än Turings modell, men mer över­skådlig, och blev allenarådande i dator­tekniken. –– Pro­fessor Bernard Hodson (länk) i Kanada har ut­vecklat en modern programmerings­teknik baserad på Turings principer. –Mate­matikern Stephen Wolfram arrangerade 2007 en tävling om Turingmaskiner, se här. – Mike Davey beskriver hur han byggde en riktig Turingmaskin (se bilden) i denna artikel. – Richard Ridel har byggt en Turingmaskin av trä, se denna video.

[it-historia] [matematik och logik] [ändrad 12 mars 2018]

Dagens ord: 2013-05-20