Funkcja Busy Beaver jako przykład problemu nieobliczalnego

Wykłada: Marek Kłocewiak
Czas trwania: 2x45min
Opis: Rok temu opowiedziałem Wam o maszynie RAM jako modelu obliczeń równoważnym maszynie Turinga. Teraz chciałbym opowiedzieć o problemie, który nie jest RAM-obliczalny. Przy tej okazji dowiecie się troszkę o teorii rekursji.
Wymagania: Mile widziane będzie gruntowne zrozumienie, na czym polega ten model obliczeń, bowiem planuję jedynie sformalizowane przypomnienie podstawowych pojęć RAM-obliczalności.
Dodatkowe informacje: @jeszcze nie wiem, co by tu dodać@
Komentarze:

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License