Co je abstraktní stroj?

Abstraktní stroje, také nazývané automaty, jsou prvkem teoretické informatiky. Abstraktní stroj připomíná funkci v matematice. Přijímá vstupy a vytváří výstupy podle stanovených pravidel. Abstraktní stroje se liší od doslovnějších strojů, protože se předpokládá, že fungují dokonale a nezávisle na hardwaru. Rozdělují se na typy na základě charakteristik, jako je způsob provádění jejich operací a jaké typy vstupů mohou přijímat.

Při klasifikaci abstraktních strojů se jedno z nejjednodušších rozdílů týká počtu operací, které mohou v daném bodě provádět. Abstraktní stroj se nazývá deterministický, pokud existuje vždy pouze jeden způsob, jak pokračovat. Je nedeterministické, pokud existuje více možností pro stroj v alespoň jednom z jeho možných stavů. „Pushdown“ automat je takový, který má schopnost manipulovat s jeho hromadou vstupů, místo aby na ně jednoduše reagoval jeden po druhém v pořadí, v jakém se objevují.

Wolfram MathWorld uvádí dva slavné příklady abstraktních strojů. Jedním z těchto příkladů je Conwayova hra života, která je deterministickým abstraktním strojem, protože z jakékoli jiné se může objevit pouze jedna konfigurace. Tato hra používá mřížku, ve které může každé pole nebo buňka mít buď „živý“ nebo „mrtvý“ stav. Stav celé mřížky je určen na základě předchozího stavu. Pokud se živá buňka dotkne přesně dvou nebo tří dalších živých buněk, pokračuje v životě. Pokud má jednoho, dva nebo více než tři sousedy (až do možných osmi), zemře. Oživí mrtvá cela se přesně třemi sousedy; jinak zůstane mrtvý.

Další příklad, Turingův stroj, je jedním z nejzákladnějších a základních abstraktních strojů v informatice. Turingův stroj provádí operace na pásku - řetězec symbolů - neomezené velikosti. Obsahuje pokyny pro výměnu symbolů i pro změnu symbolu, na kterém pracuje. Jednoduchý Turingův stroj může mít pouze instrukci „transformovat symbol na 1, pak se posuňte doprava“. Tento stroj by nevyprodukoval nic jiného než řetězec 1. Tento jednoduchý Turingův stroj je deterministický, ale je také možné zkonstruovat nedeterministické Turingovy stroje, které mohou při stejném vstupu provádět několik různých operací.

Tyto abstraktní stroje mohou sloužit mnoha účelům. Mohou to být zábavné teoretické hračky, ale mohou také sloužit jako modely pro skutečné počítačové systémy. Abstraktní stroj je jádrem počítačové vědy jako disciplína.