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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wprowadzenie

Zadaniem tego modułu jest wprowadzić podstawowe narzędzie, jakim dla teorii złożoności jest maszyna Turinga. Jest to pewien abstrakcyjny model maszyny liczącej, który ma trzy podstawowe własności:

  • jest prosty koncepcyjnie.
  • potrafi przeprowadzić dowolne obliczenie możliwe na innych znanych nam maszynach.
  • zużycie zasobów podczas obliczenia dobrze modeluje rzeczywiste komputery.

Pierwsza własność jest bardzo istotna, gdyż pozwala formułować i dowodzić twierdzenia dotyczące maszyn używając tylko najprostszych pojęć matematycznych.

Druga własność jest związana ze słynną tezą Churcha mówiącą, że każdą funkcję, którą da się efektywnie obliczać, da się obliczać używając maszyny Turinga. Jest to stwierdzenie natury filozoficznej i nie może być matematycznie udowodnione, ale rzeczywicie żaden ze znanych sposobów reprezentowania obliczeń nie potrafi przedstawić nic więcej niż maszyna Turinga.

Trzecia własność jest najważniejszą dla teorii złożoności. W dalszej części kursu wykażemy, że zarówno czas, jak i pamięć zużyta podczas obliczenia maszyny Turinga nie różnią się bardzo od zasobów zużywanych podczas wykonania algorytmów na rzeczywistych komputerach. Sprawia to, że wyniki teorii złożoności mówiące o obliczeniach na maszynach Turinga pozostają w ścisłym związku z rzeczywistymi problemami informatyki i praktycznymi implementacjami algorytmów.

Notacje i pojęcia wprowadzone w tym module będą szeroko wykorzystywane w następnych. Dlatego nawet osoby dobrze znające pojęcia związane z maszynami Turinga powinny sprawdzić, czy znane im definicje są tymi samymi, które będą używane w dalszej części kursu.

Model obliczeń

Zacznijmy od odpowiedzi na pytanie, po co model obliczeń jest nam w ogóle potrzebny? Celem tego przedmiotu jest zbadanie jak złożone są różne problemy. Ale złożone dla kogo? Dla komputera oczywiście, bo to właśnie problemy rozwiązywane przez komputery nas interesują. Odpowiedź ta jest jak najbardziej poprawna, ale bardzo mało precyzyjna, bo dla jakiego komputera? Na świecie są miliony, jeżeli nie miliardy, komputerów i różnią się one od siebie możliwościami. Zadania, które wykonuje się łatwo na jednym z nich mogą być trudne, lub wręcz niemożliwe, do wykonania na innym.

Moglibyśmy wybrać jakiś konkretny komputer, albo nawet model komputera - powiedzmy „ZX Spectrum” (zakładając, że wszystkie jego egzemplarze pracują tak samo), ale niewiele by nas to posunęło do przodu - dopiero po zbadaniu i dokładnym opisaniu możliwości naszego komputera moglibyśmy zacząć budować teorię obliczeń na nim. Taki matematyczny opis działania komputera to właśnie model obliczeń.

W przypadku „ZX Spectrum” opis działania komputera musiałby uwzględniać organizację pamięci operacyjnej, strukturę procesora i jego operacje, oraz funkcje wejścia/wyjścia. To nie jest coś co można opisać łatwo, nawet w wypadku prostego komputera. Opis współczesnego komputera opartego o najnowocześniejsze rozwiązania technologiczne byłby jeszcze trudniejszy.

Pokazuje to, ze wybór „ZX Spectrum” na model obliczeń nie jest najszczęśliwszy. To dlatego, że nie jest on koncepcyjnie prosty. Dlatego musimy poszukiwać jakiegoś łatwiejszego.

Maszyna Turinga

Alan Turing (1912-1954)
Zobacz biografię

Maszyna Turinga została zaproponowana jako model „dowolnego możliwego obliczenia” przez Alana Turinga w 1936 roku. Czyli na całe dekady przed pojawieniem się pierwszego urządzenia, które moglibyśmy współcześnie nazwać komputerem. Powstała ona jako notacja do wyrażania algorytmów i służyła (głównie logikom) do określenia, jakie problemy są możliwe do algorytmicznego rozwiązania.

