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
Bruksområder: Modellerturingmaskiner brukes til å studere beslutbarhet og beregningsbarhet, og til å definere og analysere kompleksitet,
Historie og betydning: Turingmaskinen ble introdusert av Alan Turing i 1930-årene og har siden vært grunnlaget