Obliczalność — Computability

Obliczalność to umiejętność skutecznego rozwiązania problemu. Jest to kluczowy temat w dziedzinie teorii obliczalności w logice matematycznej i teorii obliczeń w informatyce . Obliczalność problemu jest ściśle powiązana z istnieniem algorytmu do rozwiązania problemu.

Najszerzej badanymi modelami obliczalności są funkcje obliczalne Turinga i funkcje rekurencyjne μ oraz rachunek lambda , z których wszystkie mają równoważną moc obliczeniową. Badane są również inne formy obliczalności: pojęcia obliczalności słabsze od maszyn Turinga są badane w teorii automatów , natomiast pojęcia obliczalności silniejsze od maszyn Turinga są badane w dziedzinie hiperobliczeń .

Problemy

Główną ideą obliczalności jest problem ( obliczeniowy ) , który jest zadaniem, którego obliczalność można zbadać.

Istnieją dwa kluczowe typy problemów:

A problem decyzyjny ustala zbiór S , który może być zbiorem ciągów liczb naturalnych, lub innych przedmiotów wykonanych z jakiegoś większego zbioru U . Szczególnym przypadkiem problemu jest rozstrzygnięcie, mając dany element u z U , czy u należy do S . Na przykład niech U będzie zbiorem liczb naturalnych, a S zbiorem liczb pierwszych. Odpowiedni problem decyzyjny odpowiada testowaniu pierwszości .
Problemem funkcja składa się z funkcji f z zestawu U do zestawu V . Przykładem problemu jest obliczenie danego elementu u w U , odpowiadającego mu elementu f ( u ) w V . Na przykład, U i V mogą być zbiorem wszystkich skończonych ciągów binarnych, a f może wziąć ciąg i zwrócić ciąg otrzymany przez odwrócenie cyfr na wejściu (więc f(0101) = 1010).

Inne rodzaje problemów obejmują problemy z wyszukiwaniem i problemy z optymalizacją .

Jednym z celów teorii obliczalności jest określenie, które problemy lub klasy problemów można rozwiązać w każdym modelu obliczeniowym.

Formalne modele obliczeń

Model obliczeń jest formalnym opisem danego rodzaju procesu obliczeniowego. Opis często przybiera formę abstrakcyjnej maszyny, która ma wykonać dane zadanie. Ogólne modele obliczeń równoważne maszynie Turinga (patrz teza Churcha-Turinga ) obejmują:

