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ż
Przypisy
Linki zewnętrzne
Mathematical theory of computation (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].
- p
- d
- e
główne obszary |
|
---|---|
wybrane zagadnienia |
|
- p
- d
- e
logika matematyczna | |
---|---|
metamatematyka | |
teoria mnogości | |
teoria obliczeń |
|
inne |
- p
- d
- e
- БРЭ: 1810389
- Catalana: 0267888