Pult
pult je druh paměti zvažované v teorii vypočitatelnosti. Pult skladuje jeden přirozené číslo (zpočátku nula) a moci být libovolně-mnoho číslic dlouho. Pult je obvykle zvažován v spojení s konečným státním strojem (FSM), který může vykonávat následující operace na pultě:- Kontrola zda pult je nulový
- Inkrement pult jeden
- Zmenšit pult jeden (jestliže to je už nula, toto opustí to nezměněný)
| Tabulka s obsahem |
| 1 síla |
- Deterministický nebo Non-deterministický FSM plus dva pulty
- Non-deterministický FSM plus jeden zásobník
- Non-deterministický FSM plus jeden pult
- Deterministický FSM plus jeden pult
- Deterministický nebo Non-deterministický FSM
První stroj, FSM plus dva pulty, je ekvivalent u moci k Turing stroji. Tato rovnocennost může být ukazována ve třech krokách. Nejprve, Turing stroj může být simulovaný dvěma zásobníky. Pak, hromada může být simulovaná dvěma pulty. Konečně, čtyři pulty mohou být simulovány dvěma pulty.
Krok 1: Turing stroj může být simulovaný dvěma zásobníky.
Turing stroj sestává z FSM a nekonečná páska, zpočátku se plnil nulami, na kterém stroj může psát ones a nuly. Kdykoli, číst/psát hlavu strojových důvodů k jedné buňce na pásce. Tato páska může být pojmově zmírnění v polovině na tom místě. Každá polovina pásky může být zpracovaná jako hromada, kde vrchol je buňka nejbližší číst/psát hlavu a dolní část je nějaká vzdálenost pryč od hlavy, se všemi nulami na pásce za dolní částí. Společně, Turing stroj může být simulovaný FSM plusem dva zásobníky. Pohybovat hlavou levý nebo pravý je ekvivalent k šupinatění kousek od jednoho zásobníku a narážení to na jiný. Psaní je ekvivalentní ke střídání kousek dříve tlačit to. Krok 2: Hromada může být simulovaná dvěma pulty.
Hromada obsahovat nuly a ones moci být simulován dvěma pulty, když kousky na hromadě jsou myšlenka jak reprezentovat dvojkové číslo, s vrcholem být nejméně významný bit. Tlačit nula na hromadě je ekvivalentní ke zdvojnásobení počtu. Tlačit jeden je ekvivalentní ke zdvojení a sčítání 1. Šupinatění je ekvivalentní k dělení 2, kde zbytek je kousek to bylo vyjato. Dva pulty mohou simulovat tento zásobník, ve kterém jeden z pultů drží číslo jehož binární reprezentace reprezentuje kousky na hromadě a jiný pult je používán jako scratchpad. To zdvojnásobí počet v prvním pultu, FSM může inicializovat druhý protipól pro nulu, pak opakovaně zmenšit první pult jakmile a inkrement druhý pult dvakrát. Toto pokračuje, než první pult dosáhne nuly. Na tom místě, druhý pult bude držet zdvojnásobené číslo. Půlení je vykonáváno tím, že zmenší jeden pult dvakrát a inkrement jiný jakmile, a opakování až do prvního pultu dosáhne nuly. Zbytek může být předurčený zda to dosáhlo nuly po dokonce nebo liché číslo zkoušek.
Krok 3: Čtyři pulty mohou být simulovány dvěma pulty.
Jako dříve, jeden z pultů je používán jako scratchpad. Jiný, skutečný pult drží celé číslo jehož primární factorization je 23b5c7d. Exponenty , b, c, a d moci být myšlenka jako čtyři virtuální pulty, které jsou simulovány. Jestliže skutečný pult je dán k nule pak incremented jednou, to je ekvivalentní k nastavení všechny virtuální protipóly pro nulu. Jestliže skutečný pult je zdvojnásoben, to je ekvivalentní k incrementing , a jestliže to je půleno, to je ekvivalent k zmenšit . Podobnou procedurou, to může být znásobil nebo podělil 3, který je ekvivalentní k incrementing nebo zmenšit b. Podobně, c a d moci být incremented nebo zmenšil. Ke kontrole jestliže virtuální pult takový jak c je stejný s nulovým, spravedlivým předělem skutečný pult 5, vidět co zbytek je, pak násobit 5 a sčítat couvat se zbytkem. To opustí skutečný pult nezměněný. Zbytek chtít nonzero jestliže a jediný jestliže c byl nulový.
Jako výsledek, FSM s dva pulty mohou simulovat čtyři pulty, který být podle pořadí simulovat dva zásobníky, který simulují Turing stroj. Proto, FSM plus dva pulty je přinejmenším jak silný jako Turing stroj. Turing stroj může snadno simulovat FSM se dvěma pulty, proto dva stroje mají rovnocennou moc.