Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić.

Rozważania tego typu nie są możliwe bez formalnego, matematycznego modelu komputera. Najczęściej używanym modelem jest maszyna Turinga. Taką maszynę można w uproszczeniu 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).

• 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 się zatrzyma (zob. Problem stopu).

Zobacz też

• język formalny
• automaty skończone
• automaty z stosem
• przegląd zagadnień z zakresu matematyki.
• przegląd zagadnień z zakresu informatyki

Teoria obliczeń

Theoretische Informatik Theory_of_computation Calculabilité 計算理論 Teoria da computação Computation การคณนา