Przykładowo możemy zdefiniować nasz język formalny jako zbiór zapisów liczb pierwszych w systemie dziesiętnym. Pytanie, czy dany ciąg znaków należy do języka, jest wtedy pytaniem o to, czy dana liczba jest liczbą pierwszą. Podobnie możemy definiować nasz język jako zbiór palindromów, zbiór wszystkich ciągów złożonych wyłącznie z litery ‘a’ itp. Łatwo zauważyć, że dla jednych języków postawiony problem jest wyraźnie łatwiejszy niż dla innych.
Co dokładnie jednak znaczy „łatwiejszy”? Teoria obliczalności zajmuje się właśnie formalizowaniem tej intuicji, określając w sposób ścisły poziomy trudności języków.
Formalne modele obliczeń Aby móc formalnie mówić o możliwościach komputerów, należy po pierwsze formalnie zdefiniować czym są obliczenia komputerowe. Używa się w tym celu kilku modeli obliczeń. Do najczęściej badanych należą:
Deterministyczny automat skończony Najprostszy model obliczeń. Opisuje komputer jako maszynę o skończonej liczbie stanów i skończonej liczbie dopuszczalnych przejść pomiędzy stanami. Wybrane stany są oznaczone jako akceptujące. Wejściowy ciąg znaków jest odczytywany po jednym znaku, i po odczytaniu każdego znaku maszyna wykonuje przejście do nowego stanu zgodne z odczytanym znakiem.