Rachunek lambda: Obliczenie składa się z początkowego wyrażenia lambda (lub dwóch, jeśli chcesz oddzielić funkcję od jej danych wejściowych) oraz skończonej sekwencji terminów lambda, z których każdy został wydedukowany z poprzedniego wyrażenia przez jedno zastosowanie redukcji beta .
Logika kombinacyjna: Pojęcie, które ma wiele podobieństw do rachunku różniczkowego, ale istnieją również istotne różnice (np. kombinator punktu stałego Y ma postać normalną w logice kombinatorycznej, ale nie w rachunku różniczkowym). Logika kombinatoryczna była rozwijana z wielkimi ambicjami: zrozumienie natury paradoksów, uczynienie podstaw matematyki bardziej ekonomicznymi (pojęciowo), wyeliminowanie pojęcia zmiennych (a tym samym wyjaśnienie ich roli w matematyce). ${\ Displaystyle \ lambda}$ ${\ Displaystyle \ lambda}$
μ-funkcje rekurencyjne: Obliczenie składa się z funkcji μ-rekurencyjnej, tj. jej sekwencji definiującej, dowolnej wartości wejściowej i sekwencji funkcji rekurencyjnych występujących w sekwencji definiującej z wejściami i wyjściami. Jeśli więc w ciągu definiującym funkcję rekurencyjną $f (x) występują$ funkcje $g (x)$ i $h (x, y)$ , to wyrazy postaci $g (5) = 7$ lub $h (3,2) = 10$ może pojawić się. Każdy wpis w tej sekwencji musi być zastosowaniem funkcji podstawowej lub wynikać z powyższych wpisów przy użyciu kompozycji , pierwotnej rekurencji lub μ-rekursji . Na przykład, jeśli $f (x) = h (x, g (x))$ , to aby pojawiło się $f (5) = 3$ , wyrażenia takie jak $g (5) = 6$ i $h (5,6) = 3$ muszą wystąpić powyżej. Obliczenie kończy się tylko wtedy, gdy ostatni wyraz podaje wartość funkcji rekurencyjnej zastosowanej do danych wejściowych.
Systemy przepisywania ciągów: Zawiera algorytmy Markowa , które używają reguł podobnych do gramatyki do operowania na ciągach symboli; także system postkanoniczny .
Zarejestruj maszynę: Teoretyczna idealizacja komputera. Istnieje kilka wariantów. W większości z nich każdy rejestr może zawierać liczbę naturalną (o nieograniczonej wielkości), a instrukcje są proste (i nieliczne), np. istnieje tylko dekrementacja (połączona ze skokiem warunkowym) i inkrementacja (i zatrzymanie). Brak nieskończonej (lub dynamicznie rosnącej) pamięci zewnętrznej (widoczny na maszynach Turinga) można zrozumieć zastępując jego rolę technikami numeracji Gödla : fakt, że każdy rejestr zawiera liczbę naturalną, pozwala na reprezentację skomplikowanej rzeczy (np. sekwencja, macierz itp.) przez odpowiednią ogromną liczbę naturalną — jednoznaczność zarówno reprezentacji, jak i interpretacji można ustalić na podstawie liczbowych podstaw teoretycznych tych technik.
Maszyna Turinga: Również podobny do skończonej maszyny stanów, z wyjątkiem tego, że dane wejściowe są dostarczane na „taśmie” wykonawczej, z której maszyna Turinga może czytać, zapisywać lub poruszać się tam iz powrotem za swoją „głowicą” odczytu/zapisu. Taśma może urosnąć do dowolnego rozmiaru. Maszyna Turinga jest w stanie wykonywać złożone obliczenia, które mogą mieć dowolny czas trwania. Model ten jest prawdopodobnie najważniejszym modelem obliczeniowym w informatyce, ponieważ symuluje obliczenia przy braku predefiniowanych limitów zasobów.
Wielotaśmowa maszyna Turinga: Tutaj może być więcej niż jedna taśma; ponadto na taśmie może być wiele głowic. Co zaskakujące, wszelkie obliczenia, które można wykonać za pomocą tego rodzaju maszyny, mogą być również wykonane przez zwykłą maszynę Turinga, chociaż ta ostatnia może być wolniejsza lub wymagać większego całkowitego obszaru taśmy.
P′′: Podobnie jak maszyny Turinga, P′′ używa nieskończonej taśmy symboli (bez dostępu losowego) i raczej minimalistycznego zestawu instrukcji. Ale te instrukcje są bardzo różne, stąd w przeciwieństwie do maszyn Turinga, P′′ nie musi utrzymywać odrębnego stanu, ponieważ cała „pamięciowa” funkcjonalność może być zapewniona tylko przez taśmę. Zamiast przepisywać bieżący symbol, może wykonać na nim modularną inkrementację arytmetyczną . P′′ ma również parę instrukcji dla cyklu, sprawdzając pusty symbol. Mimo swojego minimalistycznego charakteru, stał się on macierzystym językiem formalnym zaimplementowanego i (dla rozrywki) używanego języka programowania o nazwie Brainfuck .

Oprócz ogólnych modeli obliczeniowych niektóre prostsze modele obliczeniowe są przydatne do specjalnych, ograniczonych zastosowań. Na przykład wyrażenia regularne określają wzorce ciągów w wielu kontekstach, od oprogramowania biurowego po języki programowania . Inny formalizm matematycznie równoważny wyrażeniom regularnym, automaty skończone, są używane w projektowaniu obwodów i w niektórych rodzajach rozwiązywania problemów. Gramatyki bezkontekstowe określają składnię języka programowania. Non-deterministyczne automaty przesuwająca w dół jest inny równoważny formalizm gramatyk bezkontekstowych.

