Złożoność obliczeniowa/Test 1: Obliczenia w modelu maszyny Turinga

From Studia Informatyczne

Język rekurencyjny to

język akceptowany przez pewną maszynę Turinga

język akceptowany przez pewną maszynę Turinga z własnością stopu

zbiór słów nad pewnym alfabetem

skończony zbiór słów nad pewnym alfabetem

zbiór słów, który można wylistować uruchamiając pewną maszynę Turinga


W maszynie Turinga funkcja przejścia

może mieć nieskończenie wiele wartości

określona jest dla przeliczalnej liczby argumentów

może być funkcją częściową

określona jest na konfiguracjach maszyny

dla każdej pary (stan, znak) posiada inną wartość


W k-taśmowej maszynie Turinga funkcja przejścia określona jest dla całych konfiguracji

przekształca (k+1)-krotki w (2k+1)-krotki

zależy od numerów klatek czytanych przez k głowic

przekształca (k+1)-krotki w (k+2)-krotki

nie może być funkcją częściową


Symulacja maszyny k-taśmowej na maszynie z jedną taśmą

wymaga kwadratowego zwiększenia pamięci roboczej

jest wykonalna przy kwadratowym zwiększeniu czasu

może być przeprowadzona w tym samym czasie

może być przeprowadzona w tej samej pamięci


Jeśli maszyna niedeterministyczna M o złożoności O(n^2) na wejściu ma słowo x\in L(M), to

stopnie wierzchołków drzewa obliczeń nie są ograniczone przez stałą i są ograniczone przez O(n^2)

długości wszystkich ścieżek są ograniczone przez O(n^2)

niektóre wierzchołki w drzewie mogą być identyczne

możliwe jest, że wszystkie ścieżki mają długość O(n)


Maszyna niedterministyczna dla danego słowa wejściowego x na 3/4 możliwych ścieżek obliczeń zatrzymuje się po O(n) krokach, na pozostałych nie zatrzymuje się. Maszyna ta

ma własność stopu

nie ma własności stopu

ma złożoność czasową O(n)

akceptuje x

nie akceptuje x


Symulacja maszyny niedeterministycznej przez deterministyczną

wymaga kwadratowego zwiększenia czasu

wymaga wykładniczego zwiększenia czasu

nie wymaga zwiększenia rzędu złożoności czasowej

nie jest możliwa na maszynie jednotaśmowej

nie jest możliwa na maszynie dwutaśmowej