Turingův stroj s náhodným přístupem - Random-access Turing machine

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Turingův stroj s náhodným přístupem"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Srpna 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v výpočetní složitost, pole počítačová věda, náhodně přístupné Turingovy stroje jsou příponou Turingovy stroje mluvilo se o malých třídách složitosti, zejména u tříd využívajících logaritmický čas, jako DLOGTIME a Logaritmická hierarchie.

Definice

Na Turingově stroji s náhodným přístupem existuje speciální ukazatel páska logaritmického prostoru přijímající binární slovník. Turingův stroj má zvláštní stav, že když je binární číslo na ukazatel páska je „p“, Turingův stroj napíše na pracovní pásku strth symbol vstupu.

To umožňuje Turingovu stroji přečíst libovolné písmeno vstupu, aniž by si vzal čas na přesun po celém vstupu. To je povinné pro třídy složitosti, které používají méně než lineární čas.

Reference

• N. Immerman Popisná složitost (1999 Springer), kapitola 5