Różne modele obliczeń mają możliwość wykonywania różnych zadań. Jednym ze sposobów pomiaru mocy modelu obliczeniowego jest zbadanie klasy języków formalnych, które model może wygenerować; w ten sposób uzyskuje się hierarchię języków Chomsky'ego .

Inne ograniczone modele obliczeń obejmują:

Deterministyczny automat skończony (DFA): Nazywana także maszyną skończoną. Wszystkie istniejące obecnie rzeczywiste urządzenia obliczeniowe można zamodelować jako maszynę skończoną, ponieważ wszystkie rzeczywiste komputery działają na skończonych zasobach. Taka maszyna ma zbiór stanów oraz zbiór przejść stanów, na które wpływa strumień wejściowy. Niektóre stany są zdefiniowane jako stany akceptujące. Strumień wejściowy jest podawany do maszyny po jednym znaku na raz, a zmiany stanu dla bieżącego stanu są porównywane ze strumieniem wejściowym, a jeśli występuje pasujące przejście, maszyna może wejść w nowy stan. Jeżeli na końcu strumienia wejściowego maszyna jest w stanie akceptującym, to cały strumień wejściowy jest akceptowany.
Niedeterministyczny automat skończony (NFA): Kolejny prosty model obliczeń, chociaż kolejność jego przetwarzania nie jest jednoznacznie określona. Można to interpretować jako przyjmowanie wielu ścieżek obliczeń jednocześnie przez skończoną liczbę stanów. Jednak możliwe jest udowodnienie, że każdy NAS można zredukować do równoważnego DFA.
Automat do dociskania: Podobny do automatu skończonego, z wyjątkiem tego, że ma dostępny stos wykonawczy, który może urosnąć do dowolnego rozmiaru. Przejścia stanów dodatkowo określają, czy dodać symbol do stosu, czy usunąć symbol ze stosu. Jest potężniejszy niż DFA ze względu na stos nieskończonej pamięci, chociaż tylko górny element stosu jest dostępny w dowolnym momencie.

Moc automatów automat

Dysponując tymi modelami obliczeniowymi, możemy określić ich granice. To znaczy, jakie klasy języków mogą zaakceptować?

Moc maszyn skończonych

Informatycy nazywają każdy język, który może być zaakceptowany przez maszynę skończoną, językiem regularnym . Ze względu na ograniczenie, że liczba możliwych stanów w skończonej maszynie stanów jest skończona, możemy zobaczyć, że aby znaleźć język, który nie jest regularny, musimy skonstruować język, który wymagałby nieskończonej liczby stanów.

Przykładem takiego języka jest zbiór wszystkich ciągów składających się z liter „a” i „b”, które zawierają jednakową liczbę liter „a” i „b”. Aby zobaczyć, dlaczego ten język nie może być poprawnie rozpoznany przez maszynę skończoną, załóżmy najpierw, że taka maszyna M istnieje. M musi mieć pewną liczbę stanów n . Rozważmy teraz łańcuch x składający się z „a”, po którym następuje „b”. ${\ Displaystyle (n + 1)}$ ${\ Displaystyle (n + 1)}$

Tak jak M czyta w x , musi istnieć jakiś stan w maszynie, który jest powtarzany tak, jak czyta w pierwszej serii „a”, ponieważ zgodnie z zasadą szufladki istnieje tylko „a” i tylko n stanów . Nazwijmy ten stan S i dalej niech d będzie liczbą „a”, które nasza maszyna odczytała, aby przejść od pierwszego wystąpienia S do jakiegoś kolejnego wystąpienia w sekwencji „a”. Wiemy więc, że przy drugim wystąpieniu S możemy dodać dodatkowe d (gdzie ) 'a' i znów będziemy w stanie S . Oznacza to, że wiemy, że ciąg „a” musi znaleźć się w tym samym stanie, co ciąg „a”. Oznacza to, że jeśli nasza maszyna akceptuje x , musi również zaakceptować ciąg znaków 'a', po którym następuje 'b', co nie jest językiem łańcuchów zawierających równą liczbę 'a' i 'b'. Innymi słowy, M nie potrafi poprawnie rozróżnić między ciągiem o równej liczbie „a” i „b” a ciągiem z „a” i „b”. ${\ Displaystyle (n + 1)}$ $d>0$ ${\ Displaystyle (n+d+1)}$ ${\ Displaystyle (n + 1)}$ ${\ Displaystyle (n+d+1)}$ ${\ Displaystyle (n + 1)}$ ${\ Displaystyle (n+d+1)}$ $n+1$

