Teoria obliczeń
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/250px-Maquina.png)
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ż
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]Linki zewnętrzne
[edytuj | edytuj kod]Mathematical theory of computation (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].