Teoria obliczeń

Nie mylić z obliczeniową teorią umysłu .

Aby zapoznać się z czasopismem, zobacz Theory of Computing .

Artystyczna reprezentacja maszyny Turinga . Maszyny Turinga są często używane jako modele teoretyczne do obliczeń.

W informatyce teoretycznej i matematyce teoria obliczeń jest gałęzią zajmującą się tym, jakie problemy można rozwiązać na modelu obliczeniowym przy użyciu algorytmu , jak skutecznie można je rozwiązać lub w jakim stopniu (np. rozwiązania przybliżone a rozwiązania precyzyjne ). Dziedzina ta jest podzielona na trzy główne gałęzie: teoria automatów i języki formalne , teoria obliczalności i teoria złożoności obliczeniowej , które łączy pytanie: „Jakie są podstawowe możliwości i ograniczenia komputerów?”.

Aby przeprowadzić rygorystyczne badanie obliczeń, informatycy pracują z matematyczną abstrakcją komputerów zwaną modelem obliczeń . W użyciu jest kilka modeli, ale najczęściej badana jest maszyna Turinga . Informatycy badają maszynę Turinga, ponieważ jest ona łatwa do sformułowania, może być analizowana i używana do udowodnienia wyników, a także dlatego, że reprezentuje to, co wielu uważa za najpotężniejszy możliwy „rozsądny” model obliczeń (patrz teza Churcha-Turinga ) . Mogłoby się wydawać, że potencjalnie nieskończona pojemność pamięci jest atrybutem nie do zrealizowania, ale jakimkolwiek rozstrzygalny problem rozwiązany przez maszynę Turinga zawsze będzie wymagał tylko skończonej ilości pamięci. Tak więc w zasadzie każdy problem, który może zostać rozwiązany (rozstrzygnięty) przez maszynę Turinga, może zostać rozwiązany przez komputer, który ma skończoną ilość pamięci.

Historia

Teorię obliczeń można uznać za tworzenie wszelkiego rodzaju modeli w dziedzinie informatyki. Dlatego stosuje się matematykę i logikę . W ostatnim stuleciu stała się samodzielną dyscypliną akademicką i została oddzielona od matematyki.

Pionierami teorii obliczeń byli Ramon Llull , Alonzo Church , Kurt Gödel , Alan Turing , Stephen Kleene , Rózsa Péter , John von Neumann i Claude Shannon .

Gałęzie

Teoria automatów

Główny artykuł: Teoria automatów

Gramatyka	Języki	Automat	Reguły produkcji (ograniczenia)
Wpisz-0	Rekurencyjnie przeliczalny	Maszyna Turinga	${\ Displaystyle \ alfa \ rightarrow \ beta}$ (bez ograniczeń)
Typ 1	Kontekstowe	Niedeterministyczna maszyna Turinga o granicach liniowych	${\ Displaystyle \ alfa A \ beta \ strzałka w prawo \ alfa \ gamma \ beta}$
Typ-2	Bezkontekstowe	Niedeterministyczny automat przesuwający w dół	${\ Displaystyle A \ strzałka w prawo \ gamma}$
Typ-3	Regularny	Automat skończony	${\ Displaystyle A \ rightarrow a}$ i ${\ Displaystyle A \ rightarrow aB}$

Teoria automatów to nauka o abstrakcyjnych maszynach (lub, bardziej odpowiednio, abstrakcyjnych „matematycznych” maszynach lub systemach) i problemach obliczeniowych, które można rozwiązać za pomocą tych maszyn. Te abstrakcyjne maszyny nazywane są automatami. Automata pochodzi od greckiego słowa (Αυτόματα), które oznacza, że ​​coś samo się robi. Teoria automatów jest również ściśle związana z językiem formalnym teorii, ponieważ automaty są często klasyfikowane według klas języków formalnych, które są w stanie rozpoznać. Automat może być skończoną reprezentacją języka formalnego, który może być zbiorem nieskończonym. Automaty są używane jako modele teoretyczne dla maszyn obliczeniowych i są używane do dowodów obliczalności.

Teoria języka formalnego

Główny artykuł: język formalny

Zestaw inkluzji opisany hierarchią Chomsky'ego

Teoria języka to dział matematyki zajmujący się opisywaniem języków jako zbioru operacji na alfabecie . Jest ściśle powiązany z teorią automatów, ponieważ automaty służą do generowania i rozpoznawania języków formalnych. Istnieje kilka klas języków formalnych, z których każda pozwala na bardziej złożoną specyfikację języka niż poprzednia, tj. hierarchia Chomsky'ego , i każda odpowiada klasie automatów, które ją rozpoznają. Ponieważ automaty są używane jako modele do obliczeń, języki formalne są preferowanym sposobem specyfikacji każdego problemu, który musi zostać obliczony.

Teoria obliczalności

Główny artykuł: Teoria obliczalności