Maszyna Turinga jest bardzo prostym modelem komputera, który składa się z:

  • nieograniczonej taśmy podzielonej na komórki, w których są zapisane zrozumiałe dla maszyny symbole.
  • głowicy, która może się przesuwać po taśmie oraz odczytywać i zapisywać na niej symbole.
  • mechanizmu sterującego, który może być w różnych stanach (ale skończenie wielu), który decyduje o działaniu maszyny. Na podstawie bieżącego stanu i symbolu znajdującego się pod głowicą podejmuje decyzje o:
    • zmianie zawartości komórki taśmy znajdującej się pod głowicą.
    • przesunięciu głowicy w lewo lub w prawo. Ponieważ taśma jest nieograniczona (czyli potencjalnie nieskończona), zawsze można wykonać przesunięcie.
    • zmianie stanu mechanizmu sterującego.

Zaskakująco prosty opis maszyny liczącej w porównaniu do tego, który musielibyśmy napisać, żeby opisać działanie „ZX Spectrum”.

Definicja formalna

Aby móc stworzyć formalną teorię obliczeń na maszynach Turinga potrzebujemy matematycznego opisu. Jest wiele różnych definicji formalnych i każda z nich mogłaby konkurować o miano najlepszej. Musimy jednak wybrać którąś z nich. W związku z tym proponujemy następującą:

Definicja 1

Maszyna Turinga , to siódemka: M = , gdzie:

to skończony zbiór stanów maszyny.
to skończony zbiór symboli wejściowych, które służą do reprezentacji wejścia maszyny i są zapisane na taśmie przed rozpoczęciem obliczenia.
to skończony zbiór symboli taśmowych - są to wszystkie symbole jakie mogą się znajdować na taśmie. Oczywiście .
to symbol pusty - specjalny symbol taśmowy nie należący do symboli wejściowych. Symbol pusty będzie zawsze wypełniał prawie całą taśmę.
to funkcja przejścia. Jest to funkcja częściowa prowadząca z w . Wartość oznacza, że maszyna będąca w stanie i czytając symbol z taśmy przejdzie do stanu , zapisze symbol na taśmie i przesunie głowicę o jedną komórkę w lewo () lub w prawo ().
to stan początkowy w jakim znajduje się maszyna przed rozpoczęciem obliczenia.
to zbiór stanów akceptujących będący podzbiorem . Obliczenie maszyny kończy się kiedy osiągnięty zostanie któryś ze stanów .

Działanie

Jak zatem uruchomić formalnie zdefiniowaną maszynę Turinga? Najpierw trzeba odpowiednio przygotować taśmę - można rozważać różne reprezentacje wejścia, ale w dalszych rozważaniach będziemy zakładać, że taśma jest wypełniona symbolami pustymi oprócz skończonego spójnego fragmentu, na którym znajduje się słowo wejściowe składające się z symboli wejściowych.

Następnie należy ustawić głowicę nad którąś z komórek taśmy - tu znowu można zastosować różne podejścia, ale dla wygody będziemy ustawiać głowicę nad pierwszą komórką słowa wejściowego. Pozostaje już tylko ustawić mechanizm sterujący na stan i uruchomić maszynę.

Maszyna będzie działać zgodnie z algorytmem zapisanym w funkcji - będzie zmieniać swój stan, przesuwać głowicę i zmieniać zawartość taśmy. Tak będzie sią działo dopóki nie nastąpi jeden z dwóch warunków:

  • Maszyna znajdzie się w stanie akceptującym. Mówimy wtedy, że obliczenie zakończyło się akceptująco.
  • Maszyna znajdując się w stanie przeczyta z taśmy symbol , a wartość funkcji częściowej nie będzie zdefiniowana. Mówimy wtedy, że obliczenie zakończyło się błędem.

Może się również zdarzyć, że nigdy żaden z tych dwóch warunków nie nastąpi. W takim wypadku maszyna nie zakończy obliczenia.

Reprezentacja

Zanim przyjrzymy się przykładom konkretnych maszyn Turinga realizujących konkretne zadania przedstawimy dwa sposoby reprezentacji maszyn.

Pierwszy polega na przedstawieniu tabelki funkcji . Możemy po prostu zapisywać w kolejnych wierszach ciągi oznaczające . Zazwyczaj nie jest wtedy potrzebne dokładne definiowanie pozostałych części maszyny. Symbolami taśmowymi są po prostu symbole występujące w tabelce, a dla symbolu pustego używa się standardowej notacji . To, które symbole są symbolami wejściowymi też zazwyczaj wynika z kontekstu i nie budzi wątpliwości. Dla oznaczenia stanów akceptujących można użyć pogrubienia. Jedynie określenie stanu początkowego wymaga dodatkowego komentarza do tabelki.

