Teoria obliczalności

Teoria obliczalności, także teorii rekursji – dział teorii obliczeń zajmujący się badaniem jakie problemy są rozwiązywalne przy użyciu komputerów. Nie należy mylić teorii obliczalności z teorią złożoności obliczeniowej, zajmującej się badaniem jak efektywnie da się rozwiązywać różne problemy. Podstawowym obiektem badań teorii obliczalności są funkcje obliczalne.

Jednym z podstawowych zagadnień informatyki jest określenie potencjalnych możliwości komputerów przez zrozumienie problemów, które można za ich pomocą rozwiązywać. Współczesne komputery umożliwiają wyliczenie tak wielu rzeczy, że łatwo sobie można wyobrazić, iż rozwiązanie przez nie każdego problemu jest tylko kwestią czasu. Okazuje się jednak, że można wskazać problemy, których komputery nigdy nie będą potrafiły rozwiązać, niezależnie od dostępnych zasobów.

Aby formalnie definiować te problemy, informatyka teoretyczna bada możliwości komputerów do rozwiązywania następującego zadania:

Mając dany język formalny i ciąg znaków, określ czy ten ciąg należy do języka.

Przykładowo możemy zdefiniować nasz język formalny jako zbiór zapisów liczb pierwszych w systemie dziesiętnym. Pytanie, czy dany ciąg znaków należy do języka, jest wtedy pytaniem o to, czy dana liczba jest liczbą pierwszą. Podobnie możemy definiować nasz język jako zbiór palindromów, zbiór wszystkich ciągów złożonych wyłącznie z litery ‘a’ itp. Łatwo zauważyć, że dla jednych języków postawiony problem jest wyraźnie łatwiejszy niż dla innych.

Co dokładnie jednak znaczy „łatwiejszy”? Teoria obliczalności zajmuje się właśnie formalizowaniem tej intuicji, określając w sposób ścisły poziomy trudności języków.

Aby móc formalnie mówić o możliwościach komputerów, należy po pierwsze formalnie zdefiniować czym są obliczenia komputerowe. Używa się w tym celu kilku modeli obliczeń. Do najczęściej badanych należą:

Deterministyczny automat skończony

Najprostszy model obliczeń. Opisuje komputer jako maszynę o skończonej liczbie stanów i skończonej liczbie dopuszczalnych przejść pomiędzy stanami. Wybrane stany są oznaczone jako akceptujące. Wejściowy ciąg znaków jest odczytywany po jednym znaku, i po odczytaniu każdego znaku maszyna wykonuje przejście do nowego stanu zgodne z odczytanym znakiem. Po odczytaniu ostatniego znaku ciąg jest akceptowany albo nie, w zależności od stanu w jakim znajduje się maszyna.

Automat ze stosem

Analogiczny do automatu skończonego, ale z dodanym stosem, na którym można zapisać dowolną liczbę elementów. Przejścia dodatkowo określają czy maszyna powinna zapisać nowy symbol na stosie albo odczytać symbol z wierzchołka stosu.

Maszyna Turinga

Również podobna do automatu skończonego, ale z dodaną nieskończoną taśmą, na której maszyna może zapisywać i odczytywać symbole, przemieszczając się po niej w dowolną stronę. Maszyna Turinga jest prawdopodobnie najbardziej istotnym modelem obliczeń, ponieważ w prosty sposób modeluje wszystkie komputery niezależnie od ich mocy obliczeniowej.

Dysponując matematycznymi modelami obliczeń, możemy określić jakie są ich ograniczenia – czyli jakie języki mogą one rozpoznawać.

Języki rozpoznawane przez automaty skończone nazywane są językami regularnymi. Ponieważ liczba stanów automatu jest skończona, nie może on rozpoznawać języków, które wymagają nieograniczonej liczby stanów.

Przykładem takiego języka jest zbiór słów z liter ‘a’ i ‘b’, które zawierają taką samą liczbę liter ‘a’ i ‘b’. Aby pokazać, że nie jest on regularny, załóżmy, że istnieje maszyna M która go rozpoznaje. M ma jakąś skończoną liczbę stanów n. Rozważmy teraz ciąg x zbudowany kolejno ułożonych (n+1) liter ‘a’ i następnie (n+1) liter ‘b’. W trakcie czytania pierwszych (n+1) liter, maszyna M musi znaleźć się w którymś ze swoich stanów przynajmniej dwa razy (z powodu zasady szufladkowej). Oznacza to, że jeśli usuniemy fragment wejściowego ciągu, który maszyna przeczytała pomiędzy tymi dwoma momentami, to końcowy wynik będzie identyczny. Ale to oznacza, że maszyna zaakceptuje słowo w którym jest mniej ‘a’ niż ‘b’, co przeczy założeniu o istnieniu takiej maszyny.

Ogólnie do rozpoznawania jakie języki nie są regularne można wykorzystać lemat o pompowaniu dla języków regularnych.

Intuicyjnie wynik ten może wydawać się dziwny, ponieważ łatwo napisać program, który rozpoznaje czy w danym ciągu jest tyle samo ‘a’ co ‘b’ – a przecież wcześniej napisaliśmy, że komputery też są automatami skończonymi. Wynik ten jednak jest prawdziwy, ale wykorzystuje ważne ograniczenie komputerów: pojemność ich pamięci. Teoretycznie, czytając wystarczająco długi ciąg liter, komputer w końcu przepełni całą swoją pamięć licznikiem ile liter do tej pory przeczytał. W tym momencie będzie musiał znaleźć się ponownie w już raz odwiedzonym stanie. Ten przykład pokazuje jak wyniki dotyczące języków regularnych odnoszą się do klasycznych komputerów.

