Siła maszyn Turinga Maszyny Turinga potrafią rozpoznawać wszystkie języki bezkontekstowe i wiele innych języków, jak na przykład podany wyżej język liczb pierwszych. Z powodu unikalnej możliwości „cofania” swoich dotychczasowych obliczeń, maszyna Turinga może analizować podany ciąg liter bardzo długo, potencjalnie nawet nigdy się nie zatrzymując. Dlatego mówi się, że maszyna rozpoznaje dany język, jeśli dla dowolnego wejścia zatrzymuje się z poprawnym wynikiem. Języki, które w ten sposób mogą być rozpoznawane nazywane są językami rekursywnymi. Możemy też zdefiniować szerszą klasę języków, zawierającą te języki, dla których maszyna Turinga zatrzymuje się z poprawną odpowiedzią na każdym poprawnym ciągu, ale może analizować nieskończenie długo ciągi, które nie należą do języka. Języki rozpoznawalne w ten sposób nazywają się językami rekursywnie przeliczalnymi.