Matematické Fórum

Počet pásek označme k. Základní myšlenka je v rozšíření abecedy stroje. Pokud měly všechny pásky původního stroje abecedu G, bude mít výsledný stroj abecedu obsahující k-tice symbolů z kódující sloupce v původním stroji. Pokud třeba původní stroj měl tři pásky s následujícím obsahem:
A B C
B ) (CAX) (X) (XXX)
(záleží jak máte zavedené pásky -- někdy se uvažuje ukončení symbolem $, někdy je páska až do konce vyplněna nějakými symboly @. Ve druhém případě by se nemusel zavádět symbol X, stačilo by použít @)

Takto můžeme uchovat informaci o obsahu pásek, potřebujeme uchovat ještě informaci o hlavách. Hlavy v původním stroji si můžeme představit jako hvězdičky nad písmeny. K zakódování nám proto v případě třípáskového stroje stačí, aby abeceda nového stroje neobsahovala jen symboly tvaru (KLM), kdy K,L,M jsou z G, ale i symboly (K*LM), (KL*M), ...,(K*L*M*).

Nový stroj pak bude pracovat tak, že na příkaz "pohni i-tou hlavou doprava" původnímu stroji vykoná tyto operace:
1) najdi i-tou hlavu (tj. symbol, který má ohvězdičkovanou i-tou složku)
2) nahraď ho symbolem, ve kterém i-tá složka ohvězdičkovaná není
3) pohni hlavou doprava
4) ohvězdičkuj i-tou složku aktuálního symbolu

Sestavili jsme tedy jednopáskový stroj simulující stroj původní. Abychom mohli porovnat jejich paměťové složitosti, je potřeba, aby pracovaly nad stejnou abecedou. Proto uděláme v našem simulátoru následující změnu: k-tici symbolů původního stroje zakódujeme do 2k symbolů, na lichých pozicích budou symboly z pásky, na sudých případné hvězdičky. Na sudých pozicích, na kterých nejsou hvězdičky, bude X. Symbol (K*LM) z předchozího simulátoru bude proto zapsán šesticí symbolů K*LXMX. Paměťová složitost se proto zvýšila 2k-krát.
Časová složitost se al změní výrazněji -- místo jedné operace "posuň i-tou hlavu doprava" hrozí, že stroj bude muset prohledat celou pásku, než i-tou hlavu najde.

---
Teď mě napadlo, že to zvětšení a následné zmenšení abecedy by se dalo vypustit, kdybychom hned na začátku řekli, že sloupec budeme kódovat 2k znaky na pásce simulátoru.