Jak można rozstrzygać, czy ma pewną sekwencję cyfr?

Otrzymaliśmy następujące ćwiczenie.

Pozwolić

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Wykazać, że jest obliczalne.$f$

Jak to jest możliwe? O ile mi wiadomo, nie wiemy, czy mokra zawiera każdą sekwencję cyfr (lub które), a algorytm z pewnością nie może zdecydować, że jakaś sekwencja nie występuje. Dlatego myślę, że nie jest obliczalny, ponieważ podstawowy problem jest tylko częściowo rozstrzygalny.$\pi$$f$

Są tylko dwie możliwości do rozważenia.

• Dla każdej dodatniej liczby całkowitej łańcuch pojawia się w postaci dziesiętnej . W takim przypadku algorytm, który zawsze zwraca 1, jest zawsze poprawny.$n$$0^n$$\pi$

• Jest największa liczba całkowita taka że pojawia się w postaci dziesiętnej . W takim przypadku następujący algorytm (o wartości zakodowany na stałe) jest zawsze poprawny:$N$$0^N$$\pi$$N$

  Zeros-in-pi(n):
   if (n > N) then return 0 else return 1
  

Mamy żadnego pojęcia, która z tych możliwości jest poprawna, lub co wartość jest słuszna w drugim przypadku. Niemniej jednak jeden z tych algorytmów gwarantuje poprawność. Zatem istnieje algorytm, który decyduje, czy ciąg zer pojawi się w ; problem jest rozstrzygalny.$N$$n$$\pi$

Zwróć uwagę na subtelną różnicę w następującym szkicu próbnym zaproponowanym przez gallais :

1. Weź losową maszynę Turinga i losowe dane wejściowe.
2. Albo obliczenia będą trwały na zawsze, albo w pewnym momencie się zatrzymają i istnieje (stała) funkcja obliczeniowa opisująca każde z tych zachowań.
3. ???
4. Zysk!

Alex ten Brink wyjaśnia:

uważaj na to, co mówi twierdzenie Haltinga: mówi, że nie ma jednego programu, który mógłby zadecydować, czy dany program się zatrzyma. Możesz łatwo utworzyć dwa programy, tak aby jeden z nich obliczył, czy dany program się zatrzymuje: pierwszy zawsze mówi „zatrzymuje się”, drugi „nie zatrzymuje się” - jeden program jest zawsze poprawny, po prostu nie możemy obliczyć, który z nich z nich jest!

sepp2k dodaje:

W przypadku Alexa żaden z algorytmów nie zwróci właściwego wyniku dla wszystkich danych wejściowych. W przypadku tego pytania jeden z nich to zrobi. Możesz twierdzić, że problem jest rozstrzygalny, ponieważ wiesz, że istnieje algorytm, który daje właściwy wynik dla wszystkich danych wejściowych. Nie ma znaczenia, czy wiesz, który to algorytm. 10

Publikuję tylko drobiazgowe wyjaśnienie odpowiedzi JeffE.

Wiemy, że istnieją dwie funkcje / przypadki, które mogą obliczyć funkcję f (n):

1. Funkcja, która zawsze zwraca true (dla wszystkich n istnieje n liczby kolejnych zer)
2. Funkcja, która zwróci true, jeśli n jest mniejsze niż liczba całkowita N, gdzie N jest zdefiniowane jako maksymalna długość kolejnych zer istniejących w podanej liczbie niewymiernej (w przeciwnym razie zwraca false).

Jedna i tylko jedna z tych funkcji może być poprawna. Nie wiemy który, ale wiemy na pewno, że istnieje odpowiedź. Obliczalność wymaga istnienia funkcji, która może ustalić odpowiedź w skończonej liczbie kroków.

Liczba kroków w przypadku 1 jest trywialnie związana tylko z powrotem 1.

W przypadku 2 liczba kroków jest również skończona. Dla każdej liczby całkowitej możemy zbudować maszynę Turinga która akceptuje, jeśli a w przeciwnym razie odrzuca w skończonym czasie. Zatem brak znajomości górnej granicy nie ma znaczenia. Dla każdego istnieje maszyna Turinga, a mianowicie , która poprawnie oblicza, czy (nie wiemy, które z nich są poprawne, ale to nie ma znaczenia, jedno istnieje).T N ( n ) n < N N N T N ( n ) n < $N$$T_N(n)$$n < N$$N$$N$$T_N(n)$$n < N$

Chociaż wybór dwóch przypadków może nie być możliwy (chociaż jeden wydaje się bardziej prawdopodobny niż inny), wiemy, że dokładnie jeden z nich musi być poprawny.

Na marginesie: nasze rozwiązanie zakłada, że ​​chociaż nie jesteśmy w stanie ustalić, która funkcja wywoła poprawną wartość, istota obliczalności nie opiera się na konstrukcji dowodu. Czysta egzystencja jest wystarczająca.

Krok 5 kolejnej próby dowodowej jest nieuzasadniony, aw rzeczywistości błędny - można tu znaleźć kontrprzykład . (dzięki, Yuval; to było jak najbardziej szkicowa część szkicu). Zostawiłem tutaj odpowiedź, ponieważ uważam, że błąd jest pouczający.

Po pierwsze: para odpowiedzi JeffE'a jest wystarczająca; f można obliczyć w obu kierunkach.

Krótki objazd do próby naszkicowania dowodu przez indukcję:
Przesłanka R : nie powtarza się. 1. Spójrz na w bazie 2. Ma to głównie na celu zmniejszenie liczby przypadków. 2. Bez względu na to, jak daleko w dół linii pójdziesz, będziesz zawsze znaleźć inny 1 gdzieś: alternatywą jest zerami, co oznaczałoby zaczyna powtarzać, co jest sprzeczne R . 3. To samo dotyczy zejścia na dół i znalezienia 0 . 4. Rozwiń do sekwencji dwucyfrowych: nie możesz przestać znajdować ani 01, ani 10 (to znaczy miejsc, w których się przełącza), ponieważ w przeciwnym razieπ π π $\pi$
$\pi$
$\pi$

$\pi$ zacznie powtarzać się w ciągu 1 lub 0 . Podobnie, nie możesz przestać znajdować 11 lub 00 , ponieważ w przeciwnym razie zacznie się powtarzać 1010101 ...
5. Krok indukcyjny: każda skończona sekwencja musi pojawiać się nieskończoną liczbę razy, ponieważ alternatywą jest to, że zaczyna powtarzać się jeden z krótszych sekwencji, co stoi w sprzeczności R .$\pi$