Sld 9.1. Maszyny z nieograniczoną pamięcą Q = "Maszyna Turinga
Maszyny z nieograniczoną pamięcią Q = "  to maszyny liczące  komputery.
Matematyczny model  to maszyna Turinga . Alan Turing wymyślil maszynę w 1936 r. Celem Turinga było zbudowanie modelu, za pomocą którego można by zbadać ograniczenia  procesów obliczeniowych". Było to po opublikowaniu w 1931r.
W tym samym roku, jako narzędzie do analizy siły wyrazu procesów algorytmicznych, Emil Post zaprezentował inny model (zwany obecnie systemem produkcji Posta), który, jak udowodniono, ma takie same możliwości jak maszyny Turinga.
Modele opracowane przez tych naukowców wciąż służą jako cenne narzędzia do badań w dziedzinie informatyki.
Każdy problem, który daje się rozwiązać na maszynie Turinga lub Posta, ma także rozwiązanie na nowoczesnym komputerze. Jeśli tylko język programowania obejmuje cechy języka maszyny Turinga , to jest pewność, że dostarczy sposobów wyrażenia rozwiązania każdego problemu, który da się rozwiązać za pomocą komputera. Stosując język maszyny Turinga , odkryjemy, że są problemy, których współczesne komputery nie są w stanie rozwiązać i których żadna algorytmiczna maszyna przyszłości nie będzie w stanie rozwiązać.
Wśród problemów, które można rozwiązać na komputerze, są problemy, których rozwiązanie jest tak złożone, że są one w istocie nierozwiązywalne pod względem praktycznym.



Sld 9.2. Opis maszyny Turinga -1
Maszynę Turinga nad alfabetem A definiujemy jako
M = (, Q, L, qo, qf , � ), gdzie:
 = {a0, a1, & , ak-1}, jest skończonym alfabetem, zawierającym
a0 = L - pusty symbol ( nic nie jest zapisano);
" Q = {q0, q1, & , qr-1, qf} jest skończonym zbiorem stanów;
" q0 �� Q jest stanem początkowym;
qf �� Q jest stanem końcowym;
� jest relacją (reguły) przejścia:
ai qj ai qj S , gdzie: ai , ai �� , qj , qj �� Q,, S = {L, P, N}.
Sld 9.3. Opis maszyny Turinga - 2

Maszyna Turinga jest deterministyczna, gdy zawsze znajduje się w dokładnie jednym ze swoich stanów i widzi dokładnie jedną klatkę taśmy (nieskończonej w obie strony).
Maszyna Turinga jest niedeterministyczna gdy decyzje co do następnego kroku podejmowane są (w pewnych stanach) losowo .

Przez konfigurację maszyny rozumie się słowo postaci K=wqv, gdzie q �� Q oraz w,v �� A*, gdzie A* - to zbiór wszystkich slów nad A. Na taśmie mamy słowo wv, z lewej i z prawej same blanki (puste), a głowica maszyny patrzy na pierwszy znak na prawo od w. Konfigurację postaci Kw = qow, gdzie w ��A, nazywamy początkową, a konfigurację postaci Kf = wqf v, nazywamy końcową

Praca MT  to zmiana jej konfiguracji. K0, K1, K2, & , Kt, & , Kf .
Sld. 9.4. Przykład
Trzeba przetworzyć słowo unarne ������ w słowo binarne. Relacji przejść podane są w tabeli. Alfabet  = {L� , �� , 0,1},
q0������� (początek pętli 1) �� q11N ����� q11P ���� �� 1q1����� 1��q1��P�� 1����q1L�� 1����q2L�L �� 1��q2��� 1��q3L�L�� 1q3��� q31��� q30L�� �� q3L�0��� q110��
(początek pętli 2) �� q110��� q11P0��� 1q10��� 1q10P�� �� 10q1��� 10q1��P �� 10��q1L� �� 10��q2L�L�� 10q2��� 10q3L�L�� 1q30�� 1q41L�� q411�� q41L1 �� q4L�11�� q1L�P11��
(początek pętli 3) �� q111�� 1q11�� 11q1L�� 11q2L�� 1q21�� q211�� q2L�11�� qfL�11�� qf11.

Wynik: ������ �� 11

Sld. 9.5. Klasyfikacja problemów
Sld. 9.6. Funkcje Nierozstrzygalne i Rozstrzygalne
Są funkcje, w których związku między wartością wejściową a wynikiem nie daje się wyznaczyć algorytmicznie. Mówi się, że takie funkcje są Nieobliczalne (Nierozstrzygalne )

Funkcje, których wyniki można określić algorytmicznie na podstawie wartości wejściowych, są Obliczalne (Rozstrzygalne) .

Niema algorytmicznej metody znalezienia wartości wyjściowych funkcji nieobliczalnych. Funkcje te są poza zasięgiem możliwości współczesnych oraz przyszłych komputerów. Aby coś policzyć na komputerze, trzeba najpierw znalez
ć algorytm wykonujący niezbędne obliczenia. Poznanie granicy między funkcjami obliczalnymi i nieobliczalnymi jest równoważne poznaniu granic możliwości komputerów. Teza Churcha - Turinga stanowi ważny krok w kierunku określenia tych granic.



