Co je to abstraktní stroj?

Abstraktní stroje, také nazývané automaty, jsou prvkem teoretické informatiky. Abstraktní stroj se podobá funkci v matematice. Přijímá vstupy a produkuje výstupy podle zadaných pravidel. Abstraktní stroje se liší od doslovnějších strojů, protože se předpokládá, že budou fungovat dokonale a nezávisle na hardwaru. Jsou rozděleny na typy na základě charakteristik, jako je to, jak provádějí své operace a jaké typy vstupů mohou přijímat.

Při klasifikaci abstraktních strojů se jedna z nejjednodušších rozdílů týká počtu operací, které mají v kterémkoli daném bodě provést. Abstraktní stroj se nazývá deterministický, pokud vždy existuje pouze jeden způsob, jak postupovat. Je to nedeterministické, pokud pro stroj existuje několik možností v alespoň jednom z jeho možných stavů. Automat „Pushdown“ je takový, který má schopnost manipulovat s jejich hromadou vstupů, spíše než na ně jednoduše reagovat jedenNE v pořadí, ve které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, což je deterministický abstraktní stroj, protože z jakékoli jiné konfigurace se může objevit pouze jedna konfigurace. Tato hra používá mřížku, ve které může každá box nebo buňka mít buď stav „žijící“ nebo „mrtvý“. Stav celé mřížky je stanoven na základě předchozího stavu. Pokud se živá buňka dotkne přesně dvou nebo tří dalších živých buněk, nadále žije. Pokud má jeden, dva nebo více než tři sousedy (až do možných osmi), zemře. K životu přijde mrtvá buňka s přesně třemi sousedy; Jinak to zůstane mrtvé.

Další příklad, Turing Machine, je jedním z nejzákladnějších a nejzákladnějších abstraktních strojů v informatice. Turing stroj provádí operace na pásku - řetězec symbolů -neomezené velikosti. Obsahuje pokyny jak pro změnu symbolů, tak pro změnu symbolu, na kterém funguje. Jednoduchý stroj Turingu může mít pouze instrukci „Symbol transformace na 1 a poté se přesunout doprava“. Tento stroj by nevydal nic jiného než řetězec 1. Tento jednoduchý turingový stroj je deterministický, ale je také možné konstruovat nedeterministické Turingovy stroje, které mohou provádět několik různých operací vzhledem ke stejnému vstupu.

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.