Zdecydowane właściwości liczb obliczalnych

Czy „twierdzenie Rice'a o liczbach obliczalnych” - to znaczy żadna nietrywialna właściwość liczby reprezentowanej przez daną rzeczywistość obliczalną nie jest rozstrzygalna - jest prawdą?

Czy to w jakiś bezpośredni sposób odpowiada połączeniom reali?

computability real-numbers computable-analysis

— Shachaf
źródło

Tak, twierdzenie Rice'a o realiach obowiązuje w każdej rozsądnej wersji reali obliczalnych.

Najpierw udowodnię pewne twierdzenie i następstwo, a później wyjaśnię, co to ma wspólnego z obliczalnością.

Twierdzenie: załóżmy $p : \mathbb{R} \to \{0,1\}$ to mapa i $a, b \in \mathbb{R}$ dwie rzeczywistości takie $p(a) = 0$ i $p(b) = 1$ . Następnie istnieje sekwencja Cauchy'ego $(x_i)_i$ takie, że $p(\lim_i x_i) \neq p(x_j)$ dla wszystkich . $j \in \mathbb{N}$

Dowód. Konstruujemy sekwencję par liczb rzeczywistych $(y_i, z_i)_i$ w następujący sposób:

\begin{aligned} (y_{0}, z_{0}) & = (a, b) \\ (y_{i + 1}, z_{i + 1}) & = {\begin{cases} (y_{i}, (y_{i} + z_{i}) / 2) & if p ((y_{i} + z_{i}) / 2) = 1 \\ ((y_{i} + z_{i}) / 2, z_{i}) & if p ((y_{i} + z_{i}) / 2) = 0 \end{cases} \end{aligned}

$\begin{align*} (y_0, z_0) &= (a, b) \\ (y_{i+1}, z_{i+1}) &= \begin{cases} (y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\ ((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\ \end{cases} \end{align*}$ Zauważ, że dla wszystkich

i \in N

$i \in \mathbb{N}$ :

$p(y_i) = 0$ i $p(z_i) = 1$
$|z_i - y_i| = |b - a| \cdot 2^{-i}$
$|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
$|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Zatem sekwencje i są Cauchy i zbiegają się do wspólnego punktu . Jeśli to bierzemy , a jeśli to bierzemy . $(y_i)_i$ $(z_i)_i$ $c = \lim_i y_i = \lim_i z_i$ $p(c) = 0$ $(x_i)_i = (z_i)_i$ $p(c) = 1$ $(x_i)_i = (y_i)_i$ $\square$

W następstwie: Załóżmy, że i dwie rzeczywiste, że i . Następnie każda maszyna Turinga albo działa wiecznie, albo nie działa wiecznie. $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$

Dowód. Zgodnie z tym twierdzeniem istnieje sekwencja Cauchy'ego taka, że dla wszystkich . Bez straty ogólności możemy założyć, że i . $(x_i)_i$ $p(x_j) \neq p(\lim_i x_i)$ $j \in \mathbb{B}$ $p(x_j) = 1$ $p(\lim_i x_i) = 0$

Niech będzie maszyną Turinga. Zdefiniuj sekwencję przez Sekwencja jest dobrze zdefiniowana, ponieważ możemy symulować do kroków i decydować, czy zatrzymała się w obrębie tak wielu kroków. Następnie zauważ, że jest sekwencją Cauchy'ego, ponieważ jest sekwencją Cauchy'ego (pozostawiamy to jako ćwiczenie). Niech . Albo lub : $T$ $y_i$

y_{i} = {\begin{cases} x_{j} & if T halts in step j and j \leq i \\ x_{i} & if T does not halt within i steps \end{cases}

$y_i = \begin{cases} x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\ x_i & \text{if $T$ does not halt within $i$ steps} \end{cases}$

T

$T$

i

$i$

(y_{i})_{i}

$(y_i)_i$

(x_{i})_{i}

$(x_i)_i$

z = lim_{i} y_{i}

$z = \lim_i y_i$

p (z) = 0

$p(z) = 0$

p (z) = 1

$p(z) = 1$

jeśli to działa wiecznie. Rzeczywiście, gdyby zatrzymał się po kroku , mielibyśmy , a więc byłoby sprzeczne z . $p(z) = 0$ $T$ $j$ $z = x_j$ $p(z) = p(x_j) = 1$ $p(z) = 0$
jeśli to nie działa wiecznie. Rzeczywiście, jeśli tak, to mielibyśmy , a więc , co jest sprzeczne z . $p(z) = 1$ $T$ $z = \lim_i x_i$ $p(z) = p(\lim_i x_i) = 0$ $p(z) = 0$ $\square$

Teraz możemy wyjaśnić, dlaczego daje to nam twierdzenie Rice'a o liczbach rzeczywistych. Dowody są konstruktywne, dlatego dają procedury obliczeniowe. Dotyczy to każdego modelu obliczalności i dowolnej struktury obliczeniowej rzeczywistych, które zasługują na miano tzw. W rzeczywistości możesz wrócić i przeczytać dowód jako instrukcje dotyczące budowania programu - wszystkie kroki są obliczalne.

Tak więc, jeżeli miała obliczalną mapę i obliczamy tak, że i , moglibyśmy zastosować procedury obliczeniowe wynikające z konstruktywnych dowodów twierdzenia i następstwa, aby stworzyć wyrocznię Haltinga. Ale wyrocznia Haltinga nie istnieje, dlatego każda mapa obliczalna jest stała. $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(1) = 1$ $p : \mathbb{R} \to \{0,1\}$

Uzupełniające: Pojawiło się również pytanie, czy twierdzenie Rice'a jest powiązane z połączeniem rzeczywistości. Tak, jest to zasadniczo stwierdzenie, że rzeczywiste są połączone.

Zauważmy najpierw, że ciągła mapa (bierzemy dyskretną topologię na ) odpowiada parze rozłącznych zbiorów clopen (zamkniętych i otwartych) w taki sposób, . Rzeczywiście, weź i . Ze względu jest ciągły i i są otwarte, i zostanie otwarty, rozłączne, i oczywiście obejmować wszystkie . I odwrotnie, każda para rozłącznych klopów pokrywających określa mapę ciągłą $p : X \to \{0,1\}$ $\{0,1\}$ $U, V \subseteq X$ $U \cup V = X$ $U = p^{-1}(\{0\})$ $V = p^{-1}(\{1\})$ $p$ $\{0\}$ $\{1\}$ $U$ $V$ $X$ $(U,V)$ $X$ $p : X \to \{0,1\}$ odwzorowujący elementy na i elementy na . $U$ $0$ $V$ $1$

Z tego dowiadujemy się, że przestrzeń jest odłączony wtedy i tylko wtedy, gdy istnieje ciągła mapa a takie, że oraz (musimy i tak, że mamy nietrywialne rozkład ). Jest inny sposób, aby powiedzieć to samo: przestrzeń jest połączona, jeśli i tylko wtedy, gdy wszystkie ciągłe mapy są stałe. $X$ $p : X \to \{0,1\}$ $a, b \in X$ $p(a) = 0$ $p(1) = b$ $a$ $b$ $X$ $X$ $X \to \{0,1\}$

W matematyce obliczeniowej mamy podstawowe twierdzenie: każda mapa obliczeniowa jest ciągła . Tak długo, jak długo jesteśmy w sferze obiektów obliczalnych, twierdzenie Rice'a faktycznie stwierdza, że pewna przestrzeń jest połączona. W przypadku klasycznego twierdzenia Rice'a omawiana przestrzeń jest przestrzenią częściowych funkcji obliczeniowych . $\mathbb{N} \to \mathbb{N}$

— Andrej Bauer
źródło

Dzięki! Właśnie tego szukałem. Masz pomysł na inne pytanie - czy jest to bezpośrednio związane z połączeniem reali?

— Shachaf

Dodałem wyjaśnienie, że twierdzenie Rice'a jest w rzeczywistości formą twierdzenia o powiązaniu.

— Andrej Bauer,

Załóżmy, że i określenie jeśli nie zatrzymuje się wewnątrz czynności i inaczej. Jeśli T nie zatrzymuje się, zbiega się do , w przeciwnym razie zbiega się do . Jeśli są obliczalne, to przy danym można wygenerować maszynę obliczającą granicę . Dlaczego to nie wystarczy, aby wykazać, że nie może być obliczalne, a nawet półdecydowalne (ponieważ nie zatrzymuje się, jeżeli wynosi

p (x) = 1, p (x^{'}) = 0

$p(x)=1, p(x')=0$

y_{i} = x

$y_i=x$

T

$T$

i

$i$

y_{i} = x^{'}

$y_i=x'$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

x, x^{'}

$x,x'$

T

$T$

y_{i}

$y_i$

p

$p$

T

$T$

p

$p$

1

$1$ na granicy). Oczywiście czegoś mi brakuje, ponieważ istnieją nietrywialne właściwości, które są w połowie nierozstrzygalne.

— Ariel,

Twoja definicja jest w porządku, ale potrzebujesz również obliczalnego współczynnika zbieżności sekwencji , aby twierdzić, że jego limit jest obliczalny. Ponieważ nie możemy obliczyć, przy którym indeksie sekwencja może przeskoczyć od do (lub moglibyśmy obliczyć, przy którym kroku zatrzyma się), nie można uzyskać takiego obliczalnego stopnia zbieżności.

T

$T$

y_{i}

$y_i$

i

$i$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

T

$T$

— Andrej Bauer,

-1

Nie. Lub przynajmniej dowód nie jest trywialny, ponieważ możesz wybrać jeden z (ogólnie wielu) możliwych sposobów obliczenia rzeczywistej, i możesz być w stanie wybrać taki ze strukturą, która jest całkowicie wrt do wybranej właściwości, tak aby nie redukujesz testowania właściwości do problemu zatrzymania.

Myślę też, że potrzebuję lepszego zrozumienia tego, co „nietrywialne” oznacza wrt na właściwości liczb. Według twierdzenia Rice'a „nietrywialne” jest w zasadzie nie syntaktyczne i nie jest implikowane przez składnię. Jednak każda obliczalna liczba rzeczywista nie jest pojedynczym programem, ale raczej klasą równoważności pełną programów.

— Boyd Stephen Smith Jr.
źródło

Nie jestem pewien, co masz na myśli. Czy próbujesz odróżnić obliczalne liczby rzeczywiste (np. , , itp.) Od programów, które je obliczają? Jasne, istnieje nieskończenie wiele programów, które obliczają każde obliczalne rzeczywiste, ale jest też nieskończenie wiele maszyn Turinga, które decydują się na dowolny rozstrzygalny język, a zwykłe twierdzenie Rice'a nie ma z tym żadnego problemu.

2

$2$

22 / 7

$22/7$

π

$\pi$

— David Richerby,

Czy różne reprezentacje liczb obliczalnych faktycznie mają znacząco różne właściwości obliczeniowe? Powiedzmy, że używam jednej z definicji na en.wikipedia.org/wiki/Computable_number , np. Rzeczywista obliczalna jest reprezentowana przez program, który przyjmuje ograniczenie błędu racjonalnego i daje przybliżenie w tym zakresie. Mam na myśli „trywialny” w tym samym sensie, co twierdzenie Rice'a: Właściwość, która ma zastosowanie do wszystkich obliczalnych liczb rzeczywistych lub do żadnej z nich. To prawda, że każda liczba może być reprezentowana przez wiele programów, ale dotyczy to również funkcji częściowych.

— Shachaf

@Shachaf To bardziej „trywialne” niż wymaga twierdzenie Rice'a. Właściwości „składniowe” są również trywialne - np. „Ma co najmniej 4 stany osiągalne ze stanu początkowego”, „ma połączony wykres stanu”, „nie ma przejścia, które zapisuje X na taśmie” itp. - i potrzebują nie dotyczy każdej maszyny.

— Boyd Stephen Smith Jr.

@DavidRicherby Tak, myślę, że to rozróżnienie jest konieczne. Jeśli jesteś w stanie pracować wyłącznie z reprezentacjami całkowitymi lub produktywnymi, masz większą moc.

— Boyd Stephen Smith Jr.

Twierdzenie Rice'a dotyczy właściwości funkcji cząstkowych, a nie algorytmów, które je obliczają. Podobnie pytam o właściwości liczb obliczalnych, a nie o programach, które je obliczają.

— Shachaf