Niestandardowe modele obliczeń
Adam Michalik — adamm@mimuw.edu.pl
Wstęp
Pisząc programy komputerowe, czasem natrafiamy na trudne lub ciekawe problemy, których rozwiązanie nie jest oczywiste. Nie tak trudno wpaść na to, jak posortować ciąg liczb, ale jak napisać program, który sprawdza, czy dane równanie ma, czy też nie ma rozwiązań całkowitych?
Na tych warsztatach przekonamy się, że często ta trudność nie wynika z niedostatków naszego języka programowania czy sprzętu komputerowego, jest natomiast skutkiem głębszych właściwości procesów, które interpretujemy jako obliczenia. Przekonamy się również, że konkretna natura tych procesów bardzo mało wpływa na to, co da się obliczyć, a czego nie — okaże się, że jeżeli tylko mamy wystarczająco dużo w miarę łatwo dostępnej pamięci, to liczyć można na naprawdę prawie wszystkim. Zobaczymy kilka modeli, które czasem na pierwszy rzut oka bardzo mało przypominają komputery, a mimo to nie ustępują im wcale pod względem tego, co potrafią obliczyć.
Dowiemy się również, że pomimo tego, że liczyć można na prawie wszystkim, to są problemy, których nie da się rozwiązać algorytmicznie, choćbyśmy nie wiadomo jak się starali, a co gorsza, jest ich całkiem dużo i całkiem łatwo na nie przypadkiem trafić.
Program zajęć
Pierwszy dzień - wstęp do klasycznej teorii obliczeń — maszyny Turinga, funkcje obliczalne, kilka klasycznych wyników
Drugi dzień - modyfikacje modelu Turinga, oraz inne modele, mniej lub bardziej szalone
Trzeci dzień - modele wyraźnie słabsze od maszyn Turinga, oraz poboczne ciekawostki
Wymagania
- Umiejętność programowania na poziomie podstawowym
- Podstawowa znajomość logiki i teorii mnogości — czyli wiedza, co to są zbiory, funkcje i ciągi, oraz rozumienie, na czym polega dowodzenie twierdzeń (również przez indukcję).
Zadania kwalifikacyjne
Wyniki
Ocenę zadań kandydaci otrzymają wkrótce po ich wysłaniu (oczywiście będzie można je poprawiać), natomiast ostateczne wyniki kwalifikacji pojawią się 7 lipca.