turingmaskine

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.

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.

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.

• beregnelighed
• lambdakalkyle
• Alan M. Turing