Można też przedstawić maszynę w wygodny sposób na diagramie. Każdy ze stanów maszyny reprezentujemy rysując prostokąt z nazwą stanu zapisaną wewnątrz prostokąta. Dla przejrzystości oznaczamy stany końcowe przez pogrubienie nazwy stanu.

Następnie łączymy prostokąty strzałkami etykietowanymi trzema symbolami - dwoma symbolami taśmowymi i symbolem lub . Strzałka etykietowana prowadząca od stanu do stanu oznacza .

Przykład 2 [Maszyna dodająca dwie liczby w systemie unarnym]

Diagram maszyny dodającej dwie liczby


Możemy teraz przedstawić pierwszą maszynę Turinga. Będzie ona dodawać dwie liczby zapisane w systemie unarnym. Liczba naturalna jest reprezentowana w systemie unarnym przez jedynek zapisanych na taśmie obok siebie.

Zakładamy, że na wejściu maszyny znajdą się dwie liczby naturalne i zapisane unarnie oddzielone pojedynczym zerem. Po zakończeniu działania maszyny na taśmie powinna być zapisana liczba . W związku z tym, językiem wejściowym maszyny będzie . Maszyna będzie miała 4 stany , stanem początkowym będzie , a jedynym stanem akceptującym będzie .

Język maszyny. Języki rekurencyjne i rekurencyjnie przeliczalne

Maszyna z przykładu wykonywała bardzo pożyteczne zadanie. Dla określonego wejścia po zakończeniu działania pozostawiała na taśmie wynik dodawania. Można się domyślać, że inne działania arytmetyczne również można zakodować w algorytmie maszyny Turinga. Zachęcamy do zaprojektowania takiego kalkulatora. Czasem jednak jest całkiem nieistotne co maszyna pozostawia na taśmie, a interesuje nas tylko czy i w jaki sposób kończy swoje działanie.

Definicja 3

Językiem maszyny nazwiemy zbiór tych słów wejściowych, dla których obliczenie maszyny kończy się w stanie akceptującym. Będziemy mówić, że rozpoznaje język .

Definicja 4

Język nazywamy rekurencyjnie przeliczalnym, albo częściowo rozstrzygalnym, jeżeli istnieje taka maszyna , że .

Dlaczego język jest tylko częściowo rozstrzygalny? Ponieważ jeżeli słowo , to da się to sprawdzić - należy uruchomić maszynę na słowie i zostanie ono zaakceptowane. Natomiast jeżeli , to niekoniecznie da się to sprawdzić. Możemy oczywiście uruchomić na , ale jeżeli to obliczenie nigdy się nie kończy, to nigdy nie dowiemy się czy akceptuje .

Żeby uchwycić własność pełnej rozstrzygalności definiujemy własność stopu dla maszyny Turinga.

Definicja 5

Mówimy, że ma własność stopu, jeżeli dla dowolnego słowa obliczenie na się kończy. Język nazywamy rekurencyjnym, lub rozstrzygalnym, jeżeli istnieje maszyna Turinga z własnością stopu taka, że .

Własności i różnice pomiędzy językami rozstrzygalnymi i częściowo rozstrzygalnymi są bardzo ciekawe, ale świadomie nie będziemy się nimi tu zajmować. Prawie wszystkie języki z którymi się spotkamy w czasie tego kursu będą rozstrzygalne.

Przykład 6 [Maszyna rozpoznająca język ]

Diagram maszyny rozpoznającej język

Przedstawimy teraz drugą maszynę Turinga, której zadaniem jest rozpoznanie konkretnego języka:


                        


gdzie oznacza słowo z odwróconą kolejnością liter.

Specyfikacja problemu narzuca język wejściowy  . Maszyna, którą zaprezentujemy będzie miała 7 stanów . Stan będzie stanem początkowym, a jedynym stanem akceptującym będzie stan .

Ćwiczenia

