Maszyna Turinga
XYZ: Maszyna Turinga
Niech M
N będzie niedeterministyczną maszyną Turinga rozstrzygającą pewien problem P w pamięci
5n
4 + 2n
3 + 5n
2 + 8n + 3. Wyznacz asymptotyczne ograniczenie złożoności pamięciowej
deterministycznej maszyny Turinga M
D symulującej działanie M
N. Odpowiedź uzasadnij.