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ę da się 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ę także węższe modele (tzn. takie, które nie pozwalają na wyrażenie dowolnej funkcji obliczalnej).

• funkcje pierwotnie rekurencyjne

O poniektórych problemach związanych z modelami obliczeń wiadomo, że są nierozstrzygalne. Dla przykładu nie istnieje algorytm, który rozstrzyga, czy dwa λ-wyrażenia są równoważne albo czy maszyna Turinga dla danego wejścia się zatrzyma (zob. Problem stopu).

Sprawdź też

• język formalny
• automaty skończone
• automaty ze stosem