Wiemy zatem, że język ten nie może być poprawnie zaakceptowany przez żadną maszynę skończoną, a zatem nie jest językiem regularnym. Bardziej ogólna postać tego wyniku nazywa się lematem o pompowaniu dla języków regularnych , który może być użyty do wykazania, że szerokie klasy języków nie mogą być rozpoznawane przez maszynę skończoną.

Moc automatów dociskowych

Informatycy definiują język, który może być zaakceptowany przez automat przesuwający w dół, jako język bezkontekstowy , który można określić jako gramatykę bezkontekstową . O języku składającym się z łańcuchów o równej liczbie 'a' i 'b', który pokazaliśmy, że nie jest językiem regularnym, może rozstrzygnąć automat przesuwający w dół. Ponadto, ogólnie rzecz biorąc, automat zestawiający może zachowywać się jak maszyna skończona, więc może decydować o dowolnym języku, który jest regularny. Ten model obliczeń jest zatem ściśle potężniejszy niż automaty skończone.

Okazuje się jednak, że są też języki, których nie można rozstrzygnąć za pomocą automatu push-down. Wynik jest podobny do wyrażeń regularnych i nie będzie tutaj szczegółowo opisywany. Istnieje lemat Pumping dla języków bezkontekstowych . Przykładem takiego języka jest zbiór liczb pierwszych.

Moc maszyn Turinga

Maszyny Turinga mogą decydować o dowolnym języku bezkontekstowym, oprócz języków nierozstrzygalnych przez automat ze przesuwaniem w dół, takich jak język składający się z liczb pierwszych. Jest to zatem ściślej potężniejszy model obliczeniowy.

Ponieważ maszyny Turinga mają możliwość tworzenia kopii zapasowych na taśmie wejściowej, maszyna Turinga może działać przez długi czas w sposób, który nie jest możliwy w przypadku innych opisanych wcześniej modeli obliczeniowych. Możliwe jest skonstruowanie maszyny Turinga, która nigdy nie zakończy działania (zatrzyma się) na niektórych wejściach. Mówimy, że maszyna Turinga może zdecydować o języku, jeśli w końcu zatrzyma się na wszystkich wejściach i udzieli odpowiedzi. Język, który można tak określić, nazywa się językiem rekurencyjnym . Możemy dalej opisać maszyny Turinga, które ostatecznie zatrzymają się i udzielą odpowiedzi na dowolne dane wejściowe w języku, ale które mogą działać bez końca dla ciągów wejściowych, których nie ma w tym języku. Takie maszyny Turinga mogą nam powiedzieć, że dany ciąg znajduje się w języku, ale na podstawie jego zachowania nigdy nie możemy być pewni, że dany ciąg nie jest w języku, ponieważ w takim przypadku może działać w nieskończoność. Język akceptowany przez taką maszynę Turinga nazywany jest językiem rekurencyjnie przeliczalnym .

Okazuje się, że maszyna Turinga jest niezwykle potężnym modelem automatów. Próby zmiany definicji maszyny Turinga w celu wyprodukowania maszyny o większej mocy niespodziewanie zakończyły się niepowodzeniem. Na przykład dodanie dodatkowej taśmy do maszyny Turinga, dając jej dwuwymiarową (lub trójwymiarową lub dowolną wymiarową) nieskończoną powierzchnię do pracy, może być symulowane przez maszynę Turinga z podstawową taśmą jednowymiarową. Modele te nie są więc mocniejsze. W rzeczywistości konsekwencją tezy Churcha-Turinga jest to, że nie ma rozsądnego modelu obliczeniowego, który mógłby decydować o językach, o których nie może decydować maszyna Turinga.

