O niemożliwościach

Paradoks Russella, zwany również potocznie paradoksem fryzjera, ma doniosłe konsekwencje dla matematyki i informatyki. Opowiedział o nich dr Wojciech Czerwiński podczas Dnia Odkrywców Kampusu Ochota UW.

Nie możesz obejrzeć wykładu? Posłuchaj podcastu:

Czy istnieją problemy, których nie potrafimy rozwiązać nie dlatego, że brakuje nam wiedzy, czasu albo mocy obliczeniowej, lecz dlatego, że rozwiązanie jest z zasady niemożliwe?

Dr Wojciech Czerwiński opowiada o jednych z najbardziej zaskakujących granic matematyki i informatyki. Punktem wyjścia jest paradoks Russella, znany również jako paradoks fryzjera. Jeśli fryzjer goli wszystkich i tylko tych mieszkańców miasta, którzy nie golą się sami, to czy powinien ogolić również siebie? Każda odpowiedź prowadzi do sprzeczności, a wniosek jest prosty: taki fryzjer nie może istnieć.

Ta pozornie zabawna historia prowadzi do poważnych pytań o podstawy matematyki. Prowadzący pokazuje, jak paradoks Russella podważył naiwną teorię zbiorów oraz dlaczego nie każdą kolekcję obiektów, którą potrafimy opisać, można bezpiecznie uznać za zbiór.

Wykład przybliża także niezwykłe właściwości nieskończoności. Czy jedne zbiory nieskończone mogą być większe od innych? Jak porównuje się liczebność liczb naturalnych, wymiernych i rzeczywistych? I dlaczego nie da się sporządzić pełnej listy wszystkich liczb rzeczywistych?

Kolejna część spotkania dotyczy granic obliczeń. Dr Wojciech Czerwiński wyjaśnia problem stopu: czy można napisać uniwersalny program, który dla dowolnego innego programu rozstrzygnie, czy ten kiedyś zakończy działanie, czy będzie pracował w nieskończoność?

Okazuje się, że taki algorytm nie istnieje. Nie jest to ograniczenie współczesnych komputerów ani brak odpowiednio dobrego oprogramowania. Problem stopu jest nierozstrzygalny z samej swojej natury. Prowadzący pokazuje, jak można tego dowieść, ponownie wykorzystując mechanizm przypominający paradoks fryzjera.

Od niemożliwego programu droga prowadzi do twierdzeń Gödla o niezupełności. Intuicyjnie mówią one, że w odpowiednio bogatym systemie matematycznym istnieją zdania, których nie można w jego ramach ani udowodnić, ani obalić. Nie chodzi więc o to, że matematycy nie znaleźli jeszcze dowodu. Taki dowód po prostu nie istnieje w przyjętym systemie.

Czy matematyka może odpowiedzieć na każde poprawnie postawione pytanie? Czy każdy prawdziwy fakt ma dowód? I co nierozstrzygalność oznacza dla programowania, algorytmów oraz naszego wyobrażenia o możliwościach komputerów?

Wykład pokazuje, że odkrywanie granic wiedzy nie jest porażką nauki. Przeciwnie — dowody niemożliwości należą do jej najważniejszych osiągnięć, ponieważ precyzyjnie wskazują, czego nie da się zrobić i dlaczego.

Dr Wojciech Czerwiński – matematyk i informatyk związany z Wydziałem Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.

Wykład został nagrany podczas Dnia Odkrywców Kampusu Ochota Uniwersytetu Warszawskiego 16 marca 2019 roku.

#matematyka #informatyka #logika #paradoksRussella #paradoksfryzjera #problemstopu #nierozstrzygalność #twierdzeniaGödla #nieskończoność #algorytmy #UniwersytetWarszawski #DOKO #Wszechnica

Organizator wykładu:

***

Ten utwór jest dostępny na licencji Creative Commons Uznanie autorstwa-Na tych samych warunkach 3.0 Polska.