Teoria obliczeń

Artystyczna reprezentacja Maszyny Turinga, jednego z modeli obliczeń

Teoria obliczeń – dział informatyki i matematyki, który dzieli się na: teorię automatów i języków formalnych, teorię obliczalności oraz teorię złożoności. Teoria automatów zajmuje się definicjami i własnościami modeli obliczeń (modelami maszyn liczących). W uproszczeniu zajmuje się ona odpowiedzią na pytanie czym jest komputer, teoria obliczalności odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a teoria złożoności – odpowiedzą na pytanie jakim kosztem (czasowym i pamięciowym) da się to zrobić^[1].

Modele obliczeń stosuje się w praktyce, na przykład model zwany automatem skończonym jest wykorzystywany w architekturze komputerów, budowie kompilatorów i w przetwarzaniu tekstu (przetwarzanie języka naturalnego, synteza mowy). Inny model, nazywany gramatyką bezkontekstową, jest używany przy projektowaniu języków programowania i sztucznej inteligencji^[1].

Najogólniejszym modelem obliczeń jest maszyna Turinga. Można ją rozumieć jako komputer o nieograniczonych zasobach pamięci. Inne używane modele, takie jak: rachunek lambda, rachunek kombinatorów, algorytmy Markowa, funkcje rekurencyjne są sobie równoważne w tym sensie, że wszystko co jest obliczalne na jednym z nich, da się też obliczyć na maszynie Turinga. Rozważa się również węższe modele tzn. takie, które nie pozwalają na wyrażenie dowolnej funkcji obliczalnej, np. funkcje pierwotnie rekurencyjne. O niektórych problemach związanych z modelami obliczeń wiadomo, że są nierozstrzygalne. Na przykład nie istnieje algorytm, który rozstrzyga czy dwa λ-wyrażenia są równoważne lub czy maszyna Turinga dla danego wejścia zatrzyma się (zob. problem stopu). Podstawowym obiektem badań teorii obliczalności są funkcje obliczalne. Problem P vs NP jest określany jako najważniejszy nierozwiązany problem matematyczny w informatyce.

Zobacz też

Przypisy

↑ ^a ^b MichaelM. Sipser MichaelM., Wprowadzenie do teorii obliczeń .

Linki zewnętrzne

Mathematical theory of computation (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].

[:0-1] MichaelM. Sipser MichaelM., Wprowadzenie do teorii obliczeń .

[1]

główne obszary	teoria informacji i kodowania algorytmy i struktury danych teoria i modele obliczeń
wybrane zagadnienia	informacja problem obliczeniowy heurystyka teoria obliczalności teoria automatów język formalny system formalny teoria typów teoria języków programowania paradygmat programowania geometria obliczeniowa złożoność obliczeniowa obliczenia równoległe obliczenia rozproszone kryptologia informatyka kwantowa algorytm kwantowy

logika matematyczna	algebraiczna mereologia rachunek zdań teoria dowodu teoria modeli teoria rekursji teoria typów
metamatematyka	metalogika
teoria mnogości	opisowa algebra zbiorów arytmetyka liczb kardynalnych arytmetyka liczb porządkowych teoria PCF
teoria obliczeń	teoria obliczalności teoria złożoności
inne	teoria kategorii filozofia matematyki