Liczba Taśm w Maszynie Turinga

0

Witam.
Czy mógłby mi ktoś wytłumaczyć w prosty sposób na czym polega twierdzenie na temat Liczby Taśm w Maszynie Turinga ?

Załóżmy, ze maszyna Turinga M o k > 1 taśmach liczy funkcje w czasie f (n),wtedy istnieje maszyna Turinga M' o jednej taśmie liczącą funkcje .

0

Chodzi o to że maszyna turinga z jedna taśmą jest w stanie symulować maszynę z wieloma taśmami, a dodatkowy narzut ma pewne górne wielomianowe ograniczenie (n^2)

0

A w jaki sposób można dowieść tego twierdzenia ?

0

Odpuść sobie studiowanie informatyki bo to nie dla ciebie. Student 2-3 roku powinien umieć sobie to po prostu udowodnić w kilkanaście minut z ołówkiem i kartką w ręku a ty nie umiesz nawet ZNALEŹĆ takiego dowodu, chociaż w internecie tego setki. Marnujesz czas na tych studiach :)
http://wazniak.mimuw.edu.pl/index.php?title=Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa/Wyk%C5%82ad_1:_Obliczenia_w_modelu_maszyny_Turinga#Wielota.C5.9Bmowa_maszyna_Turinga

W wielkim skrócie robisz sobie w jednotaśmowej maszynie takie meta-stany które są złożeniem k-stanów maszyny k-taśmowej.

1 użytkowników online, w tym zalogowanych: 0, gości: 1