Hvad er en abstrakt maskine?
Abstrakte maskiner, også kaldet Automata, 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 flere bogstavelige maskiner, fordi de antages at fungere perfekt og uafhængigt af hardware. De er opdelt i typer på grundlag af egenskaber, såsom hvordan de udfører deres operationer, og hvilke typer input de kan modtage.
Når de klassificerer abstrakte maskiner, vedrører en af de mest enkle sondringer antallet af operationer, de har tilladelse til at udføre på ethvert givet tidspunkt. En abstrakt maskine kaldes deterministisk, hvis der altid kun er en måde at fortsætte på. Det er ikke -terministisk, 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 input, snarere end blotne 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 enhver anden. Dette spil bruger et gitter, hvor hver boks eller celle enten kan have staten "levende" eller "død." Staten for hele gitteret bestemmes på grundlag af den forrige tilstand. Hvis en levende celle berører nøjagtigt to eller tre andre levende celler, lever den fortsat. Hvis den har en, to eller mere 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 det dødt.
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 række symboler -af ubegrænset størrelse. Det indeholder instruktioner både til ændring af symbolerne og til at ændre det symbol, 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 ikke -terministiske Turing -maskiner, der kan udføre flere forskellige operationer i betragtning af det 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 rigtige computersystemer. Den abstrakte maskine er kernen i datalogi som en disciplin.