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 egenskaper, for eksempel hvordan de utfører sin virksomhet og hvilke typer innganger de kan motta.

Når de klassifiserer abstrakte maskiner, gjelder en av de mest enkle distinksjonene antall operasjoner de har lov til å utføre på et gitt punkt. En abstrakt maskin kalles deterministisk hvis det alltid er en måte for den å fortsette. Det er nondeterministisk hvis det finnes flere muligheter for maskinen i minst en av dens mulige tilstander. En "pushdown" -automat er en som har kapasitet til å manipulere sin bunke med innganger, i stedet for bare å svare på dem en av One i den rekkefølgen de vises i.

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 staten. Hvis en levende celle berører nøyaktig to eller tre andre levende celler, fortsetter den å leve. Hvis den har en, to eller mer enn tre naboer (opp til en mulig åtte), dør den. En død celle med nøyaktig tre naboer vil komme til liv; Ellers vil den forbli død.

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

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 en disiplin.