En turingmaskine betegner en abstrakt model af en enhed (en 'maskine'), der automatisk kan udføre en beregningsprocedure. Modellen, der blev formuleret i 1936 af Alan M. Turing, er udstyret med simple operationer. Turingmaskiner 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.
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.
Turingmaskinens opbygning
Komponenterne i en turingmaskine er:
- et endeligt antal tilstande,
- 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.
- en kontrolenhed, der beskriver den ønskede beregning.
Hvert skridt i en beregning består i først at læse et tegn fra båndet. Ud fra det læste og kontrolenhedens tilstand bestemmes, om tilstanden skal ændres, om et andet tegn skal skrives tilbage til båndet, og om læse/skrivehovedet skal flyttes. Tegnene kommer fra en endelig mængde af forskellige tegn, ofte blot 0 og 1. En beregning er en sekvens af sådanne skridt. Kontrolenhedens udformning bestemmer, hvad der beregnes.
Turingmaskinen som simpel computer
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. En anden simpel model for beregninger er lambdakalkylen, der er bevist at have samme regnekraft som turingmaskiner.
Universelle turingmaskiner
Kontrolenhedens tilstande kan betragtes som et program, der læser inddata fra båndet og skriver både mellemberegninger og slutresultatet på samme bånd. I moderne computere er programmet dog en del af lageret (svarende til båndet i en turingmaskine), og kontrolenheden (CPU'en) er den samme for alle programmer. Man kan overveje, om der findes en lignende model for turingmaskiner: Findes der en universel kontrolenhed, således at man kan gemme både program og inddata på båndet og få udført programmet på inddata, og at alle beregnelige funktioner kan beregnes blot ved at udskifte den del af båndet, der indeholder programmet. Svaret er "ja", der findes universelle turingmaskiner, og deres kontrolenheder kan være ret små. Hvis båndet kun kan indeholde 0 og 1, findes der en kontrolenhed med 15 tilstande. Hvis man tillader flere forskellige tegn, kan antallet af tilstande i kontrolenheden reduceres helt ned til 2, hvis der er 18 eller flere forskellige mulige tegn på båndet.
Kommentarer
Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.
Du skal være logget ind for at kommentere.