Hvad er en abstrakt maskine?
Abstrakte maskiner, også kaldet automater, er et element i teoretisk datalogi. En abstrakt maskine ligner en funktion i matematik. Det modtager input og producerer output i henhold til specificerede regler. Abstrakte maskiner adskiller sig fra mere bogstavelige maskiner, fordi de antages at fungere perfekt og uafhængigt af hardware. De er opdelt i typer på grundlag af karakteristika som hvordan de udfører deres operationer og hvilke typer input, de kan modtage.
Ved klassificering af abstrakte maskiner angår en af de mest enkle sondringer antallet af operationer, de har tilladelse til at udføre på et givet tidspunkt. En abstrakt maskine kaldes deterministisk, hvis der altid kun er en måde at fortsætte på. Det er ikke-bestemmende, hvis der findes flere muligheder for maskinen i mindst en af dens mulige tilstande. En "pushdown" -automat er en, der har kapacitet til at manipulere sin stak af input, snarere end blot at svare på dem en efter en i den rækkefølge, de vises.
Wolfram MathWorld giver to berømte eksempler på abstrakte maskiner. Et af disse eksempler er Conways livsspil, som er en deterministisk abstrakt maskine, fordi kun en konfiguration kan komme ud af nogen anden. Dette spil bruger et gitter, hvor hver boks eller celle enten kan have staten "levende" eller "død". Tilstanden for hele nettet bestemmes på grundlag af den forrige tilstand. Hvis en levende celle berører nøjagtigt to eller tre andre levende celler, fortsætter den med at leve. Hvis den har en, to eller flere end tre naboer (op til en mulig otte), dør den. En død celle med nøjagtigt tre naboer vil komme til live; ellers forbliver den død.
Et andet eksempel, Turing-maskinen, er en af de mest basale og grundlæggende abstrakte maskiner inden for datalogi. En Turing-maskine udfører operationer på et bånd - en streng med symboler - af ubegrænset størrelse. Det indeholder instruktioner både til ændring af symbolerne og til ændring af symbolet, som det fungerer på. En simpel Turing-maskine har muligvis kun instruktionen "transform symbol til 1, og flyt derefter til højre." Denne maskine udsender intet andet end en streng på 1'er. Denne enkle Turing-maskine er deterministisk, men det er også muligt at konstruere nondeterministiske Turing-maskiner, der kan udføre flere forskellige operationer med samme input.
Disse abstrakte maskiner kan tjene mange formål. De kan være sjove teoretiske legetøj, men de kan også tjene som modeller til ægte computersystemer. Den abstrakte maskine er kernen i datalogi som en disciplin.