Obliczenia: rachunki, dowody i gry

Co da się obliczyć, a czego nie? Dziś informatycy pytają o to rutynowo w kontekście przeróżnych problemów, jednak pierwsza odpowiedź na to pytanie na dobrą sprawę pojawiła się zanim ktokolwiek zdążył je zadać i wprawiła środowisko naukowe w zakłopotanie. Na początku XX wieku matematycy wierzyli, że każdy problem matematyczny da się rozstrzygnąć za pomocą obliczeń. U szczytu tego optymizmu, w 1928 roku, Dawid Hilbert postulował opracowanie uniwersalnej metody pozwalającego na obliczenie prawdziwości dowolnego stwierdzenia sformułowanego w języku logiki pierwszego rzędu – czyli za pomocą spójników logicznych I, LUB, NIE oraz kwantyfikatorów ISTNIEJE i DLA KAŻDEGO. Niecałe 10 lat później Alan Turing udowodnił, że taki algorytm nie istnieje. A więc są rzeczy, których obliczyć się nie da! Ale co to właściwie znaczy? Wydaje się, że wiemy, co to znaczy obliczyć. Jednak aby pokazać, że czegoś obliczyć się nie da, potrzebujemy więcej niż tylko nieformalnej intuicji. Potrzebujemy definicji obliczenia. W czasie wykładu poznamy trzy co raz ogólniejsze definicje obliczenia i zastanowimy się nad ich wzajemnymi związkami. Dowiemy się również, na czym polega najsłynniejszy problem otwarty teoretycznej informatyki, tj. czy P=NP.