Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 16

W pierwszej połowie dwudziestego wieku tacy matematycy, jak Kurt Gödel, Alan Turing i Alonzo Church odkryli, że pewnych problemów podstawowych nie można rozwiązać przy użyciu komputerów. Przykładem takiego zjawiska jest kwestia ustalenia, czy pewne twierdzenie matematyczne jest prawdziwe, czy fałszywe. Zadanie to jest chlebem powszednim matematyków. Wydawałoby się, że rozwiązywanie go przy użyciu komputerów byłoby czymś naturalnym, gdyż leży ono w obrębie królestwa matematyki. Jednak żaden algorytm komputerowy nie może zrealizować tego zadania.

Jedną z konsekwencji tego głębokiego wyniku było opracowanie koncepcji dotyczących teoretycznych modeli komputerów, które ostatecznie powinny pomóc w konstruowaniu rzeczywistych komputerów.

Teorie obliczalności i złożoności są ściśle powiązane. W teorii złożoności celem jest sklasyfikowanie problemów jako łatwych lub trudnych; tymczasem w teorii obliczalności problemy są klasyfikowalne jako te, które są możliwe do rozwiązania, lub takie, które nie są. Teoria obliczalności wprowadza wiele koncepcji wykorzystywanych w teorii złożoności.