Turingmaskine

© Dette billede må du ...

Turingmaskine. I hvert skridt af en Turingmaskines beregning sker følgende: Læse/skrivehovedet læser informationen på båndet; ud fra denne og kontrolenhedens tilstand bestemmes, om tilstanden ændres, om der skal skrives noget tilbage til båndet, og om båndet skal rykkes et trin til højre eller venstre. Båndet er vilkårligt langt i begge retninger; ved beregningens start indeholder det en endelig følge af symboler (inddata), mens de øvrige felter er blanke.

Turingmaskine, abstrakt model af en enhed (maskine), der automatisk kan udføre en beregningsprocedure. Modellen, der blev formuleret 1936 af A.M. Turing, er udstyret med simple operationer. De er så kraftfulde, at alle rimelige beregninger kan udføres, men alligevel så simple, at enhver anden automatisk beregningsenhed også kan udføre disse. Hermed kan Turingmaskinen bruges til at undersøge, hvilke funktioner der kan beregnes automatisk (se beregnelighed).

Komponenterne i en Turingmaskine er et bånd, hvorpå inddata til beregningen står, og som kan bruges til at gemme resultater undervejs i beregningerne, et læse/skrivehoved til båndet og en kontrolenhed, der beskriver den ønskede beregning. Hvert skridt i en beregning består i først at læse en informationsenhed fra båndet. Ud fra det læste og kontrolenhedens tilstand bestemmes, om tilstanden skal ændres, om der skal skrives noget tilbage til båndet, og om læse/skrivehovedet skal flyttes. En beregning er en sekvens af sådanne skridt. Kontrolenhedens udformning bestemmer, hvad der beregnes.

En Turingmaskine kan betragtes som en meget simpel computer med kontrolenheden som program. Enhver funktion, der kan beregnes af en computer, kan således beregnes af en Turingmaskine med en passende kontrolenhed. Den simple struktur betyder, at modellens egenskaber kan analyseres matematisk.