Należy zatem zadać pytanie: czy istnieją języki, które są rekurencyjnie przeliczalne, ale nie rekurencyjne? A ponadto, czy istnieją języki, które nie są nawet rekurencyjnie przeliczalne?

Problem z zatrzymaniem

Problem zatrzymania jest jednym z najbardziej znanych problemów w informatyce, ponieważ ma głębokie implikacje dla teorii obliczalności i sposobu, w jaki używamy komputerów w codziennej praktyce. Problem można sformułować:

Mając opis maszyny Turinga i jej początkowe dane wejściowe, określ, czy program, gdy jest wykonywany na tym wejściu, kiedykolwiek się zatrzyma (ukończy). Alternatywą jest to, że działa w nieskończoność bez zatrzymywania się.

Tutaj nie zadajemy prostego pytania o liczbę pierwszą lub palindrom, ale zamiast tego odwracamy sytuację i prosimy maszynę Turinga o odpowiedź na pytanie o inną maszynę Turinga. Można wykazać (patrz główny artykuł: Problem z zatrzymaniem ), że nie jest możliwe skonstruowanie maszyny Turinga, która potrafiłaby odpowiedzieć na to pytanie we wszystkich przypadkach.

Oznacza to, że jedynym ogólnym sposobem uzyskania pewności, czy dany program zatrzyma się na określonym wejściu we wszystkich przypadkach, jest po prostu uruchomienie go i sprawdzenie, czy się zatrzyma. Jeśli się zatrzyma, to wiesz, że się zatrzyma. Jeśli jednak się nie zatrzyma, możesz nigdy nie wiedzieć, czy w końcu się zatrzyma. Język składający się ze wszystkich opisów maszyn Turinga w połączeniu ze wszystkimi możliwymi strumieniami wejściowymi, na których te maszyny Turinga ostatecznie się zatrzymają, nie jest rekurencyjny. Problem zatrzymania nazywany jest zatem nieobliczalnym lub nierozstrzygalnym .

Rozszerzeniem problemu zatrzymania nazywa się twierdzenie Rice'a , które mówi, że jest nierozstrzygnięte (w ogólności), czy dany język posiada jakąś konkretną nietrywialną właściwość.

Poza rekurencyjnie przeliczalnymi językami

Problem zatrzymania jest jednak łatwy do rozwiązania, jeśli pozwolimy, aby maszyna Turinga, która o tym decyduje, działała w nieskończoność, gdy dane wejście jest reprezentacją maszyny Turinga, która sama się nie zatrzymuje. Wstrzymujący się język jest zatem rekurencyjnie przeliczalny. Możliwe jest jednak konstruowanie języków, które nie są nawet rekurencyjnie przeliczalne.

Prostym przykładem takiego języka jest dopełnienie języka przerywanego; to jest język składający się ze wszystkich maszyn Turinga sparowanych z ciągami wejściowymi, w których maszyny Turinga nie zatrzymują się na swoim wejściu. Aby zobaczyć, że język ten nie jest rekurencyjnie przeliczalny, wyobraźmy sobie, że konstruujemy maszynę Turinga M, która jest w stanie udzielić określonej odpowiedzi dla wszystkich takich maszyn Turinga, ale że może działać w nieskończoność na dowolnej maszynie Turinga, która w końcu się zatrzyma. Możemy następnie skonstruować kolejną maszynę Turinga, która symuluje działanie tej maszyny, wraz z symulacją bezpośrednio wykonania maszyny podanej na wejściu, przeplatając wykonanie dwóch programów. Ponieważ bezpośrednia symulacja w końcu zatrzyma się, jeśli symulowany program się zatrzyma, i ponieważ z założenia symulacja M zostanie ostatecznie zatrzymana, jeśli program wejściowy nigdy się nie zatrzyma, wiemy, że w końcu jedna z jego równoległych wersji zostanie zatrzymana. jest zatem decydentem problemu zatrzymania. Wcześniej jednak pokazaliśmy, że problem zatrzymania jest nierozstrzygnięty. Mamy sprzeczność i pokazaliśmy w ten sposób, że nasze założenie o istnieniu M jest błędne. Dopełnienia języka niestabilnego nie można zatem rekurencyjnie przeliczyć. $M'$ $M'$ $M'$

