#1 23. 10. 2019 20:43
- stepanVich
- Zelenáč
- Příspěvky: 9
- Škola: VŠB FEI
- Pozice: student
- Reputace: 0
Simulace turingova stroje
Ahoj, mám zde úkol do Teoretické Informatiky. Pomohl by mi s ním někdo? Zadání zní takto: Popište jak Turingův stroj s oboustranně nekonečnou páskou simulovat Turingovým strojem s jednostranně nekonečnou páskou tak, aby simulace jednoho kroku původního stroje vyžadovala O(1) kroků simulujícího stroje. Máte nějaké nápady?
Offline
#3 23. 10. 2019 21:01
- stepanVich
- Zelenáč
- Příspěvky: 9
- Škola: VŠB FEI
- Pozice: student
- Reputace: 0
Re: Simulace turingova stroje
↑ Stýv: Jasně, seřadí se podle absolutní hodnoty a očíslují se pomocí přirozených čísel (ty jsou spočetné). Takhle to mám udělat i s Turingovým strojem? Že si představím že jednostranná páska jsou přirozená čisla a oboustraná by představovala celá čísla?
Offline