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

Język rekurencyjny to

język akceptowany przez pewną maszynę Turinga Źle

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

zbiór słów nad pewnym alfabetem Źle

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

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

W maszynie Turinga funkcja przejścia

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

określona jest dla przeliczalnej liczby argumentów Źle

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

określona jest na konfiguracjach maszyny Źle

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

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 Dobrze

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

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

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

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

wymaga kwadratowego zwiększenia pamięci roboczej Źle

jest wykonalna przy kwadratowym zwiększeniu czasu Dobrze

może być przeprowadzona w tym samym czasie Źle

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

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})$ Źle

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

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

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

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 Źle

nie ma własności stopu Dobrze

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

akceptuje $x$ Dobrze

nie akceptuje $x$ Źle

Symulacja maszyny niedeterministycznej przez deterministyczną

wymaga kwadratowego zwiększenia czasu Źle

wymaga wykładniczego zwiększenia czasu Dobrze

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

nie jest możliwa na maszynie jednotaśmowej Źle

nie jest możliwa na maszynie dwutaśmowej Źle