Modele oparte na współbieżności

Opracowano szereg modeli obliczeniowych opartych na współbieżności , w tym równoległą maszynę o dostępie swobodnym i sieć Petriego . Te modele obliczeń współbieżnych nadal nie implementują żadnych funkcji matematycznych, których nie mogą zaimplementować maszyny Turinga.

Silniejsze modele obliczeń

Kościół-Turinga dyplomowych przypuszczenia, że nie istnieje skuteczny model obliczeniowy może obliczyć funkcje matematyczne więcej niż maszyna Turinga. Informatycy wyobrazili sobie wiele odmian hiperkomputerów , modeli obliczeniowych, które wykraczają poza obliczalność Turinga.

Nieskończona egzekucja

Wyobraź sobie maszynę, w której każdy krok obliczeń wymaga połowy czasu poprzedniego kroku (i miejmy nadzieję, że o połowę mniej energii w poprzednim kroku...). Jeśli znormalizujemy do 1/2 jednostki czasu ilość czasu potrzebnego na pierwszy krok (i do 1/2 jednostki energii ilość energii potrzebnej na pierwszy krok...), wykonanie będzie wymagało

{\ Displaystyle 1 = \ suma _ {n = 1} ^ {\ infty} {\ Frac {1} {2 ^ {n}}} = {\ Frac {1} {2}} + {\ Frac {1} {4}}+{\frac {1}{8}}+{\frac {1}{16}}+\cdots }

jednostka czasu (i 1 jednostka energii...) do uruchomienia. Ta nieskończona seria zbiega się do 1, co oznacza, że ta maszyna Zeno może wykonać nieskończoną liczbę kroków w 1 jednostce czasu (używając 1 jednostki energii...). Ta maszyna jest w stanie rozwiązać problem zatrzymania poprzez bezpośrednią symulację wykonania danej maszyny. Co za tym idzie, każda zbieżna nieskończona seria [musi być prawdopodobnie nieskończona] będzie działać. Zakładając, że nieskończony szereg zbiega się do wartości n , maszyna Zeno wykonałaby przeliczalnie nieskończone wykonanie w n jednostkach czasu.

Maszyny Oracle

Tak zwane maszyny Oracle mają dostęp do różnych „wyroczni”, które zapewniają rozwiązanie konkretnych, nierozstrzygalnych problemów. Na przykład maszyna Turinga może mieć „wyrocznię zatrzymującą”, która natychmiast odpowiada, czy dana maszyna Turinga kiedykolwiek zatrzyma się na danym wejściu. Maszyny te są centralnym tematem badań w teorii rekurencji .

Granice hiperobliczeń

Nawet te maszyny, które pozornie reprezentują granicę automatów, jakie moglibyśmy sobie wyobrazić, napotykają na własne ograniczenia. Chociaż każdy z nich może rozwiązać problem zatrzymania maszyny Turinga, nie może rozwiązać własnej wersji problemu zatrzymania. Na przykład maszyna Oracle nie może odpowiedzieć na pytanie, czy dana maszyna Oracle kiedykolwiek się zatrzyma.

Zobacz też

Bibliografia

Michaela Sipsera (1997). Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. Numer ISBN 0-534-94728-X. Część druga: Teoria obliczalności, rozdziały 3–6, s. 123–222.
Christos Papadimitriou (1993). Złożoność obliczeniowa (wyd. 1). Addisona Wesleya. Numer ISBN 0-201-53082-1. Rozdział 3: Obliczalność, s. 57–70.
S. Barry'ego Coopera (2004). Teoria obliczalności (wyd. 1). Chapman & Hall/CRC. Numer ISBN 978-1-58488-237-4.

Languages

In other projects