Teoria obliczalności zajmuje się przede wszystkim kwestią stopnia, w jakim problem można rozwiązać na komputerze. Stwierdzenie, że problemu zatrzymania nie można rozwiązać za pomocą maszyny Turinga, jest jednym z najważniejszych wyników teorii obliczalności, ponieważ jest przykładem konkretnego problemu, który jest zarówno łatwy do sformułowania, jak i niemożliwy do rozwiązania za pomocą maszyny Turinga. Większość teorii obliczalności opiera się na wyniku problemu zatrzymania.

Kolejnym ważnym krokiem w teorii obliczalności było twierdzenie Rice'a , które stwierdza, że ​​dla wszystkich nietrywialnych właściwości funkcji cząstkowych nie można rozstrzygnąć , czy maszyna Turinga oblicza funkcję cząstkową z tą właściwością.

Teoria obliczalności jest ściśle powiązana z gałęzią logiki matematycznej zwaną teorią rekurencji , która usuwa ograniczenie studiowania tylko modeli obliczeń, które można zredukować do modelu Turinga. Wielu matematyków i teoretyków obliczeń, którzy badają teorię rekurencji, nazywa ją teorią obliczalności.

Teoria złożoności obliczeniowej

Główny artykuł: Teoria złożoności obliczeniowej

Reprezentacja relacji między klasami złożoności

Teoria złożoności bierze pod uwagę nie tylko to, czy problem można w ogóle rozwiązać na komputerze, ale także, jak skutecznie można go rozwiązać. Rozważane są dwa główne aspekty: złożoność czasowa i złożoność przestrzenna, które oznaczają odpowiednio liczbę kroków wymaganych do wykonania obliczeń oraz ilość pamięci wymaganej do wykonania tych obliczeń.

Aby przeanalizować, ile czasu i miejsca wymaga dany algorytm , informatycy wyrażają czas lub miejsce potrzebne do rozwiązania problemu jako funkcję wielkości problemu wejściowego. Na przykład znalezienie określonej liczby na długiej liście liczb staje się trudniejsze, gdy lista liczb rośnie. Jeśli powiemy, że istnieje n numerów na liście, to jeśli lista nie jest w żaden sposób posortowana ani indeksowana, być może będziemy musieli spojrzeć na każdy numer, aby znaleźć numer, którego szukamy. Mówimy zatem, że aby rozwiązać ten problem, komputer musi wykonać szereg kroków, których rozmiar rośnie liniowo.

Aby uprościć ten problem, informatycy przyjęli notację Big O , która umożliwia porównywanie funkcji w sposób gwarantujący, że nie trzeba brać pod uwagę poszczególnych aspektów konstrukcji maszyny, a jedynie asymptotyczne zachowanie , gdy problemy stają się duże. Tak $więc w naszym poprzednim przykładzie możemy$ rozwiązanie problemu wymaga

Być może najważniejszym otwartym problemem w całej informatyce jest pytanie, czy pewną szeroką klasę problemów oznaczoną jako NP można skutecznie rozwiązać. Jest to omówione dalej w klasach złożoności P i NP , a problem P kontra NP jest jednym z siedmiu problemów nagrody milenijnej stwierdzonych przez Clay Mathematics Institute w 2000 r. Oficjalny opis problemu został podany przez zdobywcę nagrody Turinga , Stephena Cooka .

Modele obliczeń

Główny artykuł: Model obliczeń

Oprócz maszyny Turinga w użyciu są inne równoważne (patrz teza Churcha-Turinga ) modele obliczeń.

Rachunek lambda Obliczenie

składa się z początkowego wyrażenia lambda (lub dwóch, jeśli chcesz oddzielić funkcję od danych wejściowych) oraz skończonej sekwencji wyrażeń lambda, z których każdy jest wydedukowany z poprzedniego wyrażenia przez jedno zastosowanie redukcji Beta .

Logika kombinacyjna

to koncepcja, która ma wiele podobieństw do rachunku $różniczkowego$ , ale istnieją również ważne różnice (np. kombinator punktów stałych Y ma postać normalną w logice kombinatorycznej, ale nie w $displaystyle \ lambda}$ -rachunek różniczkowy). Logika kombinatoryczna została opracowana z wielkimi ambicjami: zrozumienie natury paradoksów, uczynienie podstaw matematyki bardziej ekonomicznymi (koncepcyjnie), wyeliminowanie pojęcia zmiennych (w ten sposób wyjaśnienie ich roli w matematyce).

Funkcje μ-rekurencyjne

Obliczenie składa się z funkcji mu-rekurencyjnej, tj . jej sekwencji definiującej, dowolnej wartości wejściowej oraz sekwencji funkcji rekurencyjnych występujących w sekwencji definiującej z wejściami i wyjściami. Tak więc, jeśli w definiującej sekwencji funkcji rekurencyjnej funkcje fa $\ Displaystyle f (x)}$${\ Displaystyle g (x)}$ i ${\ Displaystyle h (x, y)}$ pojawiają się wtedy wyrazy postaci „g (5) = 7” lub „h (3, 2)=10' może się pojawić. Każdy wpis w tej sekwencji musi być zastosowaniem podstawowej funkcji lub wynikać z powyższych wpisów przy użyciu kompozycji , rekurencji pierwotnej lub rekurencji μ . Na przykład, jeśli ${\ Displaystyle f (x) = h (x, g (x))}$ , a następnie, aby pojawił się „f (5) = 3”, terminy takie jak „g (5) = 6” i „h (5,6)=3' musi wystąpić powyżej. Obliczenia kończą się tylko wtedy, gdy końcowy wyraz podaje wartość funkcji rekurencyjnej zastosowanej do danych wejściowych.

