Vo všetkých úlohách predpokladajte (pokiaľ nie je uvedené ináč), že L, L₁, L₂, atď. sú ľubovoľné jazyky a h je ľubovoľný homomorfizmus. Zjednotenie značíme u, prienik ^, doplnok ^C, a reverz ^R. Nerovnosť značíme !=.

1. Dané sú TS A₁, A₂. Zostrojte TS A' taký, že L(A')=L(A₁) ^ L(A₂)
2. Zostrojte TS A taký, že
   L(A)={a^p | p je prvočíslo }
3. Zostrojte TS A taký, že
   L(A)={a^z | z je zložené číslo }
4. Zostrojte TS A, ktorý keď spustíme na páske so slovom #w# (kde w je slovo nad abecedou {a,b}), vyrobí na páske slovo #ww# a skončí v akceptačnom stave. Môžete predpokladať, že na začiatku výpočtu je hlava automatu na ľavom znaku #.
5. Zostrojte TS A, ktorý keď spustíme na páske so slovom #w# (kde w je slovo nad abecedou {a,b}), vyrobí na páske slovo #w^R# a skončí v akceptačnom stave. Môžete predpokladať, že na začiatku výpočtu je hlava automatu na ľavom znaku #.
6. Definujte (štandardné 4 definície) Turingov stroj, ktorý používa dve pásky. Na každej páske má samostatnú hlavu. Porovnajte výpočtovú silu dvojpáskového TS s obyčajným TS. Zdôvodnite svoju odpoveď.
7. Definujte (štandardné 4 definície) Turingov stroj, ktorý má dve hlavy na jednej páske. Porovnajte jeho výpočtovú silu s obyčajným TS. Zdôvodnite svoju odpoveď.
8. Definujte (štandardné 4 definície) Turingov stroj, ktorého pohybová zložka delta funkcie je z množiny {-2,0,3}. Porovnajte jeho výpočtovú silu s obyčajným TS. Zdôvodnite svoju odpoveď.