Wat is een abstracte machine?

Samenvatting 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 waar ze toe mogen uitvoerenelk bepaald punt.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 eenvoudigweg op een voor een te reageren in de volgorde waarin ze verschijnen.

Wolfram Mathworld geeft twee beroemde voorbeelden van abstracte machines.Een van deze voorbeelden is Conways 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 kan leven of dood.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 mdash; een reeks symbolen mdash; van onbeperkte grootte.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 het instructietransformatiesymbool hebben naar 1 en ga dan naar rechts.Deze machine zou niets anders uitvoeren dan een reeks van 1s.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.