Jak się nie ma o czym pisać, to się publikuje na blogu interesujące twierdzenia. Ten blog zapowiada się na nudnego bloga ;-)
Twierdzenie: Niech f będzie dowolną rekurencyjną funkcją zgadującą następny element danego ciągu a na podstawie elementów już pokazanych. Powiemy, że f zgadła a wtw od pewnego momentu wszystkie jej predykcje są prawdziwe. Istnieje rekurencyjny ciąg a' taki, że f nie jest w stanie go zgadnąć.
Dowód. Ustalmy f. a(0) będzie równe 0. Dla każdego n>0, niech a'(n) będzie równe predykcji f na podstawie a'(0), a'(1), ... , a'(n-1) powiększonej o 1. c.b.d.o
K. Kelly, "Learning Theory and Epistemology", na podstawie Putnama.
1 komentarz:
chcialam tylko powiedziec, ze dowod wydaje sie byc mozno przeklamana szarlataneria, no bo skoro istnieje a', to go pokażmy, hę? no to pokaż!
Prześlij komentarz