Złożoność obliczeniowa/Wykład 1: Obliczenia w modelu maszyny Turinga: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:17, 11 wrz 2023

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 $M$ , to siódemka: M = $(Q, Σ, Γ, #, δ, q_{0}, F)$ , gdzie:

Q

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

Σ \subseteq Γ

.

#

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

Q \times Γ

w

Q \times Γ \times {\leftarrow, \to}

. Wartość

δ (A, x) = (B, y, K)

oznacza, że maszyna będąca w stanie

A

i czytając symbol

x

z taśmy przejdzie do stanu

B

, zapisze symbol

y

na taśmie i przesunie głowicę o jedną komórkę w lewo (

K = \leftarrow

) lub w prawo (

K = \to

).

q_{0}

to stan początkowy w jakim znajduje się maszyna przed rozpoczęciem obliczenia.

F

to zbiór stanów akceptujących będący podzbiorem

Q

. Obliczenie maszyny kończy się kiedy osiągnięty zostanie któryś ze stanów

F

.

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 $q_{0}$ 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 $A$ przeczyta z taśmy symbol $x$ , a wartość funkcji częściowej $δ (A, x)$ 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 $A, x : B, y, K$ oznaczające $δ (A, x) = (B, y, K)$ . 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 $\leftarrow$ lub $\to$ . Strzałka etykietowana $x, y, K$ prowadząca od stanu $A$ do stanu $B$ oznacza $δ (A, x) = (B, y, K)$ .

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

Możemy teraz przedstawić pierwszą maszynę Turinga. Będzie ona dodawać dwie liczby zapisane w systemie unarnym. Liczba naturalna

n

jest reprezentowana w systemie unarnym przez

n + 1

jedynek zapisanych na taśmie obok siebie.

Zakładamy, że na wejściu maszyny znajdą się dwie liczby naturalne $n$ i $m$ zapisane unarnie oddzielone pojedynczym zerem. Po zakończeniu działania maszyny na taśmie powinna być zapisana liczba $n + m$ . W związku z tym, językiem wejściowym maszyny będzie $Σ = {0, 1}$ . Maszyna będzie miała 4 stany $Q = {A, B, C, D}$ , stanem początkowym będzie $A$ , a jedynym stanem akceptującym będzie $D$ .

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 $M$ nazwiemy $L (M) \subseteq Σ^{*}$ zbiór tych słów wejściowych, dla których obliczenie maszyny $M$ kończy się w stanie akceptującym. Będziemy mówić, że $M$ rozpoznaje język $L (M)$ .

Definicja 4

Język $L \subseteq Σ^{*}$ nazywamy rekurencyjnie przeliczalnym, albo częściowo rozstrzygalnym, jeżeli istnieje taka maszyna $M$ , że $L = L (M)$ .

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

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

Definicja 5

Mówimy, że $M$ ma własność stopu, jeżeli dla dowolnego słowa $w \in Σ^{*}$ obliczenie $M$ na $w$ się kończy. Język $L \subseteq Σ^{*}$ nazywamy rekurencyjnym, lub rozstrzygalnym, jeżeli istnieje maszyna Turinga $M$ z własnością stopu taka, że $L = L (M)$ .

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 $w w^{\leftarrow}$ ]

Diagram maszyny rozpoznającej język $w w^{\leftarrow}$

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

${w w^{\leftarrow} : w \in {0, 1} *}$

gdzie $w^{\leftarrow}$ oznacza słowo $w$ z odwróconą kolejnością liter.

Specyfikacja problemu narzuca język wejściowy $Σ = {0, 1}$ . Maszyna, którą zaprezentujemy będzie miała 7 stanów $Q = {A, B, C, D, E, F, G}$ . Stan $A$ będzie stanem początkowym, a jedynym stanem akceptującym będzie stan $G$ .

Ćwiczenia