Sld. 9.7. Teza Churcha - Turinga
Funkcję, którą można obliczyć za pomocą maszyny Turinga, nazwiemy funkcją obliczalną w sensie Turinga. Komputery mogą rozwiązywać jedynie problemy, które dają się rozwiązać algorytmicznie.
Funkcje obliczalne w sensie Turinga są tym samym co funkcje obliczalne. Moc obliczeniowa maszyn Turinga jest nie mniejsza niż moc dowolnego systemu algorytmicznego lub, równoważnie, że za pomocą maszyny Turinga można opisać wszystkie funkcje obliczalne .
W spółcześnie ten postulat bywa często nazywany tezą Churcha - Turinga w hołdzie wkładu wniesionego zarówno przez Alana Turinga, jak i Alonza Churcha. Od czasu prac Turinga zebrano wiele dowodów świadczących o prawdziwości tej tezy i obecnie jest ona powszechnie akceptowana.
Znaczenie tego stwierdzenia polega na tym, że daje ono pogląd na możliwości i ograniczenia sprzętu komputerowego. Mówiąc precyzyjnie, zbiór funkcji obliczalnych w sensie Turinga stanowi zbiór, z którym porównuje się moc obliczeniową różnych systemów. Jeśli system obliczeniowy jest w stanie obliczyć wszystkie funkcje obliczalne w sensie Turinga, to jest uważany za system uniwersalny.
Problem obliczenia funkcji sprowadza się w istocie do stwierdzenia, czy dany program zakończy się po uruchomieniu go w konkretnym stanie początkowym. Problem ten jest często nazywany problemem stopu. Problem stopu jest przykładem problemu nierozwiązywalnego (nierozstrzygalnego), czyli problemu, którego rozwiązanie wymaga obliczenia wartości funkcji nieobliczalnej, a zatem leży poza możliwościami sprzętu liczącego.




Sld. 5.10. Złożoność problemów
Każde obliczenie na maszynie Turinga składa się z co najmniej tylu kroków ile wynosi długość słowa wejściowego.

Konwencja: Symbol n oznacza długość słowa wejściowego.

Mówimy, że (deterministyczna lub nie) maszyna Turinga ma złożoność czasową T(n) jeśli dla dowolnego n, każde obliczenie tej maszyny dla dowolnego słowa wejściowego w o długości n składa się z co najwyżej T(n) kroków. Musi zachodzić warunek T(n) > n.

Maszyna ma złożoność pamięciową S(n) jeśli każde jej obliczenie się zatrzymuje, i na dodatek, dla dowolnego n w każdym obliczeniu dla dowolnego słowa wejściowego w o długości n, maszyna używa co najwyżej S(n) klatek na każdej taśmie roboczej.

Mówiąc o złożoności czasowej T(n) i pamięciowej S(n), mamy w istocie na myśli
max{T(n),n} i max{Sr(n), n}.


Sld. 9.11. Złożoność czasową asymptotyczna
1. f(n) = Q�(g(n)) - Mówimy, że problem ma złożoność czasową Q�(g(n)), gdzie f(n) jest pewnym wyrażeniem matematycznym zależnym od n, n > n0 , jeśli istnieje algorytm o złożoności czasowej nie mniejszej niż c1g(n) i nie większej niż c2g(n) rozwiązujący ten problem. c1 i c2 - to dowolne stałe.
2. f(n) = O(g(n)) - Mówimy, że problem ma złożoność czasową O(g(n)), jeśli istnieje algorytm o złożoności czasowej nie większej niż cg(n) rozwiązujący ten problem, gdze c - dowolna stała, n > n0 .
3. f(n) = W�(g(n)) - Mówimy, że problem ma złożoność (czasową) W�(f(n)), jeśli nie ma algorytmu rozwiązującego go o mniejszej złoz
oności niż cg(n) gdzie c - stala., n > n0 .

Sld. 9.12. Klasy złożoności

Klasa P - Problem jest problemem wielomianowym, jeśli należy do klasy O(f (n)), gdzie f (n) jest albo wielomianem, albo jest ograniczone przez wielomian (n, n2, n3, ...). Taki problem może być rozwiązany na deterministycznej maszynie Turinga za wielomianowy czas.

Klasa NP - Problem nie jest problemem wielomianowym, jeśli należy do klasy O(f (n)), gdzie f (n) nie opisuje się wielomianem, a jest eksponentą (2n, an, n!, ... ). Taki problem może być rozwiązany na niedeterministycznej maszynie Turinga za wielomianowy czas.
Sld. 9.13. Klasy P i NP

Sld. 9.15. ZA
OŻONOŚĆ PAMI
CIOWA 
Alterntywą do mierzenia złożoności za pomocą czasu jest określenie wymagań pamięciowych. Taka miara to złożoność pamięciowa. Złożoność pamięciowa algorytmu to ilość miejsca w pamięci potrzebnego do rozwiązania problemu.

Często trzeba wybierać między złożonością czasową a pamięciową. W niektórych zastosowaniach może opłacić się wykonać z wyprzedzeniem pewne obliczenia i zapamiętać wyniki w tablicy, skąd można je będzie szybko pobrać, gdy będą potrzebne. Taka technika zmniejsza czas działania końcowego systemu kosztem dodatkowej pamięci potrzebnej do zapamiętania tablicy. Z drugiej strony, często wykorzystuje się kompresję danych do zmniejszenia wymagań pamięciowych kosztem dodatkowego czasu potrzebnego na skompresowanie danych i ich dekompresję.

Sld. 9.16. Literatura do rozdziału
J.Glenn Brookshear. Informatyka w ogólnym zarysie. Wydawnictwo Naukowo-Techniczne. Warszawa, 2003.
J.E.Hopcroft, J.D.Ullman. Wprowadzenie do teorii automatów, jeżyków i obliczeń. PWN, Warszawa, 2003.