next up previous contents
Next: Klasický Turingův stroj Up: qc Previous: Kvantová interference   Obsah

Matematické modely počítačů

U počítačů jsme ze současných zkušeností zvyklí, že řeší nějaké problémy. V těchto případech se více zaměřujeme na aplikaci a méně nás zajímá teoretický model výpočetních úkonů, které počítač provádí. Již před časem, v roce 1936, se však teoretici Alan Turing, Alonso Church a Kurt Gödel zabývali právě těmito teoretickými základy, na nichž by se dala moderní počítačová věda definovat. Nezávisle na sobě hledali univerzální model, který by z hlediska funkce bez ohledu na fyzikální vlastnosti popsal chování libovolného výpočtu. Každý přišel s vlastním návrhem jak tento problém vyřešit. Později bylo dokázáno, že všechny tři řešení jsou ekvivalentní, přestože každé vychází z rozdílných úvah. Nejčastěji zmiňovaným řešením se stal model Alana Turinga, který byl založen na matematické abstrakci výpočetního stroje, jenž se označuje jako Turingův stroj. V této kapitole se proto budeme zabývat matematickými modely počítačů. Nejprve si popíšeme klasický deterministický Turingův stroj, poté se zmíníme o jeho pravděpodobnostní verzi a na závěr uvedeme jeho paralelu v kvantovém světě.



Podkapitoly

Bashar 2001-01-23