Archiwa blogu

27. spotkanie – Teza Churcha w informatyce

18 czerwca, w gościnnych murach Akademii Ignatianum, odbyło się ostatnie w tym roku akademickim, spotkanie grupy Maquinaposzukującej implikacji filozoficznych w informatyce.

Tym razem Adam Olszewski rozważał odpowiedź na pytanie Czy teza Churcha ma jeszcze jakieś znaczenie dla informatyki? Zauważył, że algorytmiczny punkt widzenie jest doskonałym sposobem porządkowania rzeczywistości, w tym rzeczywistości informatycznej. W wyniku próby aksjomatyzacji informatyki powstała teza Churcha, będącej intuicyjnym pojęciem funkcji efektywnie obliczalnej. Niestety, tym samym został przedstawiony nierozwiązywalny, w tym ujęciu, problem stopu, którego nie jest w stanie obliczyć żadna funkcja rekurencyjna. Jednak problem nie został ostatecznie zamknięty jako nierozwiązany. Pojawiła się bowiem idea hiperobliczalności, która dzięki potencjalnej możliwości rozszerzenia pojęcia obliczalności, może przynieść rozwiązanie. W ten sposób teza Churcha została osłabiona.

W dalszej części referatu, Olszewski przedstawił wyniki teoretycznych rozważań, odnoszących się do prób implementacji hiperobliczalności w strukturze komputerowej. Przedstawił również modele obliczalności i związaną z nimi hierarchię arytmetyczną. Wskazał również kilka modeli alternatywnych.

Spotkanie zakończyło się dyskusją nad tym, czy możliwe jest by teza Churcha była fałszywa. Zastanawiano się również, jak taka możliwość zmieniłaby logikę i sposoby rozwiązywania nierozstrzygalnych dotychczas problemów.

Reklamy