Pytanie : Czy przewidywanie (jak zdefiniowano poniżej) sekwencji obliczalnych jest tak trudne, jak problem zatrzymania?
Opracowanie : „Przewidywanie” oznacza pomyślne przewidywanie, co oznacza popełnienie tylko skończonej liczby błędów w zadaniu próby przewidzenia n-tego bitu sekwencji, który ma dostęp do poprzednich bitów n-1 (zaczynając od pierwszego bitu i przechodząc przez cała nieskończona sekwencja obliczalna).
Istnieje prosty argument diagonalizacji (wynikający z Legg 2006), że dla dowolnego predyktora maszyny Turinga p istnieje obliczalna sekwencja, w której popełnia nieskończenie wiele błędów. (Skonstruuj sekwencję, której n-ty termin jest przeciwieństwem tego, co przewiduje p, biorąc pod uwagę poprzednie warunki n-1 w sekwencji). Zatem nie ma obliczalnego predyktora, który przewidziałby każdą obliczalną sekwencję. Wyrocznia zatrzymująca pozwoliłaby na budowę takiego predyktora. Ale czy możesz pokazać, że posiadanie takiego predyktora pozwala rozwiązać problem zatrzymania?
Więcej opracowania
Definicja (Legga)
czynnikiem P jest maszyna Turinga, które próbuje się przewidzieć n-ty bit sekwencji S uzyskać dostęp do wcześniejszych n-1 bitów. Jeśli przewidywanie nie zgadza się z n-tym bitem sekwencji, nazywamy to błędem . Powiemy, że p przewiduje S, jeśli p popełnia tylko skończenie wiele błędów na S. Innymi słowy, p przewiduje S, jeśli istnieje pewna liczba M w sekwencji st dla każdego m> M, p poprawnie przewiduje m-ty bit S dostęp do pierwszych bitów m-1.
Formalnie moglibyśmy zdefiniować maszynę predykcyjną jako posiadającą trzy taśmy. Sekwencja jest wprowadzana jako wejście bit po bicie na jednej taśmie, prognozy dla następnego bitu są dokonywane na drugiej taśmie (maszyna może poruszać się tylko w poprzek tej taśmy), a następnie jest taśma robocza, na której maszyna może poruszać się w obu kierunkach.
Proste wyniki
Zgodnie z powyższą definicją istnieje predyktor przewidujący wszystkie liczby wymierne. (Użyj standardowego zygzakowatego wyliczenia wymiernych. Zacznij od przewidywania pierwszego wymiernego na liście, jeśli wystąpi błąd, przejdź do następnego wymiernego.). Podobnym argumentem jest predykator, który ma dostęp do N, jest w stanie przewidzieć wszystkie sekwencje złożoności Kołomogorowa mniejsze lub równe N. (Uruchom wszystkie maszyny N-bitowe równolegle i weź pod uwagę maszynę, która zatrzyma się jako pierwsza Możesz popełnić tylko skończenie wiele błędów).
Citation Shane Legg 2006 http://www.vetta.org/documents/IDSIA-12-06-1.pdf (nie autor tego postu)