Hva er en abstrakt maskin?

Abstrakte maskiner, også kalt automata, er et element i teoretisk informatikk. En abstrakt maskin ligner en funksjon i matematikk. Den mottar innganger og produserer utganger i henhold til spesifiserte regler. Abstrakte maskiner skiller seg fra mer bokstavelige maskiner fordi de antas å fungere perfekt og uavhengig av maskinvare. De er delt inn i typer på grunnlag av kjennetegn som hvordan de utfører sine operasjoner og hvilke typer innspill de kan motta.

Ved klassifisering av abstrakte maskiner angår en av de mest enkle skillene antall operasjoner de har lov til å utføre på et gitt tidspunkt. En abstrakt maskin kalles deterministisk hvis det alltid bare er en måte å fortsette på. Det er ikke-bestemmende om det finnes flere muligheter for maskinen i minst en av dens mulige tilstander. En "pushdown" -automat er en som har kapasitet til å manipulere bunken med innganger, i stedet for å bare svare på dem en etter en i den rekkefølgen de vises.

Wolfram MathWorld gir to kjente eksempler på abstrakte maskiner. Et av disse eksemplene er Conways livsspill, som er en deterministisk abstrakt maskin fordi bare en konfigurasjon kan dukke opp fra noe annet. Dette spillet bruker et rutenett der hver boks, eller celle, enten kan ha staten "levende" eller "død." Tilstanden for hele rutenettet bestemmes på grunnlag av den forrige tilstanden. Hvis en levende celle berører nøyaktig to eller tre andre levende celler, fortsetter den å leve. Hvis den har en, to eller flere enn tre naboer (opp til en mulig åtte), dør den. En død celle med nøyaktig tre naboer vil komme til live; Ellers vil den forbli død.

Et annet eksempel, Turing-maskinen, er en av de mest grunnleggende og grunnleggende abstrakte maskinene innen informatikk. En Turing-maskin utfører operasjoner på et bånd - en streng med symboler - av ubegrenset størrelse. Den inneholder instruksjoner både for å endre symbolene og for å endre symbolet den bruker. En enkel Turing-maskin har kanskje bare instruksjonen "transformer symbol til 1, og flytt deretter til høyre." Denne maskinen ville ikke produsere annet enn en streng på 1. Denne enkle Turing-maskinen er deterministisk, men det er også mulig å konstruere nondeterministiske Turing-maskiner som kan utføre flere forskjellige operasjoner gitt samme innspill.

Disse abstrakte maskinene kan tjene mange formål. De kan være morsomme teoretiske leker, men de kan også tjene som modeller for ekte datasystemer. Den abstrakte maskinen er kjernen i informatikk som fag.