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

130

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$

computability undecidability

— Raphael
źródło

Wybacz mi, że jestem całkowicie ignorantem, oczywiście brakuje mi jakiegoś fundamentalnego pytania, ale czy nie zawsze jest 0? Ponieważ 32 miejsce po przecinku, jeśli pi wynosi 0, czy to nie znaczy, że f (n) zawsze zwraca 1?

— Cory Klein

@CoryKlein: To jest formalny zapis języka ; indeks górny oznacza tutaj krotną konkatenację, tj. . jest tutaj tylko symbolem, a nie liczbą.

n

$n$

n

$n$

a^{5} = a a a a a

$a^5 = aaaaa$

0

$0$

— Raphael

Odpowiedzi:

133

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 :

Weź losową maszynę Turinga i losowe dane wejściowe.

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ń.

???

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

— JeffE
źródło

Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .

— Gilles,

Co by się stało, gdyby ktoś udowodnił, że stwierdzenie „Dla każdej dodatniej liczby całkowitej n łańcuch 0 ^ n pojawia się w postaci dziesiętnej π” jest nie do udowodnienia? Czy nadal twierdzilibyśmy, że problem ten jest rozstrzygalny, mimo że nigdy nie można było zbudować poprawnego algorytmu?

— Inni,

@Inne Tak, chcielibyśmy.

— JeffE

@JeffE W porządku. Czy możliwy jest dowód w intuicyjnej logice? Czy też konieczne jest tutaj prawo wyłączonego środka?

— Inne,

@Inne Jeśli dobrze zrozumiałem, idea jest następująca: jeśli dla każdego zdefiniujemy maszynę Turinga jak w pierwszej części odpowiedzi, to wiemy, że jeden z nich oblicza tę funkcję. Nie wiemy, który z nich (a gdyby twoje stwierdzenie zostało udowodnione, wiedzielibyśmy nawet, że nie można wiedzieć, który z nich), ale nadal wiemy, że istnieje taka maszyna Turinga , więc funkcja jest obliczalna.

N

$N$

M_{N}

$M_N$

— JiK

Publikuję tylko drobiazgowe wyjaśnienie odpowiedzi JeffE.

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

Funkcja, która zawsze zwraca true (dla wszystkich n istnieje n liczby kolejnych zer)
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). $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.

— JC
źródło

Nie wszyscy matematycy to akceptują - np. Intuicyjni nie.

— reinierpost

Zasadniczo podajesz długi przykład prawa wykluczonego środka, , lol. W logice intuicyjnej lub dowolnym systemie logicznym opartym na teorii typów dowód ten jest odrzucany.

P \lor \neg P

$P\lor\lnot P$

— Kaa1el,

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$

— Stephen Voris
źródło

Po pierwsze wiemy, że binarne rozwinięcie nie powtarza się, ponieważ jest nieracjonalne. Po drugie, istnieją liczby niewymierne, które nie zawierają ani 000, ani 111 w ich rozwinięciu binarnym, na przykład ten odpowiadający sekwencji Thue-Morse'a: 0,0110100110010110 ...

π

$\pi$

π

$\pi$

— Yuval Filmus

Ach, niebezpieczeństwa skoków indukcyjnych: P Dobry chwyt, dzięki.

— Stephen Voris,

Nawiasem mówiąc, jeśli wniosek jest błędny, czy bardziej sensowne jest dla mnie usunięcie go lub pozostawienie go i potwierdzenie poprzez edycję, że jest błędne?

— Stephen Voris,

@StephenVoris To zależy od tego, jak pouczający jest błąd. Zauważ, że pytanie, czy jest normalne (tzn., Że jej podstawowa ekspansja zawiera nieskończenie często każdą skończoną sekwencję cyfr karnych) jest jednym z dużych otwartych problemów teorii liczb.

π

$\pi$

b

$b$

b

$b$

— David Richerby,

@DavidRicherby Duży otwarty problem, mówisz? Tak, dobrze wiedzieć. Sądzę, że jest to rozsądny błąd edukacyjny, ponieważ dowodem na to, jak trudny jest problem pytania OP - oczywiście mogę się również mylić, biorąc pod uwagę głosowanie.

— Stephen Voris,