Wat is een abstracte machine?
Abstracte machines, ook automaten genoemd, zijn een element van theoretische informatica. Een abstracte machine lijkt op een functie in de wiskunde. Het ontvangt ingangen en produceert uitgangen volgens gespecificeerde regels. Abstracte machines verschillen van meer letterlijke machines omdat ze geacht worden perfect en onafhankelijk van hardware te functioneren. Ze zijn onderverdeeld in typen op basis van kenmerken zoals hoe ze hun activiteiten uitvoeren en welke soorten invoer ze kunnen ontvangen.
Bij het classificeren van abstracte machines is een van de meest eenvoudige onderscheidingen het aantal bewerkingen dat ze op een bepaald punt mogen uitvoeren. Een abstracte machine wordt deterministisch genoemd als er altijd maar één manier is om door te gaan. Het is niet-deterministisch als er meerdere mogelijkheden bestaan voor de machine in ten minste een van de mogelijke toestanden. Een "pushdown" -automaat is een automaat die de capaciteit heeft om zijn stapel ingangen te manipuleren, in plaats van er één voor één op te reageren in de volgorde waarin ze verschijnen.
Wolfram MathWorld geeft twee beroemde voorbeelden van abstracte machines. Een van deze voorbeelden is het levensspel van Conway, dat een deterministische abstracte machine is, omdat slechts één configuratie uit een andere kan ontstaan. Deze game maakt gebruik van een raster waarin elk vak of elke cel de status 'levend' of 'dood' kan hebben. De status van het hele raster wordt bepaald op basis van de vorige status. Als een levende cel precies twee of drie andere levende cellen raakt, blijft deze leven. Als het één, twee of meer dan drie buren heeft (maximaal een acht), sterft het. Een dode cel met precies drie buren zal tot leven komen; anders blijft het dood.
Een ander voorbeeld, de Turing-machine, is een van de meest basale en fundamentele abstracte machines in de informatica. Een Turing-machine voert bewerkingen uit op een band - een reeks symbolen - van onbeperkte grootte. Het bevat instructies voor het wijzigen van de symbolen en voor het wijzigen van het symbool waarop het werkt. Een eenvoudige Turing-machine heeft mogelijk alleen de instructie "transformeer symbool in 1, ga dan naar rechts." Deze machine zou niets anders produceren dan een reeks van 1'en. Deze eenvoudige Turing-machine is deterministisch, maar het is ook mogelijk om niet-deterministische Turing-machines te construeren die verschillende bewerkingen kunnen uitvoeren met dezelfde input.
Deze abstracte machines kunnen vele doelen dienen. Ze kunnen leuk theoretisch speelgoed zijn, maar ze kunnen ook dienen als modellen voor echte computersystemen. De abstracte machine vormt het hart van de informatica als een discipline.