Wat is een abstracte machine?
Abstracte machines, ook wel automaat genoemd, zijn een element van theoretische informatica. Een abstracte machine lijkt op een functie in de wiskunde. Het ontvangt inputs en produceert uitgangen volgens gespecificeerde regels. Abstracte machines verschillen van meer letterlijke machines, omdat wordt aangenomen dat ze perfect en onafhankelijk van hardware functioneren. Ze zijn onderverdeeld in typen op basis van kenmerken zoals hoe ze hun bewerkingen uitvoeren en welke soorten input ze kunnen ontvangen.
Bij het classificeren van abstracte machines, een van de meest eenvoudige onderscheidingen betreft 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 staten. Een "pushdown" -automaat is er een die de capaciteit heeft om zijn stapel inputs te manipuleren, in plaats van er eenvoudig op te reagerenne in de volgorde waarin ze verschijnen.
Wolfram Mathworld geeft twee beroemde voorbeelden van abstracte machines. Een van deze voorbeelden is Conway's Game of Life, een deterministische abstracte machine omdat slechts één configuratie uit alle andere kan voortkomen. Deze game gebruikt een raster waarin elke doos of cel de staat "leven" of "dood" kan hebben. De staat van het hele rooster wordt bepaald op basis van de vorige staat. 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 (tot een mogelijke 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 elementaire en fundamentele abstracte machines in de informatica. Een Turing -machine voert bewerkingen uit op een tape - een reeks symbolen -van onbeperkte maat. Het bevat instructies, zowel voor het wijzigen van de symbolen als voor het wijzigen van het symbool waarop het werkt. Een eenvoudige Turing -machine kan alleen de instructie "Transform Symbool naar 1 hebben en vervolgens naar rechts gaan." Deze machine zou niets anders uitvoeren dan een reeks van 1's. Deze eenvoudige Turing -machine is deterministisch, maar het is ook mogelijk om niet -deterministische Turing -machines te construeren die verschillende bewerkingen kunnen uitvoeren, gezien dezelfde invoer.
Deze abstracte machines kunnen vele doeleinden dienen. Ze kunnen leuk theoretisch speelgoed zijn, maar ze kunnen ook dienen als modellen voor echte computersystemen. De abstracte machine vormt de kern van de informatica als een discipline.