Języki rozpoznawane przez automaty ze stosem nazywane są językami bezkontekstowymi. Równoważną definicją tej klasy jest określenie jej jako języków definiowanych przez gramatyki bezkontekstowe. Języki te obejmują wszystkie języki regularne i część języków nieregularnych (jak np. podany wyżej język zawierający równą liczbę liter ‘a’ i ‘b’). Istnieją jednak języki, których automaty ze stosem nie potrafią rozpoznawać – przykładem jest np. język liczb pierwszych. Ogólnie do pokazywania, że jakiś język nie jest bezkontekstowy można wykorzystać lemat o pompowaniu dla języków bezkontekstowych.

Maszyny Turinga potrafią rozpoznawać wszystkie języki bezkontekstowe i wiele innych języków, jak na przykład podany wyżej język liczb pierwszych. Z powodu unikalnej możliwości „cofania” swoich dotychczasowych obliczeń, maszyna Turinga może analizować podany ciąg liter bardzo długo, potencjalnie nawet nigdy się nie zatrzymując. Dlatego mówi się, że maszyna rozpoznaje dany język, jeśli dla dowolnego wejścia zatrzymuje się z poprawnym wynikiem. Języki, które w ten sposób mogą być rozpoznawane nazywane są językami rekursywnymi. Możemy też zdefiniować szerszą klasę języków, zawierającą te języki, dla których maszyna Turinga zatrzymuje się z poprawną odpowiedzią na każdym poprawnym ciągu, ale może analizować nieskończenie długo ciągi, które nie należą do języka. Języki rozpoznawalne w ten sposób nazywają się językami rekursywnie przeliczalnymi.

Maszyna Turinga okazuje się bardzo potężnym modelem obliczeń. Dodanie do maszyny dodatkowych możliwości nie zwiększa już klasy rozpoznawanych przez nią języków. Przykładowo wyposażenie maszyny w dodatkowe taśmy, używanie zamiast taśmy dwuwymiarowej płaszczyzny (i trójwymiarowej i dowolnie-wymiarowej), dodanie RAM, możliwości losowania i nawet obliczeń kwantowych – może być zasymulowane na zwykłej jednowymiarowej taśmie. Istnieje tzw. hipoteza Churcha-Turinga, mówiąca, że każdy fizycznie realizowalny komputer jest równoważny maszynie Turinga.

 Osobny artykuł: Problem stopu.

Problem stopu jest jednym z najsłynniejszych problemów w informatyce, określającym możliwości wszystkich komputerów. Problem można sformułować w następujący sposób:

Mając dany opis maszyny Turinga i wejście, które ma do zanalizowania, określ czy maszyna ta kiedykolwiek się zatrzyma, czy też będzie działała w nieskończoność.

Można pokazać, że nie istnieje maszyna Turinga potrafiąca rozwiązywać ten problem dla dowolnych danych. Tym samym język złożony z par: (opis maszyny Turinga, słowo dla którego ta maszyna się zatrzymuje), nie jest językiem rekursywnym. Rozszerzeniem tego przykładu jest twierdzenie Rice’a, mówiące, że w ogólności każda nietrywialna własność podanego języka jest nierozstrzygalna.

Warto zauważyć, że język podany wyżej jest rekursywnie przeliczalny, ponieważ symulując działanie podanej maszyny na podanym wejściu dostaniemy w skończonym czasie odpowiedź dla każdego poprawnego wejścia. Można łatwo podać przykłady języków, które tego nie spełniają – przykładem jest język par dla których maszyna nie zatrzyma się na podanym wejściu.

Istnieją modele obliczeń, które faktycznie rozszerzają maszyny Turinga, ale zwykle są uznawane za nierealizowalne w żadnym praktycznym sensie.

Wyobraźmy sobie maszynę, której każdy kolejny krok wymaga o połowę mniej czasu niż poprzedni. Jeśli pierwszy krok wymaga jednej jednostki czasu, całe obliczenie trwa

${\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{4}}+\ldots }$

W ciągu 2 jednostek czasu maszyna może wykonać nieskończoną liczbę kroków. Taka maszyna jest zdolna do rozwiązywania problemu stopu.

Wyobraźmy sobie że nasza maszyna ma dostęp do „wyroczni” która może odpowiadać na pytania dotyczące wyszczególnionych nierozstrzygalnych problemów. Taki model jest często rozważany w kryptografii, gdy modelujemy urządzenia szyfrujące jako mające dostęp do nieznanego nam źródła informacji.

Okazuje się, że powyższe maszyny mają swoje ograniczenia analogiczne do ograniczeń maszyn Turinga. O ile potrafią rozstrzygać problem stopu dla maszyn Turinga, nie potrafią rozstrzygać własnych problemów stopu: przykładowo maszyna wyposażona w wyrocznię nie będzie potrafiła odpowiedzieć na pytanie czy podana maszyna z wyrocznią kiedykolwiek się zatrzyma.

• funkcja obliczalna

• NeilN. Immerman NeilN., Computability and Complexity, [w:] Stanford Encyclopedia of Philosophy, CSLI, Stanford University, 2 września 2015, ISSN 1095-5054 [dostęp 2018-01-16]  (ang.). (Obliczalność i złożoność)
• Computability theory (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].