Modellerturingmaskiner

Modellerturingmaskiner er teoretiske beregningsmodeller som bygger på Turingmaskinen, en av de sentrale modellene i beregningsvitenskapen. En modellert Turingmaskin består av et uendelig langt bånd delt inn i celler som kan inneholde symboler fra et alfabet, et les-/skrivhodet som kan flyttes ett skritt til venstre eller høyre, og en kontrollenhet med et endelig antall tilstander. Maskinen har en starttilstand og en eller flere aksepterings- eller avvisningstilstander. Beregninger utføres ved at maskinen i hvert trinn leser symbolet under hodet, bestemmer neste tilstand, oppdaterer symbolet og beveger hodet.

Det finnes to hovedtyper: deterministiske modellerturingmaskiner, der det ikke finnes mer enn én mulig neste handling for hver kombinasjon av gjeldende tilstand og lest symbol, og ikke-deterministiske varianter, som tillater flere muligheter. I ren beregningslogikk har disse variantene samme beregningskraft: de kan simulere hverandre i prinsippet, selv om kostnadene i tid og minne kan variere.

Bruksområder: Modellerturingmaskiner brukes til å studere beslutbarhet og beregningsbarhet, og til å definere og analysere kompleksitet, som tids- og plasskostnader for ulike algoritmer. Varianter inkluderer multi-tape, nondeterministiske, probabilistiske og oracle-tilsvarende maskiner, som gir forskjellige måter å uttrykke beregning på, uten å endre den grunnleggende definisjonen av hva som er beregnbart.

Historie og betydning: Turingmaskinen ble introdusert av Alan Turing i 1930-årene og har siden vært grunnlaget for teoretisk datavitenskap. Modellerturingmaskiner er standard verktøy i undervisning og forskning for formalisering av algoritmer og bevis om beslutbarhet og kompleksitet.