W informatyce, teoria obliczalności to 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.

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.

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.

czytaj dalej: [2], [3]