Teoria obliczalności, także teorii rekursji – dział teorii obliczeń zajmujący się badaniem jakie problemy są rozwiązywalne przy użyciu komputerów. Nie należy mylić teorii obliczalności z teorią złożoności obliczeniowej, zajmującej się badaniem jak efektywnie da się rozwiązywać różne problemy. Podstawowym obiektem badań teorii obliczalności są funkcje obliczalne.

Wprowadzenie Jednym z podstawowych zagadnień informatyki jest określenie potencjalnych możliwości komputerów przez zrozumienie problemów, które można za ich pomocą rozwiązywać. Współczesne komputery umożliwiają wyliczenie tak wielu rzeczy, że łatwo sobie można wyobrazić, iż rozwiązanie przez nie każdego problemu jest tylko kwestią czasu. Okazuje się jednak, że można wskazać problemy, których komputery nigdy nie będą potrafiły rozwiązać, niezależnie od dostępnych zasobów.

Aby formalnie definiować te problemy, informatyka teoretyczna bada możliwości komputerów do rozwiązywania następującego zadania:

Mając dany język formalny i ciąg znaków, określ czy ten ciąg należy do języka.