Ćwiczenie 7 [Język maszyny przykładowej

Udowodnij, że maszyna z przykładu rzeczywiście rozpoznaje język $w w^{\leftarrow}$ .

Podpowiedź

Rozwiązanie

Zauważmy, że jedynym stanem akceptującym jest stan $G$ , a jedyne przejście do stanu $G$ pochodzi ze stanu $A$ przy symbolu $#$ . Ponieważ stan $A$ jest stanem początkowym, oznacza to, że aby maszyna zaakceptowała niepuste słowo $x$ musi ona powrócić jeszcze choć raz do stanu $A$ . Przyglądając się ścieżkom, które umożliwiają powrót do stanu $A$ dochodzimy do wniosku, że maszyna $A$ akceptuje słowa postaci:

$x$ jest słowem pustym.

$x = 0 y 0$ lub $x = 1 y 1$ , gdzie $A$ akceptuje słowo $y$ .

Przeprowadzimy teraz dowód indukcyjny ze względu na długość słowa $x$ , że $x$ należy do języka maszyny wtedy i tylko wtedy, gdy $x = w w^{\leftarrow}$ dla pewnego $w$ .

Dla długości równej $0$ teza jest trywialna. Krok indukcyjny dowodzimy dla $x$ o długości większej od zera. Słowo $x$ należące do języka maszyny nie jest zatem słowem pustym i jest postaci $0 y 0$ lub $1 y 1$ , a $y$ jest postaci $v v^{\leftarrow}$ . To z kolei jest równoważne $x = (0 v) (0 v)^{\leftarrow}$ lub $x = (1 v) (1 v)^{\leftarrow}$ .

Ć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

Przedstawimy maszynę, która po kolei zrealizuje etapy obliczenia:

1. skróci zapis pierwszej liczby o jedną jedynkę i przejdzie na koniec wejścia:

\begin{aligned} A, 1 & : B, #, \to \\ B, 1 & : B, 1, \to \\ B, 0 & : B, 0, \to \end{aligned}

2. dopisze reprezentację liczby $0$ , czyli jedną jedynkę za wejściem i przejdzie z powrotem na początek wejścia:

\begin{aligned} B, # & : C, 0, \to \\ C, # & : D, 1, \leftarrow \\ D, 0 & : D, 0, \leftarrow \\ D, 1 & : D, 1, \leftarrow \\ D, # & : E, #, \to \end{aligned}

3. dopóki pierwsza liczba wejścia nie zostanie całkiem zamazana będzie zamazywać jedną komórkę i przechodzić do drugiej liczby:

\begin{aligned} E, 1 & : F, #, \to \\ F, 1 & : F, 1, \to \\ F, 0 & : G, 0, \to \end{aligned}

4. i dopisywać ją do wyniku:

\begin{aligned} G, 1 & : H, *, \to \\ H, 1 & : I, *, \to \\ I, 1 & : I, 1, \to \\ I, 0 & : I, 0, \to \\ I, # & : J, 1, \leftarrow \\ J, 1 & : J, 1, \leftarrow \\ J, 0 & : K, 0, \leftarrow \\ K, 1 & : L, 1, \leftarrow \\ L, * & : H, *, \to \\ K, * & : M, 1, \leftarrow \\ M, * & : M, 1, \leftarrow \\ M, 0 & : M, 0, \leftarrow \\ M, 1 & : M, 1, \leftarrow \\ M, # & : E, #, \to \end{aligned}

5. a jeżeli liczba jest już zamazana, to usunie też drugą liczbę i pozostawi sam wynik:

\begin{aligned} E, 0 & : N, #, \to \\ N, 1 & : N, #, \to \\ N, 0 & : 𝐙, #, \to \end{aligned}

Ć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 $Σ = {0, 1}$ oraz, że słowo wejściowe jest niepuste.

Podpowiedź

Dodaj dodatkowy symbol do alfabetu $Γ$ , którego użyjesz jako znacznika miejsc odwiedzonych w poszukiwaniu słowa wejściowego. Nie zapomnij na końcu usunąć znaczników z taśmy!

Rozwiązanie

Przedstawimy maszynę, która używa dodatkowego symbolu $* \in Γ$ na oznaczenie komórek już odwiedzonych przez głowicę. Maszyna rozpoczyna w stanie $A$ i poszerza odwiedzony obszar z lewej i z prawej strony aż znajdzie słowo wejściowe. Kiedy w końcu trafi na komórkę zawierającą $0$ lub $1$ , to usuwa wszystkie $*$ z taśmy i ustawia się na początku słowa wejściowego w stanie $Z$ .

\begin{aligned} A, # & : B, *, \to \\ B, * & : B, *, \to \\ B, # & : C, *, \leftarrow \\ C, * & : C, *, \leftarrow \\ C, # & : B, *, \to \\ A, 0 & : D, 0, \leftarrow \\ A, 1 & : D, 1, \leftarrow \\ D, 0 & : D, 0, \leftarrow \\ D, 1 & : D, 1, \leftarrow \\ D, * & : D, #, \leftarrow \\ D, # & : 𝐙, #, \to \\ E, * & : E, #, \to \\ E, 0 & : D, 0, \leftarrow \\ E, 1 & : D, 1, \leftarrow \\ B, 0 & : F, 0, \leftarrow \\ B, 1 & : F, 0, \leftarrow \\ F, * & : F, *, \leftarrow \\ F, # & : E, #, \to \\ A, 0 & : G, 0, \to \\ A, 1 & : G, 1, \to \\ G, * & : G, *, \to \\ G, # & : D, #, \leftarrow \end{aligned}

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

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

Podpowiedź

Zmodyfikuj alfabet $Γ$ tak, żeby dało się stwierdzić które komórki mogły być odwiedzone podczas obliczenia.

Rozwiązanie

Zauważmy, że po zakończeniu obliczenia $M$ musimy zamienić wszystkie wystąpienia symboli innych niż $#$ . Kłopot może sprawić to, że ciągi takich symboli mogą być oddzielone od siebie znakami pustymi i nie wiadomo, czy na lewo (lub na prawo) od danej pozycji są jeszcze symbole inne niż $#$ .

Zmodyfikujemy teraz działanie maszyny $M$ dodając nowy symbol taśmowy $*$ , który będzie miał znaczenie „to jest symbol pusty zapisany na taśmie przez maszynę $M$ ”. Musimy zmienić funkcję $δ$ tak, żeby czytając znak $*$ zachowywała się dokładnie tak samo, jak gdyby przeczytała $#$ . Jednocześnie za każdym razem kiedy funkcja $δ$ wskazywała, że należy zapisać na taśmie symbol $#$ , teraz należy zapisać symbol $*$ .

Ta modyfikacja nie zmienia języka rozpoznawanego przez $M$ , gdyż możemy patrzeć na wystąpienia symbolu $*$ jak na wystąpienia $#$ i wtedy całe obliczenie wygląda tak samo.

Musimy teraz „wykryć” zakończenie obliczenia maszyny i przejść do specjalnego stanu „czyszczącego-akceptującego” lub „czyszczącego-błędnego”. Wszystkie przejścia do stanów akceptujących modyfikujemy tak, żeby przechodziły do „czyszczącego-akceptującego”. Z kolei wszystkie niezdefiniowane przejścia ustawiamy tak, żeby prowadziły do stanu „czyszczącego-błędnego”.

Zauważmy, że dla nowej maszyny ciąg symboli różnych od $#$ jest spójny - są to wszystkie komórki taśmy, nad którymi znajdowała się maszyna podczas obliczenia. Możemy w związku z tym odnaleźć jego początek (korzystając na przykład z maszyny zdefiniowanej w poprzednim ćwiczeniu, choć w tym wypadku zadanie jest łatwiejsze) i zamazać wszystkie symbole aż do końca.

Kiedy taśma jest już pusta możemy przejść do stanu akceptującego lub umyślnie wykonać błąd w zależności od tego, czy dokonaliśmy czyszczenia „akceptującego”, czy „błędnego”.

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

Pokaż, że jeżeli języki $L_{1} \in Σ^{*}$ i $L_{2} \in Σ^{*}$ są rozstrzygalne, to języki $L_{1} \cap L_{2}$ i $L_{1} \cup L_{2}$ są rozstrzygalne.

Podpowiedź

Użyj maszyn $M_{1}$ i $M_{2}$ z własnością stopu rozpoznających języki $L_{1}$ i $L_{2}$ . Stwórz alfabet nowej maszyny $Γ = Σ \cup Γ_{1} \times Γ_{2}$ z alfabetów obu maszyn. Zamień symbol wejściowy $a$ na symbol $(a, a)$ . Możesz teraz tak uruchomić odpowiednio zmodyfikowane maszyny $M_{1}$ i $M_{2}$ , aby ich obliczenia nawzajem na siebie nie „zachodziły”.

Rozwiązanie

Postępujemy zgodnie z podpowiedzią i używając maszyn z własnością stopu $M_{1}$ i $M_{2}$ rozpoznających odpowiednio $L_{1}$ i $L_{2}$ definiujemy nową maszynę $M$ , która ma zasymulować uruchomienie obu maszyn na tym samym wejściu.

Alfabetem symboli taśmowych będzie $Γ = Σ \cup Γ_{1} \times Γ_{2}$ . Symbolem pustym jest teraz $(#_{1}, #_{2})$ .

Dokonujemy modyfikacji maszyn $M_{1}$ i $M_{2}$ , tak żeby po zakończeniu ich działania taśma była pusta oprócz jednej komórki zawierającej symbol 1 jeżeli słowo zostało zaakceptowane, lub 0 jeżeli zostało odrzucone (jest to prosta modyfikacja pomysłu wykorzystanego w poprzednim ćwiczeniu).

Następnie wprowadzamy dalsze modyfikacje tak, żeby maszyna $M_{1}$ w swoim obliczeniu korzystała tylko z pierwszej współrzędnej alfabetu taśmowego. Po prostu produkcję $δ_{1} (A, x) = (B, y, K)$ zamieniamy na zbiór produkcji postaci $δ (A, (x, g)) = (B, (y, g), K)$ po wszystkich $g \in Γ_{2}$ . Podobną modyfikację wykonujemy dla drugiej maszyny.

Wiemy, że maszyny $M_{1}$ i $M_{2}$ miały własność stopu. Ich modyfikacje nie zmieniły tego faktu. Możemy w związku z tym skonstruować maszynę $M$ z własnością stopu, która po kolei:

przepisuje litery słowa wejściowego $a \in Σ$ na pary $(a, a)$ .

wraca na początek słowa i uruchamia zmodyfikowaną wersję maszyny $M_{1}$ .

odszukuje początek słowa na drugich współrzędnych i uruchamia zmodyfikowaną wersję maszyny $M_{2}$ .

po zakończeniu obliczenia obu maszyn co najwyżej dwie komórki na taśmie są niepuste. Maszyna może osobno odczytać wynik na pierwszej współrzędnej i osobno na drugiej. W zależności od tego, czy $M$ miało rozpoznawać sumę, czy przecięcie języków, maszyna przechodzi do stanu akceptującego gdy jeden, lub oba obliczenia pozostawiły po sobie 1 zapisaną na taśmie.

Zauważmy, że tej samej metody nie można zastosować do skonstruowania maszyny rozpoznającej sumę języków częściowo rozstrzygalnych. W takim przypadku obliczenie zmodyfikowanej maszyny $M_{1}$ może się nigdy nie zakończyć dla słów należących do $M_{2}$ . Aby rozwiązać takie zadanie będziemy musieli użyć innych technik.

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 $Q$ . Możemy zatem założyć, że są to kolejne liczby naturalne. Wtedy do opisu maszyny wystarczy zapisać:

1. $q$ - liczbę elementów w zbiorze $Q$ . Dalej zakładamy, że $Q = {0, 1, \dots, q - 1}$ .

2. $s$ - liczbę elementów w zbiorze $Σ$ .

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

4. $s \leq b < g$ - numer symbolu pustego.

5. $d$ - liczbę zdefiniowanych wartości funkcji $δ$ .

6. Następnie $d$ piątek liczb naturalnych $A < q$ , $X < g$ , $B < q$ , $Y < g$ , $K \in {0, 1}$ oznaczających, że
$δ (A, X) = (B, Y, \leftarrow)$ , gdy $K = 0$ .
$δ (A, X) = (B, Y, \to)$ , gdy $K = 1$ .

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 ${0, 1}$ . 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 ${0, 1}$ , 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

Zauważmy, że zawartość taśmy, mimo że jest potencjalnie nieskończona, to w każdym momencie obliczenia wymagane jest opisanie tylko skończonej liczby komórek - wiemy, że pozostałe są wypełnione symbolem pustym. Możemy zatem zapisać ciąg liczb w systemie unarnym pooddzielanych zerami:

$q$ - numer stanu w którym znajduje się maszyna

$t$ - liczba komórek taśmy, które wymagają opisu

Następnie ciąg $T$ składający się z $t$ liczb, gdzie liczba $T_{i}$ oznacza numer symbolu z $Γ$ , który jest zapisany w $i$ -tej komórce.

$h$ - numer komórki w ciągu $T$ nad którą znajduje się głowica.

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 $M$ na konkretnym słowie wejściowym $w$ - $T (M, w)$ to liczba kroków wykonanych zanim maszyna się zatrzymała. Jeżeli $M$ nigdy się nie zatrzyma, to mówimy, że czas obliczenia jest nieskończony i zapisujemy $T (M, w) = \infty$ .

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

Definicja 14

Funkcja $f : ℕ \to ℕ$ jest złożonością czasową dla maszyny $M$ , jeżeli

\forall_{n \in ℕ} : f (n) = m a x {T (M, w) : w \in Σ^{n}}

Odpowiada to intuicji, że $f (n)$ jest równe czasowi wystarczającemu do obliczenia na dowolnym $n$ -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 $M$ na słowie $w$ - $S (M, w)$ definiujemy jako liczbę komórek taśmy, które zostały odwiedzone przez głowicę zanim maszyna się zatrzymała. Jeżeli $M$ nie zatrzymuje się na $w$ , to wartość $S (M, w)$ jest nieokreślona.

Definicja 16

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

\forall_{n \in ℕ} : f (n) = m a x {S (M, w) : w \in Σ^{n}}

Dzięki założeniu o własności stopu dla maszyny $M$ wszystkie wartości są dobrze określone, a $f (n)$ jest równe pamięci wystarczającej do wykonania obliczenia $M$ na dowolnym $n$ -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 $w w^{\leftarrow}$ .

Podpowiedź

	Złożoność czasowa	Złożoność pamięciowa
Maszyna dodająca	$f (0) = 1$ $f (1) = 3$ $f (n) = n + 3; n \geq 2$	$f (0) = 2$ $f (1) = 3$ $f (n) = n + 1; n \geq 2$
Maszyna rozpoznająca $w w^{\leftarrow}$	$f (n) = 6 + 8 + \dots + (n + 3) + 2; n = 2 k + 1$ $f (n) = 5 + 7 + \dots + (n + 3) + 1; n = 2 k$	$f (n) = n + 1$

Rozwiązanie

Żeby określić złożoność czasową i pamięciową maszyny dodającej wystarczy zauważyć, że maszyna czytając dowolny ciąg $n$ zer i jedynek przesunie się $n$ razy w prawo (dochodząc do $n + 1$ pozycji na której jest zero), a potem cofnie się co najwyżej trzy razy (o ile są dwie jedynki na końcu). Ponieważ dla słów krótszych niż $2$ -znakowe niemożliwe są dwie jedynki na końcu, a możliwe jest wycofanie głowicy przed słowo wejściowe - należy te przypadki rozważyć osobno. Otrzymuje się wyniki podane w podpowiedzi.

Analiza maszyny rozpoznającej język $w w^{\leftarrow}$ jest prostsza (mimo, że maszyna jest bardziej skomplikowana), ponieważ nie występują przypadki brzegowe. Złożoność pamięciowa wynosi $n + 1$ , gdyż maszyna używa zawsze dokładnie $n + 1$ pierwszych komórek.

Złożoność czasowa wynika w rekurencyjnego wzoru $f (n) = n + 3 + f (n - 2)$ z bazą $f (0) = 1$ i $f (1) = 2$ . Rozwiązaniem rekursji dla $n \geq 2$ jest:

\begin{aligned} f (n) = \frac{n - 1}{2} (6 + \frac{n + 3}{2}); n = 2 k + 1 \\ f (n) = \frac{n}{2} (5 + \frac{n + 3}{2}); n = 2 k \end{aligned}

Jak widać, nawet dla prostych maszyn oszacowanie dokładnych wartości złożoności czasowej i pamięciowej przysparza sporych kłopotów. Dlatego prawie nigdy nie będziemy rozważać dokładnych wartości tych funkcji i będziemy szeroko korzystać z notacji $𝒪$ .

Wielotaśmowa maszyna Turinga

Interesującym rozszerzeniem modelu maszyny Turinga jest dodanie do jej mechanizmu dodatkowych taśm.

k

-taśmowa maszyna Turinga różni się od zwykłej maszyny Turinga tym, że ma

k

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 $k$ -taśmowej maszyny Turinga w wersji normalnej i off-line.

Podpowiedź

Przyjrzyj się definicji zwykłej maszyny Turinga i zmodyfikuj jej argumenty i wynik tak, żeby można było wyrazić dostęp do $k$ taśm. Który element jest niepotrzebny w wypadku maszyny off-line?

Rozwiązanie

Formalna definicja funkcji przejścia dla $k$ -taśmowej maszyny Turinga musi zależeć od stanu i odczytu ze wszystkich $k$ taśm i decydować o zmianie stanu i wszystkich $k$ głowic. W związku z tym ma postać:

δ : Q \times Γ^{k} \to Q \times (Γ \times {\leftarrow, ∙, \to})^{k}

Wersja off-line nie może dokonywać zapisu na pierwszej taśmie, stąd funkcja przyjmuje postać:

δ : Q \times Γ^{k} \to Q \times {\leftarrow, ∙, \to} \times (Γ \times {\leftarrow, ∙, \to})^{k - 1}

Wersja off-line z taśmą wyjściową dodatkowo nie może dokonywać odczytów z ostatniej taśmy. W związku z tym funkcja przyjmuje postać:

δ : Q \times Γ^{k - 1} \to Q \times {\leftarrow, ∙, \to} \times (Γ \times {\leftarrow, ∙, \to})^{k - 2} \times Γ \times {∙, \to}

Ćwiczenie 19 [Symulacja maszyny $k$ -taśmowej]

Pokaż, że dla języka rozpoznawanego przez $k$ -taśmową maszynę Turinga $M_{(k)}$ o złożoności czasowej $𝒪 (f (n))$ da się skonstruować zwykłą maszynę Turinga $M$ o złożoności czasowej $𝒪 (f (n)^{2})$ .

Podpowiedź

Wykorzystaj pomysł z ćwiczenia o sumie i przecięciu języków rekurencyjnych, aby zakodować zawartość $k$ -taśm na jednej taśmie. Użyj kopii alfabetu taśmowego do zaznaczenia pozycji głowicy na każdej z taśm.

Rozwiązanie

Zakładamy, że maszyna $M_{(k)}$ została zmodyfikowana tak jak w ćwiczeniu o „czystym” obliczeniu i używa symbolu $*$ do oznaczenia komórek z symbolem pustym zapisanym podczas obliczenia. Pozwoli to określić które fragmenty taśmy zawierają „istotne” informacje.

Maszyna $M$ będzie pracować przy alfabecie wejściowym $Σ = Σ_{(k)}$ i taśmowym $Γ = Σ_{k} \cup {(Γ_{(k)} \cup \underline{Γ_{(k)}})}^{k}$ . Gdzie $\underline{Γ_{(k)}} = {\underline{A} : A \in Γ_{(k)}}$ jest kopią alfabetu taśmowego, a symbol $\underline{A}$ oznacza, że na taśmie jest symbol $A$ i głowica znajduje się nad tą właśnie komórką.

Stany Maszyny $M$ to $Q = Q_{(k)} \cup Q_{(k)} \times {(Γ_{(k)} \cup {⊔})}^{k}$ . Stany z $Q_{(k)}$ będą odpowiadać stanom maszyny $M_{(k)}$ , a stany $(q, A_{1}, A_{2}, \dots, A_{k})$ sytuacji w której maszyna $M_{(k)}$ jest stanie $q$ , a na taśmie $k$ pod głowicą jest $A_{k}$ . Symbolu $⊔$ na $i$ -tej pozycji używamy, kiedy jeszcze nie wiemy co jest pod głowicą na $i$ -tej taśmie.

Maszyna $M$ będzie działać w następujący sposób:

przepisze wejście z wartości $a$ na $(\underline{a}, \underline{#}, \dots, \underline{#})$ w wypadku pierwszego symbolu i $(a, #, #, \dots, #)$ w wypadku pozostałych.

będąc w stanie odpowiadającym stanowi $q$ maszyny $M_{(k)}$ i na lewym końcu taśmy (do znalezienia lewego końca taśmy używamy symboli $*$ i metody z ćwiczenia o ,,czystym obliczeniu)

przejdzie do stanu $(q, ⊔, ⊔, \dots, ⊔)$ i przeglądnie zawartość taśmy aż do prawego końca uzupełniając informację w stanie. Tzn. kiedy napotkana zostanie komórka z symbolem $(x_{1}, \dots, \underline{x_{i}}, \dots, x_{k})$ , to w stanie $(q, A_{1}, \dots, A_{i}, \dots, A_{k})$ wartość na $i$ -tej współrzędnej stanu zmienia się z $⊔$ na $x_{i}$ .

Posiadając już pełną informację o odczytach ze wszystkich taśm dokona jeszcze jednego przeglądnięcia taśmy w którym zostaną zmienione symbole taśmowe (na każdej ze współrzędnych osobno zgodnie z programem maszyny $M_{(k)}$ .

Jeżeli maszyna $M_{(k)}$ działa dla wejścia rozmiaru $n$ w czasie $𝒪 (f (n))$ , to działanie maszyny $M$ zakończy się po wykonaniu $𝒪 (f (n))$ pętli przeglądających całą używaną taśmę. Wykonanie pojedynczej pętli odbywa się w czasie proporcjonalnym do długości użytej części taśmy. Tą z kolei możemy ograniczyć do $𝒪 (f (n))$ komórek na lewo i $𝒪 (f (n))$ komórek na prawo od pozycji początkowej - gdyż żadna z głowic w czasie $𝒪 (f (n))$ nie może pokonać większej odległości. W związku z tym otrzymujemy oszacowanie $𝒪 (f (n)^{2})$ na złożoność czasową wynikowej maszyny.

Ćwiczenie 20 [Symulacja na maszynie off-line]

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

Podpowiedź

Rozwiązanie

Używając konstrukcji pozwalającej zasymulować $k$ -taśmową maszynę Turinga na jednotaśmowej można całe obliczenie przeprowadzić na drugiej taśmie maszyny off-line. Wystarczy skopiować słowo wejściowej z pierwszej taśmy do odpowiednio przygotowanych komórek drugiej taśmy.

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ą:

δ : Q \times Γ \to 𝒫 (Q \times Γ \times {\leftarrow, \to})

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 $M$ akceptuje słowo $w$ 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 $P vs N P$ , 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

A

. Maszyna będąc w stanie

A

i czytając z taśmy symbol

0

może zarówno:

pozostawić $0$ na taśmie i przesunąć głowicę w prawo nie zmieniając stanu.

zamienić $0$ na $1$ , przesunąć się w prawo i zmienić stan na $B$ .

Podobnie reakcja maszyny na symbol $1$ 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 $M$ zatrzymuje się na słowie $w$ , kiedy żaden z możliwych scenariuszy obliczenia nie jest nieskończony.

Definicja 24

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

Czas wykonania $N T (M, w)$ jako liczbę kroków najdłuższego z możliwych obliczeń.

Pamięć potrzebną do obliczenia $N S (M, w)$ 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 $n$ 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 $L$ jest rozpoznawany przez niedeterministyczną maszynę Turinga w czasie $𝒪 (f (n))$ , to istnieje deterministyczna maszyna Turinga rozpoznająca ten sam język w czasie $𝒪 (c^{f (n)})$ dla pewnej stałej $c$ .

Podpowiedź

Rozwiązanie

Niech $d = m a x_{A \in Q, x \in Γ} | δ (A, x) |$ . Zauważmy, że $d$ jest maksymalnym stopniem rozgałęzienia, jaki może wystąpić w drzewie możliwych obliczeń maszyny.

Mając dany ciąg $x$ o długości $m$ liczb z przedziału $[1, d]$ możemy zdeterminować działanie maszyny w następujący sposób: W $i$ -tym kroku wykonania wybieramy $x_{i}$ -te z dostępnych przejść. Jeżeli obliczenie kończy się w mniej niż $m$ krokach to ciąg $x$ wyznacza działanie maszyny. Jeżeli obliczenie nie kończy się w pierwszych $m$ krokach, to będziemy musieli sprawdzić dłuższe ciągi $x$ .

Nasza maszyna będzie $4$ -taśmową maszyną deterministyczną. Pierwsza taśma będzie zawsze przechowywać słowo wejściowe. Druga taśma będzie zawierać ciąg determinujący obliczenie niedeterministyczne. Na trzeciej taśmie będzie się odbywać symulacja. Czwarta taśma z kolei będzie służyć do przechowywania specjalnego znacznika. Maszyna będzie działać w następujący sposób, że dla kolejnych liczb naturalnych $m$ :

usunie znaczniki z czwartej taśmy.

przeglądnie wszystkie ciągi $x$ długości $m$ liczb z przedziału $[1, d]$ zapisując je na drugiej taśmie i dla każdego z nich:

skopiuje zawartość pierwszej taśmy na trzecią taśmę i uruchomi tam zdeterminowany przy pomocy ciągu $x$ program niedeterministycznej maszyny.

jeżeli obliczenie się nie zakończyło w ciągu pierwszych $m$ kroków, to zaznaczy ten fakt zapisując specjalny symbol na czwartej taśmie.

wyczyści trzecią taśmę używając techniki „czystego” obliczenia.

Jeżeli którekolwiek ze zdeterminowanych obliczeń zakończy się akceptacją, to maszyna akceptuje słowo wejściowe. Jeżeli dla jakiejś liczby $m$ wszystkie obliczenia się zakończą (a więc nie będzie odpowiedniego znacznika na czwartej taśmie), to obliczenie powinno się zakończyć z błędem.

Tak skonstruowana maszyna rozpoznaje ten sam język co zadana maszyna niedeterministyczna. Jeżeli słowo $w$ należy do języka, to ciąg wyborów $x$ , który o tym świadczy zostanie w końcu przeglądnięty i słowo zaakceptowane. Należy zwrócić uwagę, że obliczenie nie zostanie wcześniej przerwane z błędem, gdyż prefiksy $x$ zapewnią kontynuację obliczeń.

Jeżeli natomiast słowo $x$ nie należy do języka, to przy $m = f (| x |)$ wszystkie możliwe scenariusze wykonania muszą się zakończyć i w związku z tym obliczenie zostanie przerwane z błędem.

Czas działania tak powstałej maszyny dla słowa wejściowego długości $n$ możemy oszacować przez:

\sum_{i = 1}^{f (n)} 𝒪 (i) d^{i} \leq \sum_{i = 1}^{f (n)} 𝒪 ({(2 d)}^{i}) = 𝒪 ((2 d)^{f (n) + 1}) = 𝒪 (e^{f (n)})

dla pewnej stałej $e$ .

Możemy teraz użyć symulacji $4$ -taśmowej maszyny Turinga działającej w czasie $𝒪 (e^{f (n)})$ na jednotaśmowej maszynie w czasie $𝒪 ((e^{f (n)})^{2})$ , czyli $𝒪 (c^{f (n)})$ dla $c = e^{2}$ .

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

Pokaż, że język rozpoznawany przez $k$ -taśmową niedeterministyczną maszynę Turinga $M$ w czasie $𝒪 (f (n))$ jest również rozpoznawany przez $2$ -taśmową niedeterministyczną maszynę Turinga w czasie $𝒪 (f (n))$ .

Podpowiedź

Użyj niedeterminizmu do wylosowania obliczenia akceptującego na $k$ -taśmowej maszynie, a następnie sprawdź, że wylosowałeś poprawną ścieżkę obliczeń.

Rozwiązanie

Niech $d$ oznacza tak jak poprzednio $m a x_{A \in Q, x \in Γ} | δ (A, x) |$ .

Maszyna $2$ -taśmowa, którą skonstruujemy będzie działać w następujący sposób, że na drugiej taśmie zapisze ciąg grup : $k$ symboli z $Γ$ i jedna liczba z przedziału $[1, d]$ . Znaczenie $i$ -tej grupy postaci $(x_{1}, x_{2}, \dots, x_{k}, w)$ jest takie, że w obliczeniu akceptującym maszyny $M$ w $i$ -tym kroku z $k$ taśm są wczytane symbole $x_{1}, x_{2}, \dots, x_{k}$ , a maszyna wybiera $w$ -te z dostępnych przejść.

Zauważmy, że taki ciąg wyznacza jednoznacznie zachowanie maszyny - znamy stan początkowy, a każda grupa wyznacza następny stan maszyny.

Aby skonstruować naszą maszynę chcemy mieć możliwość sprawdzenia, czy taki arbitralny ciąg może rzeczywiście wystąpić. Możemy wykonać takie sprawdzenie symulując za każdym razem tylko jedną z $k$ taśm na pierwszej taśmie konstruowanej maszyny $2$ -taśmowej. Taka symulacja musi sprawdzić, czy rzeczywiście odczyt z $i$ -tej taśmy w kroku $j$ jest taki jak przewiduje to scenariusz zapisany na drugiej taśmie.

Widać już, że możemy skonstruować maszynę, która generuje przy pomocy przejść niedeterministycznych ciąg opisujący całe obliczenie, a następnie sprawdza, że jest to rzeczywiście możliwy ciąg odczytów z taśmy. Kiedy sprawdzone obliczenie prowadzi do stanu akceptującego, to maszyna akceptuje słowo wejściowe.

Jedyny problem jaki pozostał to metoda niedeterministycznego generowania ciągu grup. Ponieważ nie chcemy uzależniać metody od funkcji $f (n)$ zastosujemy następujące podejście, że będziemy generować po kolei ciągi o długości kolejnych potęg $2$ . Zaczniemy od ciągu długości $1$ . Potem za każdym razem jeżeli obliczenie kodowane przez poprzedni ciąg się nie zakończyło, ale ciąg był poprawny, to wydłużamy go dwukrotnie.

Takie podejście zapewnia, że o ile słowo $x$ należało do języka maszyny, to obliczenie o tym świadczące zostanie odkryte przez naszą nową maszynę.

Jeśli natomiast $x$ nie należy do języka, to żadne z obliczeń nie prowadzi do akceptacji, a kiedy długość testowanych ciągów przekroczy $f (| x |)$ to każde z obliczeń się kończy i dłuższe ciągi nie będą już testowane.

Czas działania nowej maszyny dla słowa długości $n$ jest proporcjonalny do

\sum_{i = 0}^{[\log f (n)]} k 2^{i} \leq 4 k f (n) = 𝒪 (f (n))

Złożoność obliczeniowa/Wykład 1: Obliczenia w modelu maszyny Turinga: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:17, 11 wrz 2023

Spis treści

Wprowadzenie

Model obliczeń

Maszyna Turinga

Definicja formalna

Działanie

Reprezentacja

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

Ćwiczenia

Zapis programu i stanu maszyny

Ćwiczenia

Zasoby potrzebne do obliczenia maszyny

Ćwiczenia

Wielotaśmowa maszyna Turinga

Maszyna off-line

Złożoność

Ćwiczenia

Niedeterministyczna maszyna Turinga

Złożoność

Ćwiczenia

Testy końcowe

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 5: / Linia 5: @@
 * 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 rzeczywiście żaden ze znanych sposobów reprezentowania obliczeń nie potrafi przedstawić nic więcej niż maszyna Turinga.
+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.
@@ Linia 32: / Linia 33: @@
 ==Maszyna Turinga==
+[[grafika:Turing1.jpeg|thumb|right||Alan Turing (1912-1954)<br>[[Biografia Turinga|Zobacz biografię]]]]
-Uwaga do zespołu redakcyjnego: '''To chyba niezłe miejsce na biografię Alana Turinga.'''
 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.
@@ Linia 52: / Linia 49: @@
 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|[Maszyna Turinga <math>M</math>]||
+{{definicja|1||
 Maszyna Turinga <math>M</math>, to siódemka: M <nowiki>=</nowiki> <math>(Q,\Sigma,\Gamma,\#,\delta,q_0,F)</math>, gdzie:
@@ Linia 63: / Linia 60: @@
 :<math>\#</math> 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ę.
-:<math>\delta</math> to ''funkcja przejścia''. Jest to funkcja częściowa prowadząca z <math>Q \times \Gamma</math> w <math>Q \times Gamma \times \{\leftarrow,\rightarrow\}</math>. Wartość <math>\delta(A,x) = (B,y,K)</math> oznacza, że maszyna będąca w stanie <math>A</math> i czytając symbol <math>x</math> z taśmy przejdzie do stanu <math>B</math>, zapisze symbol <math>y</math> na taśmie i przesunie głowicę o jedną komórkę w lewo (<math>K = \leftarrow</math>) lub w prawo (<math>K = \rightarrow</math>).
+:<math>\delta</math> to ''funkcja przejścia''. Jest to funkcja częściowa prowadząca z <math>Q \times \Gamma</math> w <math>Q \times \Gamma \times \{\leftarrow,\rightarrow\}</math>. Wartość <math>\delta(A,x) = (B,y,K)</math> oznacza, że maszyna będąca w stanie <math>A</math> i czytając symbol <math>x</math> z taśmy przejdzie do stanu <math>B</math>, zapisze symbol <math>y</math> na taśmie i przesunie głowicę o jedną komórkę w lewo (<math>K = \leftarrow</math>) lub w prawo (<math>K = \rightarrow</math>).
 :<math>q_0</math> to ''stan początkowy'' w jakim znajduje się maszyna przed rozpoczęciem obliczenia.
@@ Linia 80: / Linia 77: @@
 * Maszyna znajdzie się w stanie akceptującym. Mówimy wtedy, że obliczenie zakończyło się akceptująco.
 * Maszyna znajdując się w stanie <math>A</math> przeczyta z taśmy symbol <math>x</math>, a wartość funkcji częściowej <math>\delta(A,x)</math> 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 nigdy nie zakończy obliczenia.
+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===
@@ Linia 88: / Linia 85: @@
 Pierwszy polega na przedstawieniu tabelki funkcji <math>\delta</math>. Możemy po prostu zapisywać w kolejnych wierszach ciągi <math>A,x: B,y,K</math> oznaczające <math>\delta(A,x) = (B,y,K)</math>. 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 <math>\#</math>. 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 podwójny prostokąt.
+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 <math>\leftarrow</math> lub <math>\rightarrow</math>. Strzałka etykietowana <math>x,y,K</math> prowadząca od stanu <math>A</math> do stanu <math>B</math> oznacza  <math>\delta(A,x) = (B,y,K)</math>.
-{{przyklad|[Maszyna dodająca dwie liczby w systemie unarnym]||
+{{przyklad|2 [Maszyna dodająca dwie liczby w systemie unarnym]||
-Możemy teraz przedstawić pierwszą maszynę Turinga. Będzie ona dodawać dwie liczby zapisane w systemie ''unarnym''. Liczba naturalna <math>n</math> jest reprezentowana w systemie unarnym przez <math>n+1</math> jedynek zapisanych na taśmie obok siebie.
-Zakładamy, że na wejściu maszyny znajdą się dwie liczby naturalne <math>n</math> i <math>m</math> zapisane unarnie oddzielone pojedynczym zerem. Po zakończeniu działania maszyny na taśmie powinna być zapisana liczba <math>n+m</math>. W związku z tym, językiem wejściowym maszyny będzie <math>\Sigma = \{0,1\}</math>. Maszyna będzie miała <math>4</math> stany <math>Q = \{A,B,C,D\}</math>, stanem początkowym będzie <math>A</math>, a jedynym stanem akceptującym będzie <math>D</math>.
 }}
-Rysunek: '''diagram maszyny dodającej dwie liczby - ZO-1.1'''
+[[grafika:ZO-1.1.gif|thumb|right||Diagram maszyny dodającej dwie liczby]]<br>Możemy teraz przedstawić pierwszą maszynę Turinga. Będzie ona dodawać dwie liczby zapisane w systemie ''unarnym''. Liczba naturalna <math>n</math> jest reprezentowana w systemie unarnym przez <math>n+1</math> jedynek zapisanych na taśmie obok siebie.
+Zakładamy, że na wejściu maszyny znajdą się dwie liczby naturalne <math>n</math> i <math>m</math> zapisane unarnie oddzielone pojedynczym zerem. Po zakończeniu działania maszyny na taśmie powinna być zapisana liczba <math>n+m</math>. W związku z tym, językiem wejściowym maszyny będzie <math>\Sigma = \{0,1\}</math>. Maszyna będzie miała '''4''' stany <math>Q = \{A,B,C,D\}</math>, stanem początkowym będzie <math>A</math>, a jedynym stanem akceptującym będzie <math>D</math>.
-Animacja: '''działanie maszyny dodającej dwie liczby - ZO-1.2'''
+[[File:ZO-1.2.mp4|250x250px|thumb|center| ]]
 ==Język maszyny. Języki rekurencyjne i rekurencyjnie przeliczalne==
@@ Linia 108: / Linia 102: @@
 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|[Język maszyny <math>M</math>]||
+{{definicja|3||
 Językiem maszyny <math>M</math> nazwiemy <math>L(M) \subseteq {\Sigma^\ast}</math> zbiór tych słów wejściowych, dla których obliczenie maszyny <math>M</math> kończy się w stanie akceptującym. Będziemy mówić, że <math>M</math> rozpoznaje język <math>L(M)</math>.
 }}
-{{definicja|||
+{{definicja|4||
 Język <math>L \subseteq {\Sigma^\ast}</math> nazywamy ''rekurencyjnie przeliczalnym'', albo ''częściowo rozstrzygalnym'', jeżeli istnieje taka maszyna <math>M</math>, że <math>L = L(M)</math>.
 }}
@@ Linia 120: / Linia 114: @@
 Żeby uchwycić własność pełnej rozstrzygalności definiujemy własność stopu dla maszyny Turinga.
-{{definicja|||
+{{definicja|5||
 Mówimy, że <math>M</math> ma ''własność stopu'', jeżeli dla dowolnego słowa <math>w \in {\Sigma^\ast}</math> obliczenie <math>M</math> na <math>w</math> się kończy. Język <math>L \subseteq {\Sigma^\ast}</math> nazywamy ''rekurencyjnym'', lub ''rozstrzygalnym'', jeżeli istnieje maszyna Turinga <math>M</math> z własnością stopu taka, że <math>L = L(M)</math>.
 }}
@@ Linia 126: / Linia 120: @@
 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.
-{{przyklad|[Maszyna rozpoznająca język <math>ww^\leftarrow</math>]||
+{{przyklad|6 [Maszyna rozpoznająca język <math>ww^\leftarrow</math>]||
+}}
-Przedstawimy teraz drugą maszynę Turinga, której zadaniem jest rozpoznanie konkretnego języka:
+[[grafika:ZO-1.3.gif|thumb|right||Diagram maszyny rozpoznającej język <math>ww^\leftarrow</math>]]Przedstawimy teraz drugą maszynę Turinga, której zadaniem jest rozpoznanie konkretnego języka:
-<center><math>{ww^\leftarrow : w \in \kleene{\{0,1\}}</math></center>
-, gdzie <math>w^\leftarrow</math> oznacza słowo <math>w</math> z odwróconą kolejnością liter.
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\{ww^\leftarrow : w \in \{0,1\}\ast\}
+</math>
-''Specyfikacja problemu narzuca język wejściowy <math>\Sigma = \{0,1\}</math>. Maszyna, którą zaprezentujemy będzie miała <math>7</math> stanów <math>Q = \{A,B,C,D,E,F,G\}</math>. Stan <math>A</math> będzie stanem początkowym, a jedynym stanem akceptującym będzie stan'' <math>G</math>.
+gdzie <math>w^\leftarrow</math> oznacza słowo <math>w</math> z odwróconą kolejnością liter.
-Rysunek: '''diagram maszyny rozpoznającej język <math>ww^\leftarrow</math>'''
+''Specyfikacja problemu narzuca język wejściowy &nbsp;<math>\Sigma = \{0,1\}</math>. Maszyna, którą zaprezentujemy będzie miała '''7''' stanów <math>Q = \{A,B,C,D,E,F,G\}</math>. Stan <math>A</math> będzie stanem początkowym, a jedynym stanem akceptującym będzie stan'' <math>G</math>.
+[[File:ZO-1.4.mp4|250x250|thumb|center| ]]
-Animacja: '''działanie maszyny rozpoznającej język <math>ww^\leftarrow</math>'''
+===Ćwiczenia===
+{{cwiczenie|7 [Język maszyny przykładowej||
 }}
-===Ćwiczenia===
-{{cwiczenie||
-Język maszyny przykładowej.
 Udowodnij, że maszyna z przykładu rzeczywiście rozpoznaje język <math>ww^\leftarrow</math>.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Przeprowadź dowód indukcyjny ze względu na długość słowa wejściowego.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Zauważmy, że jedynym stanem akceptującym jest stan <math>G</math>, a jedyne przejście do stanu <math>G</math> pochodzi ze stanu <math>A</math> przy symbolu <math>\#</math>. Ponieważ stan <math>A</math> jest stanem początkowym, oznacza to, że aby maszyna zaakceptowała niepuste słowo <math>x</math> musi ona powrócić jeszcze choć raz do stanu <math>A</math>. Przyglądając się ścieżkom, które umożliwiają powrót do stanu <math>A</math> dochodzimy do wniosku, że maszyna <math>A</math> akceptuje słowa postaci:
-[*]
-<math>x</math> jest słowem pustym.
-<math>x = 0y0</math> lub <math>x = 1y1</math>, gdzie <math>A</math> akceptuje słowo <math>y</math>.
+* <math>x</math> jest słowem pustym.
+* <math>x = 0y0</math> lub <math>x = 1y1</math>, gdzie <math>A</math> akceptuje słowo <math>y</math>.
 Przeprowadzimy teraz dowód indukcyjny ze względu na długość słowa <math>x</math>, że <math>x</math> należy do języka maszyny wtedy i tylko wtedy, gdy <math>x=ww^\leftarrow</math> dla pewnego <math>w</math>.
@@ Linia 165: / Linia 157: @@
 </div></div>
+{{cwiczenie|8 [Mnożenie liczb unarnych]||
 }}
-{{cwiczenie||
-Mnożenie liczb unarnych.
 Skonstruuj maszynę analogiczną do maszyny dodającej, która wykona mnożenie dwóch liczb zapisanych unarnie.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Skonstruuj maszynę odejmującą jeden od liczby zapisanej unarnie, a następnie połącz ją z maszyną dodającą.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Przedstawimy maszynę, która po kolei zrealizuje etapy obliczenia:
-Uwaga do zespołu redakcyjnego: '''Jeżeli jest taka możliwość, to tabelki przejść w jednym podpunkcie powinny się zwijać/rozwijać. Dzięki temu zapis będzie bardziej czytelny.'''
@@ Linia 185: / Linia 174: @@
 . skróci zapis pierwszej liczby o jedną jedynkę i przejdzie na koniec wejścia:
-<center><math>\aligned
+<center><math>\begin{align}
 A,1 &: B,\#,\rightarrow \\
 B,1 &: B,1,\rightarrow \\
 B,0 &: B,0,\rightarrow \\
-\endaligned</math></center>
+\end{align}</math></center>
 . dopisze reprezentację liczby <math>0</math>, czyli jedną jedynkę za wejściem i przejdzie z powrotem na początek wejścia:
-<center><math>\aligned
+<center><math>\begin{align}
 B,\# &: C,0,\rightarrow \\
 C,\# &: D,1,\leftarrow \\
@@ Linia 201: / Linia 190: @@
 D,\# &: E,\#,\rightarrow \\
-\endaligned</math></center>
+\end{align}</math></center>
 . dopóki pierwsza liczba wejścia nie zostanie całkiem zamazana będzie zamazywać jedną komórkę i przechodzić do drugiej liczby:
-<center><math>\aligned
+<center><math>\begin{align}
 E,1 &: F,\#,\rightarrow \\
 F,1 &: F,1,\rightarrow \\
 F,0 &: G,0,\rightarrow \\
-\endaligned</math></center>
+\end{align}</math></center>
 . i dopisywać ją do wyniku:
-<center><math>\aligned
+<center><math>\begin{align}
 G,1 &: H,*,\rightarrow \\
 H,1 &: I,*,\rightarrow \\
@@ Linia 230: / Linia 219: @@
 M,\# &: E,\#,\rightarrow \\
-\endaligned</math></center>
+\end{align}</math></center>
 . a jeżeli liczba jest już zamazana, to usunie też drugą liczbę i pozostawi sam wynik:
-<center><math>\aligned
+<center><math>\begin{align}
 E,0 &: N,\#,\rightarrow \\
 N,1 &: N,\#,\rightarrow \\
 N,0 &: \mathbf{Z},\#,\rightarrow
-\endaligned</math></center>
+\end{align}</math></center>
 </div></div>
+{{cwiczenie|9 [Źle ustawiona głowica]||
 }}
-{{cwiczenie||
+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ę.
-Ź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 <math>\Sigma = \{0,1\}</math> oraz, że słowo wejściowe jest niepuste.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
-Gdyby było wiadomo, że słowo znajduje się ,,na lewo'', lub ,,na prawo'' od pozycji początkowej głowicy, to wystarczyłoby skierować głowicę w odpowiednim kierunku. Ponieważ nie masz takiej informacji, to musisz przeglądać taśmę w obu kierunkach jednocześnie.
+Gdyby było wiadomo, że słowo znajduje się „na lewo”, lub „na prawo” od pozycji początkowej głowicy, to wystarczyłoby skierować głowicę w odpowiednim kierunku. Ponieważ nie masz takiej informacji, to musisz przeglądać taśmę w obu kierunkach jednocześnie.
+</div></div>
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Dodaj dodatkowy symbol do alfabetu <math>\Gamma</math>, którego użyjesz jako znacznika miejsc odwiedzonych w poszukiwaniu słowa wejściowego. Nie zapomnij na końcu usunąć znaczników z taśmy!
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Przedstawimy maszynę, która używa dodatkowego symbolu <math>* \in \Gamma</math> na oznaczenie komórek już odwiedzonych przez głowicę. Maszyna rozpoczyna w stanie <math>A</math> i poszerza odwiedzony obszar z lewej i z prawej strony aż znajdzie słowo wejściowe. Kiedy w końcu trafi na komórkę zawierającą <math>0</math> lub <math>1</math>, to usuwa wszystkie <math>*</math> z taśmy i ustawia się na początku słowa wejściowego w stanie <math>Z</math>.
-<center><math>\aligned
+<center><math>\begin{align}
 A,\# &: B,*,\rightarrow \\
 B,* &: B,*,\rightarrow \\
@@ Linia 283: / Linia 273: @@
 G,\# &: D,\#,\leftarrow
-\endaligned</math></center>
+\end{align}</math></center>
 </div></div>
+{{cwiczenie|10 [Obliczenie z „czystą” taśmą]||
 }}
-{{cwiczenie||
-Obliczenie z ,,czystą'' taśmą.
 Pokaż, że jeżeli maszyna <math>M</math> rozpoznaje język <math>L</math>, to można ją zmodyfikować tak, żeby nowa maszyna <math>M'</math> również rozpoznawała język <math>L</math>, ale po zakończeniu jej działania taśma była w całości wypełniona symbolem pustym.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Zmodyfikuj alfabet <math>\Gamma</math> tak, żeby dało się stwierdzić które komórki mogły być odwiedzone podczas obliczenia.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Zauważmy, że po zakończeniu obliczenia <math>M</math> musimy zamienić wszystkie wystąpienia symboli innych niż <math>\#</math>. Kłopot może sprawić to, że ciągi takich symboli mogą być oddzielone od siebie znakami pustymi i nie wiadomo, czy na lewo (lub na prawo) od danej pozycji są jeszcze symbole inne niż <math>\#</math>.
-Zmodyfikujemy teraz działanie maszyny <math>M</math> dodając nowy symbol taśmowy <math>*</math>, który będzie miał znaczenie ,,to jest symbol pusty zapisany na taśmie przez maszynę <math>M</math>''. Musimy zmienić funkcję <math>\delta</math> tak, żeby czytając znak <math>*</math> zachowywała się dokładnie tak samo, jak gdyby przeczytała <math>\#</math>. Jednocześnie za każdym razem kiedy funkcja <math>\delta</math> wskazywała, że należy zapisać na taśmie symbol <math>\#</math>, teraz należy zapisać symbol <math>*</math>.
+Zmodyfikujemy teraz działanie maszyny <math>M</math> dodając nowy symbol taśmowy <math>*</math>, który będzie miał znaczenie „to jest symbol pusty zapisany na taśmie przez maszynę <math>M</math>”. Musimy zmienić funkcję <math>\delta</math> tak, żeby czytając znak <math>*</math> zachowywała się dokładnie tak samo, jak gdyby przeczytała <math>\#</math>. Jednocześnie za każdym razem kiedy funkcja <math>\delta</math> wskazywała, że należy zapisać na taśmie symbol <math>\#</math>, teraz należy zapisać symbol <math>*</math>.
 Ta modyfikacja nie zmienia języka rozpoznawanego przez <math>M</math>, gdyż możemy patrzeć na wystąpienia symbolu <math>*</math> jak na wystąpienia <math>\#</math> i wtedy całe obliczenie wygląda tak samo.
-Musimy teraz ,,wykryć'' zakończenie obliczenia maszyny i przejść do specjalnego stanu ,,czyszczącego-akceptującego'' lub ,,czyszczącego-błędnego''. Wszystkie przejścia do stanów akceptujących modyfikujemy tak, żeby przechodziły do ,,czyszczącego-akceptującego''. Z kolei wszystkie niezdefiniowane przejścia ustawiamy tak, żeby prowadziły do stanu ,,czyszczącego-błędnego''.
+Musimy teraz „wykryć” zakończenie obliczenia maszyny i przejść do specjalnego stanu „czyszczącego-akceptującego” lub „czyszczącego-błędnego”. Wszystkie przejścia do stanów akceptujących modyfikujemy tak, żeby przechodziły do „czyszczącego-akceptującego”. Z kolei wszystkie niezdefiniowane przejścia ustawiamy tak, żeby prowadziły do stanu „czyszczącego-błędnego”.
 Zauważmy, że dla nowej maszyny ciąg symboli różnych od <math>\#</math> jest spójny - są to wszystkie komórki taśmy, nad którymi znajdowała się maszyna podczas obliczenia. Możemy w związku z tym odnaleźć jego początek (korzystając na przykład z maszyny zdefiniowanej w poprzednim ćwiczeniu, choć w tym wypadku zadanie jest łatwiejsze) i zamazać wszystkie symbole aż do końca.
-Kiedy taśma jest już pusta możemy przejść do stanu akceptującego lub umyślnie wykonać błąd w zależności od tego, czy dokonaliśmy czyszczenia ,,akceptującego'', czy ,,błędnego''.
+Kiedy taśma jest już pusta możemy przejść do stanu akceptującego lub umyślnie wykonać błąd w zależności od tego, czy dokonaliśmy czyszczenia „akceptującego”, czy „błędnego”.
 </div></div>
+{{cwiczenie|11 [Suma i przecięcie języków rozstrzygalnych]||
 }}
-{{cwiczenie||
-Suma i przecięcie języków rozstrzygalnych.
 Pokaż, że jeżeli języki <math>L_1 \in {\Sigma^\ast}</math> i <math>L_2 \in {\Sigma^\ast}</math> są rozstrzygalne, to języki <math>L_1 \cap L_2</math> i <math>L_1 \cup L_2</math> są rozstrzygalne.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
-Użyj maszyn <math>M_1</math> i <math>M_2</math> z własnością stopu rozpoznających języki <math>L_1</math> i <math>L_2</math>. Stwórz alfabet nowej maszyny <math>\Gamma = \Sigma \cup \Gamma_1 \times \Gamma_2</math> z alfabetów obu maszyn. Zamień symbol wejściowy <math>a</math> na symbol <math>(a,a)</math>. Możesz teraz tak uruchomić odpowiednio zmodyfikowane maszyny <math>M_1</math> i <math>M_2</math>, aby ich obliczenia nawzajem na siebie nie ,,zachodziły''.
+Użyj maszyn <math>M_1</math> i <math>M_2</math> z własnością stopu rozpoznających języki <math>L_1</math> i <math>L_2</math>. Stwórz alfabet nowej maszyny <math>\Gamma = \Sigma \cup \Gamma_1 \times \Gamma_2</math> z alfabetów obu maszyn. Zamień symbol wejściowy <math>a</math> na symbol <math>(a,a)</math>. Możesz teraz tak uruchomić odpowiednio zmodyfikowane maszyny <math>M_1</math> i <math>M_2</math>, aby ich obliczenia nawzajem na siebie nie „zachodziły”.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Postępujemy zgodnie z podpowiedzią i używając maszyn z własnością stopu <math>M_1</math> i <math>M_2</math> rozpoznających odpowiednio <math>L_1</math> i <math>L_2</math> definiujemy nową maszynę <math>M</math>, która ma zasymulować uruchomienie obu maszyn na tym samym wejściu.
@@ Linia 324: / Linia 315: @@
 Alfabetem symboli taśmowych będzie <math>\Gamma = \Sigma \cup \Gamma_1 \times \Gamma_2</math>. Symbolem pustym jest teraz <math>(\#_1,\#_2)</math>.
-Dokonujemy modyfikacji maszyn <math>M_1</math> i <math>M_2</math>, tak żeby po zakończeniu ich działania taśma była pusta oprócz jednej komórki zawierającej symbol <math>1</math> jeżeli słowo zostało zaakceptowane, lub <math>0</math> jeżeli zostało odrzucone (jest to prosta modyfikacja pomysłu wykorzystanego w poprzednim ćwiczeniu).
+Dokonujemy modyfikacji maszyn <math>M_1</math> i <math>M_2</math>, tak żeby po zakończeniu ich działania taśma była pusta oprócz jednej komórki zawierającej symbol '''1''' jeżeli słowo zostało zaakceptowane, lub '''0''' jeżeli zostało odrzucone (jest to prosta modyfikacja pomysłu wykorzystanego w poprzednim ćwiczeniu).
 Następnie wprowadzamy dalsze modyfikacje tak, żeby maszyna <math>M_1</math> w swoim obliczeniu korzystała tylko z pierwszej współrzędnej alfabetu taśmowego. Po prostu produkcję <math>\delta_1(A,x) = (B,y,K)</math> zamieniamy na zbiór produkcji postaci <math>\delta(A,(x,g)) = (B,(y,g),K)</math> po wszystkich <math>g \in \Gamma_2</math>. Podobną modyfikację wykonujemy dla drugiej maszyny.
 Wiemy, że maszyny <math>M_1</math> i <math>M_2</math> miały własność stopu. Ich modyfikacje nie zmieniły tego faktu. Możemy w związku z tym skonstruować maszynę <math>M</math> z własnością stopu, która po kolei:
-[*]
-przepisuje litery słowa wejściowego <math>a \in \Sigma</math> na pary <math>(a,a)</math>.
-wraca na początek słowa i uruchamia zmodyfikowaną wersję maszyny <math>M_1</math>.
+* przepisuje litery słowa wejściowego <math>a \in \Sigma</math> na pary <math>(a,a)</math>.
-odszukuje początek słowa na drugich współrzędnych i uruchamia zmodyfikowaną wersję maszyny <math>M_2</math>.
+* wraca na początek słowa i uruchamia zmodyfikowaną wersję maszyny <math>M_1</math>.
-po zakończeniu obliczenia obu maszyn co najwyżej dwie komórki na taśmie są niepuste. Maszyna może osobno odczytać wynik na pierwszej współrzędnej i osobno na drugiej. W zależności od tego, czy <math>M</math> miało rozpoznawać sumę, czy przecięcie języków, maszyna przechodzi do stanu akceptującego gdy jeden, lub oba obliczenia pozostawiły po sobie <math>1</math> zapisaną na taśmie.
+* odszukuje początek słowa na drugich współrzędnych i uruchamia zmodyfikowaną wersję maszyny <math>M_2</math>.
+* po zakończeniu obliczenia obu maszyn co najwyżej dwie komórki na taśmie są niepuste. Maszyna może osobno odczytać wynik na pierwszej współrzędnej i osobno na drugiej. W zależności od tego, czy <math>M</math> miało rozpoznawać sumę, czy przecięcie języków, maszyna przechodzi do stanu akceptującego gdy jeden, lub oba obliczenia pozostawiły po sobie '''1''' zapisaną na taśmie.
 Zauważmy, że tej samej metody nie można zastosować do skonstruowania maszyny rozpoznającej sumę języków częściowo rozstrzygalnych. W takim przypadku obliczenie zmodyfikowanej maszyny <math>M_1</math> może się nigdy nie zakończyć dla słów należących do <math>M_2</math>. Aby rozwiązać takie zadanie będziemy musieli użyć innych technik.
 </div></div>
-}}
 ==Zapis programu i stanu maszyny==
@@ Linia 347: / Linia 336: @@
 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 <math>\Gamma</math> i <math>Q</math>. Możemy zatem założyć, że są to kolejne liczby naturalne. Wtedy do opisu maszyny wystarczy zapisać:
+Zauważmy, że dla działania maszyny nie są istotne „nazwy” elementów ze zbioru <math>\Gamma</math> i <math>Q</math>. Możemy zatem założyć, że są to kolejne liczby naturalne. Wtedy do opisu maszyny wystarczy zapisać:
-[#]
-<math>q</math> - liczbę elementów w zbiorze <math>Q</math>. Dalej zakładamy, że <math>Q = \{0,1,\ldots,n-1\}</math>.
+. <math>q</math> - liczbę elementów w zbiorze <math>Q</math>. Dalej zakładamy, że <math>Q = \{0,1,\ldots,q-1\}</math>.
-<math>s</math> - liczbę elementów w zbiorze <math>\Sigma</math>.
+. <math>s</math> - liczbę elementów w zbiorze <math>\Sigma</math>.
-<math>g</math> - liczbę elementów w zbiorze <math>\Gamma</math>. Wygodnie jest założyć, że numeracja w <math>\Sigma \subseteq \Gamma</math> pokrywa się z tą w <math>\Gamma</math>. Dzięki temu nie trzeba rozróżniać tych dwóch numeracji.
+. <math>g</math> - liczbę elementów w zbiorze <math>\Gamma</math>. Wygodnie jest założyć, że numeracja w <math>\Sigma \subseteq \Gamma</math> pokrywa się z tą w <math>\Gamma</math>. Dzięki temu nie trzeba rozróżniać tych dwóch numeracji.
-<math>s \le b < g</math> - numer symbolu pustego.
+. <math>s \le b < g</math> - numer symbolu pustego.
-<math>d</math> - liczbę zdefiniowanych wartości funkcji <math>\delta</math>.
+. <math>d</math> - liczbę zdefiniowanych wartości funkcji <math>\delta</math>.
-Następnie <math>d</math> piątek liczb naturalnych <math>A < q</math>, <math>X < g</math>, <math>B < q</math>, <math>Y < g</math>, <math>K \in \{0,1\}</math> oznaczających, że
+. Następnie <math>d</math> piątek liczb naturalnych <math>A < q</math>, <math>X < g</math>, <math>B < q</math>, <math>Y < g</math>, <math>K \in \{0,1\}</math> oznaczających, że <br/>
-[*]
+&nbsp;&nbsp;&nbsp;&nbsp; <math>\delta(A,X) = (B,Y,\leftarrow)</math>, gdy <math>K=0</math>. <br/>
-<math>\delta(A,X) = (B,Y,\leftarrow)</math>, gdy <math>K=0</math>.
+&nbsp;&nbsp;&nbsp;&nbsp; <math>\delta(A,X) = (B,Y,\rightarrow)</math>, gdy <math>K=1</math>.
-<math>\delta(A,X) = (B,Y,\rightarrow)</math>, gdy <math>K=1</math>.
 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 <math>\{0,1\}</math>. Bardzo istotne jest, że słowo to ma skończoną długość - będziemy z tej skończonej reprezentacji nieraz korzystać.
 ===Ćwiczenia===
-{{cwiczenie||
+{{cwiczenie|12 [Konfiguracja maszyny]||
-Konfiguracja maszyny.
+}}
 Podobnie jak zapisaliśmy maszynę jako słowo wejściowe nad alfabetem <math>\{0,1\}</math>, możemy w podobny sposób zakodować opis sytuacji w jakiej znajduje się obliczenie maszyny w dowolnej chwili.
@@ Linia 375: / Linia 363: @@
 Przedstaw takie kodowanie tego opisu.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Dla zakodowania całego opisu obliczenia maszyny trzeba zapisać stan maszyny, zawartość taśmy i pozycję głowicy.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Zauważmy, że zawartość taśmy, mimo że jest potencjalnie nieskończona, to w każdym momencie obliczenia wymagane jest opisanie tylko skończonej liczby komórek - wiemy, że pozostałe są wypełnione symbolem pustym. Możemy zatem zapisać ciąg liczb w systemie unarnym pooddzielanych zerami:
-[*]
-<math>q</math> - numer stanu w którym znajduje się maszyna
-<math>t</math> - liczba komórek taśmy, które wymagają opisu
-Następnie ciąg <math>T</math> składający się z <math>t</math> liczb, gdzie liczba <math>T_i</math> oznacza numer symbolu z <math>\Gamma</math>, który jest zapisany w <math>i</math>-tej komórce.
+* <math>q</math> - numer stanu w którym znajduje się maszyna
+* <math>t</math> - liczba komórek taśmy, które wymagają opisu
+* Następnie ciąg <math>T</math> składający się z <math>t</math> liczb, gdzie liczba <math>T_i</math> oznacza numer symbolu z <math>\Gamma</math>, który jest zapisany w <math>i</math>-tej komórce.
-<math>h</math> - numer komórki w ciągu <math>T</math> nad którą znajduje się głowica.
+* <math>h</math> - numer komórki w ciągu <math>T</math> nad którą znajduje się głowica.
 </div></div>
-}}
 ==Zasoby potrzebne do obliczenia maszyny==
@@ Linia 395: / Linia 383: @@
 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|[Uzupelnij]||
+{{definicja|13||
 Czas obliczenia maszyny <math>M</math> na konkretnym słowie wejściowym <math>w</math> - <math>T(M,w)</math> to liczba kroków wykonanych zanim maszyna się zatrzymała. Jeżeli <math>M</math> nigdy się nie zatrzyma, to mówimy, że czas obliczenia jest nieskończony i zapisujemy <math>T(M,w) = \infty</math>.
 }}
@@ Linia 401: / Linia 389: @@
 Możemy też zdefiniować czas działania samej maszyny.
-{{definicja|[Uzupelnij]||
+{{definicja|14||
 Funkcja <math>f : \mathbb{N} \rightarrow \mathbb{N}</math> jest ''złożonością czasową'' dla maszyny <math>M</math>, jeżeli
+<center><math>
-{n  {N}}: f(n) <nowiki>=</nowiki> max  T(M,w) : w  ^n
+\forall_{n \in \mathbb{N}}: f(n) = max \{ T(M,w) : w \in \Sigma^n \}
+</math></center>
 }}
@@ Linia 412: / Linia 400: @@
 Wprowadzamy również podobne definicje dla pamięci wymaganej dla obliczenia związane z liczbą komórek taśmy użytych podczas obliczenia.
-{{definicja|[Uzupelnij]||
+{{definicja|15||
 Pamięć potrzebną do obliczenia maszyny <math>M</math> na słowie <math>w</math> - <math>S(M,w)</math> definiujemy jako liczbę komórek taśmy, które zostały odwiedzone przez głowicę zanim maszyna się zatrzymała. Jeżeli <math>M</math> nie zatrzymuje się na <math>w</math>, to wartość <math>S(M,w)</math> jest nieokreślona.
 }}
-{{definicja|[Uzupelnij]||
+{{definicja|16||
 Mówimy, że funkcja <math>f : \mathbb{N} \rightarrow \mathbb{N}</math> jest ''złożonością pamięciową'' maszyny <math>M</math> z własnością stopu, jeżeli
+<center><math>
-{n  {N}}: f(n) <nowiki>=</nowiki> max  S(M,w) : w  ^n
+\forall_{n \in \mathbb{N}}: f(n) = max \{ S(M,w) : w \in \Sigma^n \}
+</math></center>
+Dzięki założeniu o własności stopu dla maszyny <math>M</math> wszystkie wartości są dobrze określone, a <math>f(n)</math> jest równe pamięci wystarczającej do wykonania obliczenia <math>M</math> na dowolnym <math>n</math>-literowym słowie wejściowym.
 }}
-Dzięki założeniu o własności stopu dla maszyny <math>M</math> wszystkie wartości są dobrze określone, a <math>f(n)</math> jest równe pamięci wystarczającej do wykonania obliczenia <math>M</math> na dowolnym <math>n</math>-literowym słowie wejściowym.
 ===Ćwiczenia===
-{{cwiczenie||
+{{cwiczenie|17 [Czas i pamięć potrzebna przykładowym maszynom]||
-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 <math>ww^\leftarrow</math>.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
+{| border="1" cellspacing="0"
+! !! Złożoność czasowa !! Złożoność pamięciowa
+ |-
+ ! Maszyna dodająca || <math>f(0) = 1</math><br/><math>f(1) = 3</math><br/><math>f(n) = n+3; n\geq2</math> ||   <math>f(0) = 2</math><br/><math>f(1) = 3</math><br/><math>f(n) = n+1; n\geq2</math>
+ |-
+ ! Maszyna rozpoznająca <math>ww^\leftarrow</math>         || <math>f(n) = 6 + 8 + \ldots + (n+3) + 2 ; n=2k+1</math><br/><math>f(n) = 5 + 7 + \ldots + (n+3) + 1 ; n=2k</math> ||   <math>f(n) = n+1</math>
+|}
-{p{0.15}|p{0.4}|p{0.4}|}
+</div></div>
-& Złożoność czasowa & Złożoność pamięciowa <br>
-Maszyna dodająca &
-<math>f(0) = 1</math>
-<math>f(1) = 3</math>
-<math>f(n) = n+3; n\geq2</math>
-&
-<math>f(0) = 2</math>
-<math>f(1) = 3</math>
-<math>f(n) = n+1; n\geq2</math>
-<br>
-Maszyna rozpoznająca <math>ww^\leftarrow</math> &
-<math>f(n) = 6 + 8 + \ldots + (n+3) + 2 ; n=2k+1</math>
-<math>f(n) = 5 + 7 + \ldots + (n+3) + 1 ; n=2k</math>
-&
-<math>f(n) = n+1</math>
-<br>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Żeby określić złożoność czasową i pamięciową maszyny dodającej wystarczy zauważyć, że maszyna czytając dowolny ciąg <math>n</math> zer i jedynek przesunie się <math>n</math> razy w prawo (dochodząc do <math>n+1</math> pozycji na której jest zero), a potem cofnie się co najwyżej trzy razy (o ile są dwie jedynki na końcu). Ponieważ dla słów krótszych niż <math>2</math>-znakowe niemożliwe są dwie jedynki na końcu, a możliwe jest wycofanie głowicy przed słowo wejściowe - należy te przypadki rozważyć osobno. Otrzymuje się wyniki podane w podpowiedzi.
@@ Linia 464: / Linia 433: @@
 Złożoność czasowa wynika w rekurencyjnego wzoru <math>f(n) = n+3 + f(n-2)</math> z bazą <math>f(0) = 1</math> i <math>f(1) = 2</math>. Rozwiązaniem rekursji dla <math>n\geq2</math> jest:
-<center><math>\aligned
+<center><math>\begin{align}
 f(n) = \frac{n-1}{2}(6+\frac{n+3}{2}); n=2k+1\\
 f(n) = \frac{n}{2}(5+\frac{n+3}{2}); n=2k
-\endaligned</math></center>
+\end{align}</math></center>
 Jak widać, nawet dla prostych maszyn oszacowanie dokładnych wartości złożoności czasowej i pamięciowej przysparza sporych kłopotów. Dlatego prawie nigdy nie będziemy rozważać dokładnych wartości tych funkcji i będziemy szeroko korzystać z notacji <math>\mathcal{O}</math>.
 </div></div>
-}}
 ==Wielotaśmowa maszyna Turinga==
-Interesującym rozszerzeniem modelu maszyny Turinga jest dodanie do jej mechanizmu dodatkowych taśm. <math>k</math>-taśmowa maszyna Turinga różni się od zwykłej maszyny Turinga tym, że ma <math>k</math> 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.
+[[grafika:ZO-1.5.gif|thumb|right||Wielotaśmowa maszyna Turinga]]<br>Interesującym rozszerzeniem modelu maszyny Turinga jest dodanie do jej mechanizmu dodatkowych taśm. <math>k</math>-taśmowa maszyna Turinga różni się od zwykłej maszyny Turinga tym, że ma <math>k</math> 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.
-{
-{}{{}{1pt}{}{0pt}{}{0.12}{}{0.12}}
-Rysunek: '''wielotaśmowa maszyna Turinga'''
-}
 ===Maszyna off-line===
@@ Linia 500: / Linia 460: @@
 ===Ćwiczenia===
-{{cwiczenie||
+{{cwiczenie|18 [Definicje funkcji przejścia]||
-Definicje funkcji przejścia.
+}}
 Sformalizuj definicję funkcji przejścia dla <math>k</math>-taśmowej maszyny Turinga w wersji normalnej i off-line.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Przyjrzyj się definicji zwykłej maszyny Turinga i zmodyfikuj jej argumenty i wynik tak, żeby można było wyrazić dostęp do <math>k</math> taśm. Który element jest niepotrzebny w wypadku maszyny off-line?
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Formalna definicja funkcji przejścia dla <math>k</math>-taśmowej maszyny Turinga musi zależeć od stanu i odczytu ze wszystkich <math>k</math> taśm i decydować o zmianie stanu i wszystkich <math>k</math> głowic. W związku z tym ma postać:
-: Q  ^k  Q  (  , , )^k
+<center><math>\delta : Q \times \Gamma^k \rightarrow Q \times (\Gamma \times \{\leftarrow, \bullet, \rightarrow\})^k</math></center>
 Wersja off-line nie może dokonywać zapisu na pierwszej taśmie, stąd funkcja przyjmuje postać:
-: Q  ^k  Q  , ,   (  , , )^{k-1}
+<center><math>\delta : Q \times \Gamma^k \rightarrow Q \times \{\leftarrow, \bullet, \rightarrow\} \times (\Gamma \times \{\leftarrow, \bullet, \rightarrow\})^{k-1}</math></center>
 Wersja off-line z taśmą wyjściową dodatkowo nie może dokonywać odczytów z ostatniej taśmy. W związku z tym funkcja przyjmuje postać:
-: Q  ^{k-1}  Q  , ,   (  , , )^{k-2}    ,
+<center><math>\delta : Q \times \Gamma^{k-1} \rightarrow Q \times \{\leftarrow, \bullet, \rightarrow\} \times (\Gamma \times \{\leftarrow, \bullet, \rightarrow\})^{k-2} \times \Gamma \times \{\bullet, \rightarrow\}
+</math></center>
 </div></div>
-}}
-{{cwiczenie||
-Symulacja maszyny <math>k</math>-taśmowej.
+{{cwiczenie|19 [Symulacja maszyny <math>k</math>-taśmowej]||
+}}
 Pokaż, że dla języka rozpoznawanego przez <math>k</math>-taśmową maszynę Turinga <math>M_{(k)}</math> o złożoności czasowej <math>\mathcal{O}(f(n))</math> da się skonstruować zwykłą maszynę Turinga <math>M</math> o złożoności czasowej <math>\mathcal{O}(f(n)^2)</math>.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Wykorzystaj pomysł z ćwiczenia o sumie i przecięciu języków rekurencyjnych, aby zakodować zawartość <math>k</math>-taśm na jednej taśmie. Użyj kopii alfabetu taśmowego do zaznaczenia pozycji głowicy na każdej z taśm.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Zakładamy, że maszyna <math>M_{(k)}</math> została zmodyfikowana tak jak w ćwiczeniu o ,,czystym'' obliczeniu i używa symbolu <math>*</math> do oznaczenia komórek z symbolem pustym zapisanym podczas obliczenia. Pozwoli to określić które fragmenty taśmy zawierają ,,istotne'' informacje.
+Zakładamy, że maszyna <math>M_{(k)}</math> została zmodyfikowana tak jak w ćwiczeniu o „czystym” obliczeniu i używa symbolu <math>*</math> do oznaczenia komórek z symbolem pustym zapisanym podczas obliczenia. Pozwoli to określić które fragmenty taśmy zawierają „istotne” informacje.
 Maszyna <math>M</math> będzie pracować przy alfabecie wejściowym <math>\Sigma = \Sigma_{(k)}</math> i taśmowym <math>\Gamma = \Sigma_{k} \cup {(\Gamma_{(k)} \cup \underline{\Gamma_{(k)}})}^k</math>. Gdzie <math>\underline{\Gamma_{(k)}} = \{ \underline{A} : A \in \Gamma_{(k)}\}</math> jest kopią alfabetu taśmowego, a symbol <math>\underline{A}</math> oznacza, że na taśmie jest symbol <math>A</math> i głowica znajduje się nad tą właśnie komórką.
@@ Linia 539: / Linia 498: @@
 Maszyna <math>M</math> będzie działać w następujący sposób:
-[*]
-przepisze wejście z wartości <math>a</math> na <math>(\underline{a},\underline{\#},\ldots,\underline{\#})</math> w wypadku pierwszego symbolu i <math>(a,\#,\#,\ldots,\#)</math> w wypadku pozostałych.
-będąc w stanie odpowiadającym stanowi <math>q</math> maszyny <math>M_{(k)}</math> i na lewym końcu taśmy (do znalezienia lewego końca taśmy używamy symboli <math>*</math> i metody z ćwiczenia o ,,czystym'' obliczeniu)
+* przepisze wejście z wartości <math>a</math> na <math>(\underline{a},\underline{\#},\ldots,\underline{\#})</math> w wypadku pierwszego symbolu i <math>(a,\#,\#,\ldots,\#)</math> w wypadku pozostałych.
-przejdzie do stanu <math>(q,\sqcup,\sqcup,\ldots,\sqcup)</math> i przeglądnie zawartość taśmy aż do prawego końca uzupełniając informację w stanie. Tzn. kiedy napotkana zostanie komórka z symbolem <math>(x_1,\ldots,\underline{x_i},\ldots,x_k)</math>, to w stanie <math>(q,A_1,\ldots,A_i,\ldots,A_k)</math> wartość na <math>i</math>-tej współrzędnej stanu zmienia się z <math>\sqcup</math> na <math>x_i</math>.
+* będąc w stanie odpowiadającym stanowi <math>q</math> maszyny <math>M_{(k)}</math> i na lewym końcu taśmy (do znalezienia lewego końca taśmy używamy symboli <math>*</math> i metody z ćwiczenia o ,,czystym'' obliczeniu)
-Posiadając już pełną informację o odczytach ze wszystkich taśm dokona jeszcze jednego przeglądnięcia taśmy w którym zostaną zmienione symbole taśmowe (na każdej ze współrzędnych osobno zgodnie z programem maszyny <math>M_{(k)}</math>.
+* przejdzie do stanu <math>(q,\sqcup,\sqcup,\ldots,\sqcup)</math> i przeglądnie zawartość taśmy aż do prawego końca uzupełniając informację w stanie. Tzn. kiedy napotkana zostanie komórka z symbolem <math>(x_1,\ldots,\underline{x_i},\ldots,x_k)</math>, to w stanie <math>(q,A_1,\ldots,A_i,\ldots,A_k)</math> wartość na <math>i</math>-tej współrzędnej stanu zmienia się z <math>\sqcup</math> na <math>x_i</math>.
+* Posiadając już pełną informację o odczytach ze wszystkich taśm dokona jeszcze jednego przeglądnięcia taśmy w którym zostaną zmienione symbole taśmowe (na każdej ze współrzędnych osobno zgodnie z programem maszyny <math>M_{(k)}</math>.
 Jeżeli maszyna <math>M_{(k)}</math> działa dla wejścia rozmiaru <math>n</math> w czasie <math>\mathcal{O}(f(n))</math>, to działanie maszyny <math>M</math> zakończy się po wykonaniu <math>\mathcal{O}(f(n))</math> pętli przeglądających całą używaną taśmę. Wykonanie pojedynczej pętli odbywa się w czasie proporcjonalnym do długości użytej części taśmy. Tą z kolei możemy ograniczyć do <math>\mathcal{O}(f(n))</math> komórek na lewo i <math>\mathcal{O}(f(n))</math> komórek na prawo od pozycji początkowej - gdyż żadna z głowic w czasie <math>\mathcal{O}(f(n))</math> nie może pokonać większej odległości. W związku z tym otrzymujemy oszacowanie <math>\mathcal{O}(f(n)^2)</math> na złożoność czasową wynikowej maszyny.
 </div></div>
-}}
-{{cwiczenie||
-Symulacja na maszynie off-line.
+{{cwiczenie|20 [Symulacja na maszynie off-line]||
+}}
 Pokaż jak zasymulować <math>k</math>-taśmową maszynę Turinga na <math>2</math>-taśmowej maszynie off-line.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Użyj rezultatu z poprzedniego ćwiczenia.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Używając konstrukcji pozwalającej zasymulować <math>k</math>-taśmową maszynę Turinga na jednotaśmowej można całe obliczenie przeprowadzić na drugiej taśmie maszyny off-line. Wystarczy skopiować słowo wejściowej z pierwszej taśmy do odpowiednio przygotowanych komórek drugiej taśmy.
 </div></div>
-}}
 ==Niedeterministyczna maszyna Turinga==
@@ Linia 569: / Linia 525: @@
 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|[Uzupelnij]||
+{{definicja|21||
 Niedeterministyczna maszyna Turinga, to maszyna Turinga, w której funkcja przejścia jest częściową funkcją wielowartościową:
-: Q    {P}(Q    ,)
+<center><math>\delta : Q \times \Gamma \rightarrow \mathcal{P}(Q \times \Gamma \times \{\leftarrow,\rightarrow\})</math></center>
 }}
 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|[Uzupelnij]||
+{{definicja|22||
 Mówimy, że niedeterministyczna maszyna <math>M</math> akceptuje słowo <math>w</math> 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 niedeterminiźmie.
+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 <math>P\text{ vs }NP</math>, który omówimy dokładnie w dalszej części kursu.
-{{przyklad|[Uzupelnij]||
+{{przyklad|23 [Drzewo możliwych wykonań]||
-Drzewo możliwych wykonań.
-{
-{}{{}{1pt}{}{0pt}{}{0.12}{}{0.12}}
-Rysunek: '''drzewo możliwych wykonań z zaznaczonymi wykonaniami akceptującymi'''
+[[grafika:ZO-1.6-rys.gif|thumb|right||Drzewo możliwych wykonań z zaznaczonymi wykonaniami akceptującymi]]<br>Przyjrzyjmy się teraz diagramowi przykładowej niedeterministycznej maszyny Turinga. Można zauważyć, że niedeterminizm pojawia się w stanie <math>A</math>. Maszyna będąc  w stanie <math>A</math> i czytając z taśmy symbol <math>0</math> może zarówno:
-}
+* pozostawić <math>0</math> na taśmie i przesunąć głowicę w prawo nie zmieniając stanu.
-Przyjrzyjmy się teraz diagramowi przykładowej niedeterministycznej maszyny Turinga. Można zauważyć, że niedeterminizm pojawia się w stanie <math>A</math>. Maszyna będąc  w stanie <math>A</math> i czytając z taśmy symbol <math>0</math> może zarówno:
+* zamienić <math>0</math> na <math>1</math>, przesunąć się w prawo i zmienić stan na <math>B</math>.
-[*]
-pozostawić <math>0</math> na taśmie i przesunąć głowicę w prawo nie zmieniając stanu.
-zamienić <math>0</math> na <math>1</math>, przesunąć się w prawo i zmienić stan na <math>B</math>.
 Podobnie reakcja maszyny na symbol <math>1</math> może być dwojaka.
@@ Linia 614: / Linia 561: @@
 Przede wszystkim definiujemy, że niedeterministyczna maszyna <math>M</math> zatrzymuje się na słowie <math>w</math>, kiedy żaden z możliwych scenariuszy obliczenia nie jest nieskończony.
-{{definicja|[Uzupelnij]||
+{{definicja|24||
 Czas i pamięć zużytą przez maszynę <math>M</math>, która zatrzymuje się na słowie <math>w</math> definiujemy następująco:
-[*]
-Czas wykonania <math>NT(M,w)</math> jako liczbę kroków najdłuższego z możliwych obliczeń.
-Pamięć potrzebną do obliczenia <math>NS(M,w)</math> jako maksimum z liczby komórek potrzebnych w każdym możliwym scenariuszu obliczenia.
+* Czas wykonania <math>NT(M,w)</math> jako liczbę kroków najdłuższego z możliwych obliczeń.
+* Pamięć potrzebną do obliczenia <math>NS(M,w)</math> jako maksimum z liczby komórek potrzebnych w każdym możliwym scenariuszu obliczenia.
 }}
@@ Linia 628: / Linia 575: @@
 ===Ćwiczenia===
-{{cwiczenie||
+{{cwiczenie|25 [Symulacja maszyny niedeterministycznej na maszynie deterministycznej]||
-Symulacja maszyny niedeterministycznej na maszynie deterministycznej.
+}}
 Pokaż, że jeżeli język <math>L</math> jest rozpoznawany przez niedeterministyczną maszynę Turinga w czasie <math>\mathcal{O}(f(n))</math>, to istnieje deterministyczna maszyna Turinga rozpoznająca ten sam język w czasie <math>\mathcal{O}(c^{f(n)})</math> dla pewnej stałej <math>c</math>.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Skonstruuj wielotaśmową deterministyczną maszynę, która będzie przeglądać wszystkie ścieżki drzewa możliwych wykonań.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Niech <math>d = max_{A \in Q,x \in \Gamma} {\vert \delta(A,x) \vert}</math>. Zauważmy, że <math>d</math> jest maksymalnym stopniem rozgałęzienia, jaki może wystąpić w drzewie możliwych obliczeń maszyny.
@@ Linia 641: / Linia 587: @@
 Nasza maszyna będzie <math>4</math>-taśmową maszyną deterministyczną. Pierwsza taśma będzie zawsze przechowywać słowo wejściowe. Druga taśma będzie zawierać ciąg determinujący obliczenie niedeterministyczne. Na trzeciej taśmie będzie się odbywać symulacja. Czwarta taśma z kolei będzie służyć do przechowywania specjalnego znacznika. Maszyna będzie działać w następujący sposób, że dla kolejnych liczb naturalnych <math>m</math>:
-[*]
-usunie znaczniki z czwartej taśmy.
-przeglądnie wszystkie ciągi <math>x</math> długości <math>m</math> liczb z przedziału <math>[1,d]</math> zapisując je na drugiej taśmie i dla każdego z nich:
+* usunie znaczniki z czwartej taśmy.
-skopiuje zawartość pierwszej taśmy na trzecią taśmę i uruchomi tam zdeterminowany przy pomocy ciągu <math>x</math> program niedeterministycznej maszyny.
+* przeglądnie wszystkie ciągi <math>x</math> długości <math>m</math> liczb z przedziału <math>[1,d]</math> zapisując je na drugiej taśmie i dla każdego z nich:
-jeżeli obliczenie się nie zakończyło w ciągu pierwszych <math>m</math> kroków, to zaznaczy ten fakt zapisując specjalny symbol na czwartej taśmie.
+* skopiuje zawartość pierwszej taśmy na trzecią taśmę i uruchomi tam zdeterminowany przy pomocy ciągu <math>x</math> program niedeterministycznej maszyny.
-wyczyści trzecią taśmę używając techniki ,,czystego'' obliczenia.
+* jeżeli obliczenie się nie zakończyło w ciągu pierwszych <math>m</math> kroków, to zaznaczy ten fakt zapisując specjalny symbol na czwartej taśmie.
+* wyczyści trzecią taśmę używając techniki „czystego” obliczenia.
 Jeżeli którekolwiek ze zdeterminowanych obliczeń zakończy się akceptacją, to maszyna akceptuje słowo wejściowe. Jeżeli dla jakiejś liczby <math>m</math> wszystkie obliczenia się zakończą (a więc nie będzie odpowiedniego znacznika na czwartej taśmie), to obliczenie powinno się zakończyć z błędem.
@@ Linia 659: / Linia 605: @@
 Czas działania tak powstałej maszyny dla słowa wejściowego długości <math>n</math> możemy oszacować przez:
-{i<nowiki>=</nowiki>1}^{f(n)} {O}(i)d^i  {i<nowiki>=</nowiki>1}^{f(n)} {O}({(2d)}^i)  <nowiki>=</nowiki> {O}((2d)^{f(n)+1}) <nowiki>=</nowiki> {O}(e^{f(n)})
-, dla pewnej stałej <math>e</math>.
+<center><math>\sum_{i=1}^{f(n)} \mathcal{O}(i)d^i \leq \sum_{i=1}^{f(n)} \mathcal{O}({(2d)}^i)  = \mathcal{O}((2d)^{f(n)+1}) = \mathcal{O}(e^{f(n)})</math></center>
+dla pewnej stałej <math>e</math>.
 Możemy teraz użyć symulacji <math>4</math>-taśmowej maszyny Turinga działającej w czasie <math>\mathcal{O}(e^{f(n)})</math> na jednotaśmowej maszynie w czasie <math>\mathcal{O}((e^{f(n)})^2)</math>, czyli <math>\mathcal{O}(c^{f(n)})</math> dla <math>c=e^2</math>.
 </div></div>
-}}
-{{cwiczenie||
-Symulacja maszyny niedeterministycznej <math>k</math>-taśmowej na <math>2</math>-taśmowej.
+{{cwiczenie|26 [Symulacja maszyny niedeterministycznej <math>k</math>-taśmowej na <math>2</math>-taśmowej]||
+}}
 Pokaż, że język rozpoznawany przez <math>k</math>-taśmową niedeterministyczną maszynę Turinga <math>M</math> w czasie <math>\mathcal{O}(f(n))</math> jest również rozpoznawany przez <math>2</math>-taśmową niedeterministyczną maszynę Turinga w czasie <math>\mathcal{O}(f(n))</math>.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
 Użyj niedeterminizmu do wylosowania obliczenia akceptującego na <math>k</math>-taśmowej maszynie, a następnie sprawdź, że wylosowałeś poprawną ścieżkę obliczeń.
+</div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Niech <math>d</math> oznacza tak jak poprzednio <math>max_{A \in Q,x \in \Gamma} {\vert \delta(A,x) \vert}</math>.
@@ Linia 694: / Linia 641: @@
 Czas działania nowej maszyny dla słowa długości <math>n</math> jest proporcjonalny do
-{i<nowiki>=</nowiki>0}^{{  f(n) }} k2^i  4kf(n) <nowiki>=</nowiki> {O}(f(n))
+<center><math>\sum_{i=0}^{[\log f(n)]} k2^i \leq 4kf(n) = \mathcal{O}(f(n))</math></center>
 </div></div>
-}}
 ==Testy końcowe==