5. Sada domacich uloh

Uloha 1 (prez.)

Zostrojte det. turingov stroj(TM), ktory ak dostane navstup kod lub. TM A pretransformuje ho na kod TM A' takeho, ze

1. A' nema definovany krok zo ziadneho akceptacneho stavu
2. L(A') = L(A)

Detailne zdovodnite spravnost svojej konstrukcie.

Uloha 2 (prez.)

Zostrojte det. turingov stroj(TM), ktory pocita funkciu f(n) = n² + n + 3

Detailne zdovodnite spravnost svojej konstrukcie.

Uloha 3 (prez.)

Zostrojte det. turingov stroj(TM), ktory pocita funkciu f(n) = | log₂ n |

Detailne zdovodnite spravnost svojej konstrukcie.

Pozn.: | | znamena hornu celu cast.

Uloha 4 (prez.)

Dokazte, ze k lubovolnemu TM A existuje TM A' taky, ze

1. v kazdom akceptacnom stve zastavi (t.j. nie je definovany krok na ziadne pismeno)
2. v ziadnom inom stave nezastavi
3. L(A') = L(A)

Detailne zdovodnite spravnost svojej konstrukcie.

Uloha 5 (prez)

Zostrojte det. turingov stroj(TM), ktory ak dostane navstup k cisel, k>=2 (napriklad v tvare 1ⁱ¹01ⁱ²0...1^ik0) potom tieto cisla utriedi.

Detailne zdovodnite spravnost svojej konstrukcie.

Uloha 6

Zostrojte det. turingov stroj(TM), ktory ak dostane navstup k cisel, k>=2, v tvare 1ⁱ¹01ⁱ²0...1^ik0 tak nastavi hlavu pred maximalne.

Uloha 7

Zadefinujte det. TM, ktory zacne pracovat na prazdnej paske, bude pracovat donekonecna a a na paske bude postupne generovat slova v abecede {0, 1} v lexikografickom usporiadani a oddelene znakom #.