Algorytm Markowa

system przepisywania ciągów znaków , który wykorzystuje reguły gramatyczne do operowania na ciągach symboli.

Zarejestruj maszynę

jest teoretycznie interesującą idealizacją komputera. Istnieje kilka wariantów. W większości z nich każdy rejestr może pomieścić 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ńczonego (lub dynamicznie rosnącego) magazynu zewnętrznego (widocznego na maszynach Turinga) można zrozumieć, zastępując jego rolę numeracją Gödla techniki: fakt, że każdy rejestr zawiera liczbę naturalną, pozwala na przedstawienie skomplikowanej rzeczy (np. ciągu, macierzy itp.) przez odpowiednią ogromną liczbę naturalną — jednoznaczność zarówno reprezentacji, jak i interpretacji można ustalić na podstawie teorii liczb z tych technik.

Oprócz ogólnych modeli obliczeniowych, niektóre prostsze modele obliczeniowe są przydatne w specjalnych, ograniczonych zastosowaniach. Na przykład wyrażenia regularne określają wzorce ciągów znakó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. Niedeterministyczne automaty przesuwające w dół to kolejny formalizm równoważny gramatyce bezkontekstowej. Prymitywne funkcje rekurencyjne są zdefiniowaną podklasą funkcji rekurencyjnych.

Różne modele obliczeń umożliwiają wykonywanie 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 .

Dalsza lektura

Podręczniki skierowane do informatyków

(Istnieje wiele podręczników w tej dziedzinie; ta lista jest z konieczności niekompletna).

•   Hopcroft, John E. i Jeffrey D. Ullman (2006). Wprowadzenie do teorii automatów, języków i obliczeń . 3. wydanie , czytanie, MA: Addison-Wesley. ISBN 978-0-321-45536-9 Jedno ze standardowych źródeł w tej dziedzinie.
•   Linza P. (2007). Wprowadzenie do języka formalnego i automatów . Wydawnictwo Narosa. ISBN 9788173197819 .
•   Michaela Sipsera (2013). Wprowadzenie do teorii obliczeń (wyd. 3). Nauka Cengage'a. ISBN 978-1-133-18779-0 .
•   Eitan Gurari (1989). Wprowadzenie do teorii obliczeń . Prasa informatyczna. ISBN 0-7167-8182-4 . Zarchiwizowane od oryginału w dniu 2007-01-07.
•   Hein, James L. (1996) Teoria obliczeń. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1 Delikatne wprowadzenie w tę dziedzinę, odpowiednie dla studentów drugiego roku studiów licencjackich informatyki.
•   Taylor, R. Gregory (1998). Modele obliczeniowe i języki formalne. Nowy Jork: Oxford University Press. ISBN 978-0-19-510983-2 Niezwykle czytelny podręcznik, odpowiedni dla studentów studiów wyższych lub początkujących doktorantów.
• Lewis, FD (2007). Podstawy informatyki teoretycznej Podręcznik obejmujący tematykę języków formalnych, automatów i gramatyk. Wydaje się, że nacisk kładziony jest na przedstawienie przeglądu wyników i ich zastosowań, a nie na dostarczanie dowodów wyników.
•   Martin Davis , Ron Sigal, Elaine J. Weyuker, Obliczalność, złożoność i języki: podstawy informatyki teoretycznej , wyd. 2, Academic Press, 1994, ISBN 0-12-206382-1 . Obejmuje szerszy zakres tematów niż większość innych książek wprowadzających, w tym semantykę programów i teorię kwantyfikacji . Skierowany do absolwentów.

Książki o teorii obliczalności z (szerszej) perspektywy matematycznej

•   Hartley Rogers Jr (1987). Teoria funkcji rekurencyjnych i efektywnej obliczalności , MIT Press. ISBN 0-262-68052-1
•   S. Barry'ego Coopera (2004). Teoria obliczalności . Chapmana i Halla/CRC. ISBN 1-58488-237-9 . .
•   Carl H. Smith , Rekurencyjne wprowadzenie do teorii obliczeń , Springer, 1994, ISBN 0-387-94332-3 . Krótszy podręcznik odpowiedni dla studentów studiów podyplomowych z informatyki.

Perspektywa historyczna

•   Richard L. Epstein i Walter A. Carnielli (2000). Obliczalność: funkcje obliczeniowe, logika i podstawy matematyki, z obliczalnością: oś czasu (wyd. 2) . Nauka Wadswortha/Thomsona. ISBN 0-534-54644-7 . .

Linki zewnętrzne

• Teorii Obliczeń w MIT
• Teorii Obliczeń na Harvardzie
• Logika obliczalności - teoria obliczeń interaktywnych. Główne źródło internetowe na ten temat.