Ćwiczenie 7 [Język maszyny przykładowej


Udowodnij, że maszyna z przykładu rzeczywiście rozpoznaje język .

Podpowiedź
Rozwiązanie


Ćwiczenie 8 [Mnożenie liczb unarnych]

Skonstruuj maszynę analogiczną do maszyny dodającej, która wykona mnożenie dwóch liczb zapisanych unarnie.

Podpowiedź
Rozwiązanie


Ćwiczenie 9 [Źle ustawiona głowica]

Załóżmy, że głowica nie byłaby ustawiana na początku słowa wejściowego, tylko w dowolnym miejscu na taśmie. Pokaż, że można napisać program maszyny Turinga, który „znajdzie” początek słowa wejściowego i ustawi tam głowicę.

Załóż, że maszyna pracuje nad alfabetem oraz, że słowo wejściowe jest niepuste.

Podpowiedź
Podpowiedź
Rozwiązanie


Ćwiczenie 10 [Obliczenie z „czystą” taśmą]


Pokaż, że jeżeli maszyna rozpoznaje język , to można ją zmodyfikować tak, żeby nowa maszyna również rozpoznawała język , ale po zakończeniu jej działania taśma była w całości wypełniona symbolem pustym.

Podpowiedź
Rozwiązanie


Ćwiczenie 11 [Suma i przecięcie języków rozstrzygalnych]

Pokaż, że jeżeli języki i są rozstrzygalne, to języki i są rozstrzygalne.

Podpowiedź
Rozwiązanie

Zapis programu i stanu maszyny

Bardzo ciekawą i istotną własnością jest to, że opis dowolnej maszyny Turinga można zapisać na taśmie. Takiego kodowania maszyny na taśmie można dokonać na wiele różnych sposobów. Przyjrzymy się jednemu z nich.

Zauważmy, że dla działania maszyny nie są istotne „nazwy” elementów ze zbioru i . Możemy zatem założyć, że są to kolejne liczby naturalne. Wtedy do opisu maszyny wystarczy zapisać:

1. - liczbę elementów w zbiorze . Dalej zakładamy, że .

2. - liczbę elementów w zbiorze .

3. - liczbę elementów w zbiorze . Wygodnie jest założyć, że numeracja w pokrywa się z tą w . Dzięki temu nie trzeba rozróżniać tych dwóch numeracji.

4. - numer symbolu pustego.

5. - liczbę zdefiniowanych wartości funkcji .

6. Następnie piątek liczb naturalnych , , , , oznaczających, że
     , gdy .
     , gdy .

Możemy zatem zapisać te liczby w systemie unarnym oddzielając je pojedynczymi zerami i potraktować wynikowy napis jako słowo wejściowe nad alfabetem wejściowym . Bardzo istotne jest, że słowo to ma skończoną długość - będziemy z tej skończonej reprezentacji nieraz korzystać.

Ćwiczenia

Ćwiczenie 12 [Konfiguracja maszyny]

Podobnie jak zapisaliśmy maszynę jako słowo wejściowe nad alfabetem , możemy w podobny sposób zakodować opis sytuacji w jakiej znajduje się obliczenie maszyny w dowolnej chwili.

Przedstaw takie kodowanie tego opisu.

Podpowiedź
Rozwiązanie

Zasoby potrzebne do obliczenia maszyny

Przy projektowaniu algorytmów komputerowych bardzo istotna jest ilość czasu i pamięci potrzebnych do ich wykonania. Dla maszyn Turinga można bardzo łatwo badać zużycie czasu i pamięci.

Definicja 13

Czas obliczenia maszyny na konkretnym słowie wejściowym - to liczba kroków wykonanych zanim maszyna się zatrzymała. Jeżeli nigdy się nie zatrzyma, to mówimy, że czas obliczenia jest nieskończony i zapisujemy .

Możemy też zdefiniować czas działania samej maszyny.

Definicja 14

Funkcja jest złożonością czasową dla maszyny , jeżeli

Odpowiada to intuicji, że jest równe czasowi wystarczającemu do obliczenia na dowolnym -literowym słowie wejściowym. Zauważmy, że dla maszyny bez własności stopu nie można podać złożoności czasowej.

Wprowadzamy również podobne definicje dla pamięci wymaganej dla obliczenia związane z liczbą komórek taśmy użytych podczas obliczenia.

Definicja 15

Pamięć potrzebną do obliczenia maszyny na słowie - definiujemy jako liczbę komórek taśmy, które zostały odwiedzone przez głowicę zanim maszyna się zatrzymała. Jeżeli nie zatrzymuje się na , to wartość jest nieokreślona.

Definicja 16

Mówimy, że funkcja jest złożonością pamięciową maszyny z własnością stopu, jeżeli

Dzięki założeniu o własności stopu dla maszyny wszystkie wartości są dobrze określone, a jest równe pamięci wystarczającej do wykonania obliczenia na dowolnym -literowym słowie wejściowym.

Ćwiczenia

Ćwiczenie 17 [Czas i pamięć potrzebna przykładowym maszynom]

Spróbuj określić złożoność czasową i pamięciową dla przykładowych maszyn - dodającej i rozpoznającej język .

Podpowiedź
Rozwiązanie

Wielotaśmowa maszyna Turinga

Wielotaśmowa maszyna Turinga


Interesującym rozszerzeniem modelu maszyny Turinga jest dodanie do jej mechanizmu dodatkowych taśm. -taśmowa maszyna Turinga różni się od zwykłej maszyny Turinga tym, że ma niezależnych głowic, które poruszają się po różnych taśmach - każda z nich jest nieograniczona. W nowym modelu, mechanizm sterujący podejmuje decyzje na podstawie aktualnego stanu i odczytów ze wszystkich głowic. Dokonuje zapisów i przesunięć na każdej z taśm niezależnie. Co więcej, o ile w przypadku zwykłych maszyn Turinga wymagaliśmy przesunięcia głowicy, to teraz pozwalamy, żeby głowice pozostawały na swoich miejscach.

Żeby sformalizować sposób podawania wejścia do maszyny wielotaśmowej zakładamy, że słowo wejściowe jest zapisane na pierwszej taśmie, a pozostałe taśmy są w całości wypełnione symbolami pustymi. Natomiast definicje akceptacji i zakończenia obliczenia z błędem pozostają takie same jak w przypadku zwykłej maszyny Turinga.

Maszyna off-line

Maszyna off-line jest z kolei zawężeniem modelu maszyny wielotaśmowej. Modyfikacja polega na tym, że maszynie off-line nie wolno dokonywać zmian taśmy wejściowej. Rozważa się też maszyny off-line z taśmą wyjściową - wtedy dodatkowym ograniczeniem jest to, że głowica na ostaniej taśmie może tylko zapisywać symbole i przesuwać się tylko w prawo. Taki model odpowiada sytuacji w której program ma wejście i wyjście na osobnych taśmach, a pozostałe taśmy pełnią funkcję pamięci roboczej.

Złożoność

O ile definicje związane ze złożonością czasową zwykłej maszyny Turinga można bez zastrzeżeń stosować do maszyn wielotaśmowych, to definicje użytej pamięci wymagają pewnego komentarza. W przypadku zwykłej maszyny wielotaśmowej licząc liczbę komórek używanych podczas obliczenia sumujemy liczby użytych komórek na każdej z taśm.

W przypadku maszyn off-line do komórek używanych zaliczamy tylko komórki z taśm roboczych - nie uwzględniamy przy sumowaniu komórek taśmy wejściowej i wyjściowej (jeżeli taka istnieje). Takie podejście pozwala badać bardzo ciekawe obliczenia z pamięcią mniejszą niż rozmiar danych wejściowych.

Ćwiczenia

Ćwiczenie 18 [Definicje funkcji przejścia]

Sformalizuj definicję funkcji przejścia dla -taśmowej maszyny Turinga w wersji normalnej i off-line.

Podpowiedź
Rozwiązanie


Ćwiczenie 19 [Symulacja maszyny -taśmowej]

Pokaż, że dla języka rozpoznawanego przez -taśmową maszynę Turinga o złożoności czasowej da się skonstruować zwykłą maszynę Turinga o złożoności czasowej .

Podpowiedź
Rozwiązanie


Ćwiczenie 20 [Symulacja na maszynie off-line]

Pokaż jak zasymulować -taśmową maszynę Turinga na -taśmowej maszynie off-line.

Podpowiedź
Rozwiązanie

Niedeterministyczna maszyna Turinga

Najciekawszym i bardzo istotnym dla dalszej części wykładu rozszerzeniem modelu maszyny Turinga jest wprowadzenie niedeterminizmu do funkcji przejścia. Niedeterministyczna maszyna Turinga to taka, dla której mechanizm sterujący może przy konkretnym stanie i odczycie z taśmy postąpić na kilka różnych sposobów.

Definicja 21

Niedeterministyczna maszyna Turinga, to maszyna Turinga, w której funkcja przejścia jest częściową funkcją wielowartościową:

Na niedeterministyczną maszynę Turinga można patrzeć jak na automat zachowujący się losowo - podając słowo na wejście maszyny nie wiemy jakich wyborów dokona mechanizm sterujący, jeżeli będzie miał możliwość wykonania różnych przejść. Nie jest to jednak podejście najlepsze. Żeby zrozumieć różnicę podamy teraz definicję akceptacji słowa przez niedeterministyczną maszynę Turinga.

Definicja 22

Mówimy, że niedeterministyczna maszyna akceptuje słowo jeżeli istnieje taki ciąg przejść, który kończy się stanem akceptującym.

Taka definicja akceptacji powoduje, że zamiast traktować niedeterministyczne maszyny jak maszyny zachowujące się losowo, lepiej patrzeć na nie jak na maszyny, które sprawdzają wszystkie możliwości postępowania. To podejście pozwala lepiej wyobrazić sobie potencjał obliczeniowy, jaki jest ukryty w niedeterminizmie.

Pytanie o to jak dużą moc obliczeniową zyskuje się wprowadzając niedeterminizm jest kluczowym dla teorii złożoności i jest istotą sławnego problemu , który omówimy dokładnie w dalszej części kursu.

Przykład 23 [Drzewo możliwych wykonań]

Drzewo możliwych wykonań z zaznaczonymi wykonaniami akceptującymi

Przyjrzyjmy się teraz diagramowi przykładowej niedeterministycznej maszyny Turinga. Można zauważyć, że niedeterminizm pojawia się w stanie . Maszyna będąc w stanie i czytając z taśmy symbol może zarówno:
  • pozostawić na taśmie i przesunąć głowicę w prawo nie zmieniając stanu.
  • zamienić na , przesunąć się w prawo i zmienić stan na .

Podobnie reakcja maszyny na symbol może być dwojaka.

Żeby zobrazować działanie niedeterministycznej maszyny Turinga można narysować drzewo możliwych wykonań. W korzeniu drzewa zapisujemy stan początkowy maszyny, a od każdego wierzchołka reprezentującego stan obliczenia rysujemy strzałkę do kolejnych możliwych stanów.

Na drzewie zaznaczyliśmy ścieżkę, która prowadzi do akceptacji kolorem zielonym, a obliczenia, które prowadzą do odrzucenia słowa na czerwono. Zauważmy, że jest tylko jedna ścieżka akceptująca i każde odejście od niej prowadzi do odrzucenia słowa.

Złożoność

Wprowadzenie definicji złożoności czasowej i pamięciowej dla niedeterministycznej maszyny Turinga nastręcza pewnych trudności. Jest kilka podejść do tego zagadnienia, a subtelne różnice są zazwyczaj pomijane w literaturze. My zdecydowaliśmy się na najbardziej wymagającą definicję.

Przede wszystkim definiujemy, że niedeterministyczna maszyna zatrzymuje się na słowie , kiedy żaden z możliwych scenariuszy obliczenia nie jest nieskończony.

Definicja 24

Czas i pamięć zużytą przez maszynę , która zatrzymuje się na słowie definiujemy następująco:

  • Czas wykonania jako liczbę kroków najdłuższego z możliwych obliczeń.
  • Pamięć potrzebną do obliczenia jako maksimum z liczby komórek potrzebnych w każdym możliwym scenariuszu obliczenia.

Zauważmy, że czas wykonania odpowiada wysokości drzewa możliwych wykonań.

Definicje miary złożoności czasowej i pamięciowej maszyny niedeterministycznej są analogiczne do tych dla zwykłych maszyn. Są one określone dla maszyn z własnością stopu i dla długości są równe maksimum z czasu i pamięci potrzebnej do wykonania po wszystkich słowach wejściowych tej długości.

Ćwiczenia

Ćwiczenie 25 [Symulacja maszyny niedeterministycznej na maszynie deterministycznej]

Pokaż, że jeżeli język jest rozpoznawany przez niedeterministyczną maszynę Turinga w czasie , to istnieje deterministyczna maszyna Turinga rozpoznająca ten sam język w czasie dla pewnej stałej .

Podpowiedź
Rozwiązanie


Ćwiczenie 26 [Symulacja maszyny niedeterministycznej -taśmowej na -taśmowej]

Pokaż, że język rozpoznawany przez -taśmową niedeterministyczną maszynę Turinga w czasie jest również rozpoznawany przez -taśmową niedeterministyczną maszynę Turinga w czasie .

Podpowiedź
Rozwiązanie

Testy końcowe