Vad är en abstrakt maskin?

Abstrakta maskiner, även kallad automat, är ett element i teoretisk datavetenskap. En abstrakt maskin liknar en funktion i matematik. Den tar emot ingångar och producerar utgångar enligt specificerade regler. Abstrakta maskiner skiljer sig från mer bokstavliga maskiner eftersom de antas fungera perfekt och oberoende av hårdvara. De är indelade i typer utifrån egenskaper såsom hur de utför sina operationer och vilka typer av input de kan få.

Vid klassificering av abstrakta maskiner gäller en av de mest enkla distinktionerna antalet operationer som de får utföra vid en given punkt. En abstrakt maskin kallas deterministisk om det alltid bara finns ett sätt att fortsätta. Det är obestämd om det finns flera möjligheter för maskinen i minst ett av dess möjliga tillstånd. En "pushdown" -automat är en som har förmågan att manipulera sin stack med ingångar, snarare än att helt enkelt svara på dem en efter en i den ordning de visas.

Wolfram MathWorld ger två kända exempel på abstrakta maskiner. Ett av dessa exempel är Conways livsspel, som är en deterministisk abstrakt maskin eftersom bara en konfiguration kan komma ut från någon annan. Detta spel använder ett rutnät där varje ruta, eller cell, antingen kan ha staten "levande" eller "död". Tillståndet för hela nätet bestäms på grundval av det tidigare tillståndet. Om en levande cell berör exakt två eller tre andra levande celler fortsätter den att leva. Om den har en, två eller mer än tre grannar (upp till möjliga åtta), dör den. En död cell med exakt tre grannar kommer att leva upp; annars kommer den att förbli död.

Ett annat exempel, Turing-maskinen, är en av de mest grundläggande och grundläggande abstrakta maskinerna inom datavetenskap. En Turing-maskin utför operationer på ett band - en sträng symboler - av obegränsad storlek. Den innehåller instruktioner både för att ändra symbolerna och för att ändra symbolen som den fungerar på. En enkel Turing-maskin kanske bara har instruktionen "transformera symbol till 1, flytta sedan åt höger." Den här maskinen levererade inget annat än en sträng av 1: er. Denna enkla Turing-maskin är deterministisk, men det är också möjligt att konstruera nondeterministiska Turing-maskiner som kan utföra flera olika operationer med samma input.

Dessa abstrakta maskiner kan tjäna många syften. De kan vara roliga teoretiska leksaker, men de kan också fungera som modeller för riktiga datorsystem. Den abstrakta maskinen är kärnan i datavetenskapen som en disciplin.