Dlaczego jest więcej funkcji, które nie są obliczalne niż funkcje obliczalne?

Obecnie czytam książkę o algorytmach i złożoności. W tej chwili czytam o funkcjach obliczalnych i niepoliczalnych, a moja książka stwierdza, że jest o wiele więcej funkcji, które nie są obliczalne niż obliczalne, w rzeczywistości większość jest niepoliczalna. W pewnym sensie intuicyjnie mogę to zaakceptować, ale książka nie daje formalnego dowodu ani nie rozwija zbyt wiele na ten temat.

Chciałem tylko zobaczyć dowód / pozwolić, żeby ktoś tutaj go rozwinął / bardziej szczegółowo zrozumieć, dlaczego jest tak wiele funkcji, które nie są obliczalne, niż funkcje obliczalne.

computability turing-machines combinatorics hsalin
źródło

Porównując dwa zestawy nieskończone, należy poprawić semantykę „więcej”.

Raphael

Odpowiedzi:

Istnieje niezliczona ilość funkcji obliczalnych:

Każda funkcja obliczalna ma co najmniej jeden algorytm. Każdy algorytm ma skończony opis przy użyciu symboli ze zbioru skończonego, np. Skończone ciągi binarne przy użyciu symboli . Liczba skończonych ciągów binarnych oznaczonych przez jest policzalna (tj. Taka sama jak liczba liczb naturalnych ). $\{0,1\}$ $\{0,1\}^*$ $\mathsf{N}$

Dlatego może być co najwyżej niezliczona liczba funkcji obliczalnych. Istnieje co najmniej policzalna wiele funkcji obliczalnych, ponieważ dla każdego można obliczyć funkcję stałą . $c\in \{0,1\}^*$ $f(x)=c$

Innymi słowy, istnieje zgodność między:

zestaw funkcji obliczalnych,
zestaw algorytmów,
$\{0,1\}^*$ , zbiór ciągów skończonych z i $\{0,1\}$
$\mathbb{N}$ , zbiór liczb naturalnych.

Z drugiej strony istnieje niepoliczalnie wiele funkcji nad łańcuchami (lub liczbami naturalnymi). Funkcja (lub ) przypisuje wartość dla każdego wejścia. Każdą z tych wartości można wybrać niezależnie od innych. Więc istnieje możliwa funkcja. Liczba funkcji nad liczbami naturalnymi jest równa liczbie liczb rzeczywistych. $f:\mathbb{N} \to \mathbb{N}$ $f:\{0,1\}^* \to \{0,1\}^*$ $\mathbb{N}^\mathbb{N}=2^\mathbb{N}$

Ponieważ tylko policzalnie wiele funkcji jest obliczalnych, większość z nich nie. W rzeczywistości liczba funkcji nieobliczalnych również wynosi . $2^{\mathbb{N}}$

Jeśli chcesz to zobrazować intuicyjnie, pomyśl o liczbach naturalnych i liczbach rzeczywistych lub o skończonych ciągach binarnych i nieskończonych ciągach binarnych. Istnieje znacznie więcej liczb rzeczywistych i nieskończonych ciągów binarnych niż liczb naturalnych i ciągów skończonych. Innymi słowy (na dowód tego faktu patrz przekątny argument Cantora i arytmetyka kardynalna ). $\mathbb{N} < 2^\mathbb{N}$

Kaveh
źródło

N^{N} = 2^{N}

$\mathbb{N}^\mathbb{N} = 2^\mathbb{N}$

Jest to arytmetyka kardynalna. Napisz liczby naturalne w nieskończonej sekwencji liczb naturalnych w formacie binarnym, co powinno dać intuicję.

Kaveh

Dlaczego to założenie jest prawdziwe - „Każdy algorytm ma skończony opis przy użyciu symboli ze zbioru skończonego”? Dlaczego algorytm nie może mieć nieskończonego opisu?

Roland Pihlakas,

@RolandPihlakas, który jest częścią definicji algorytmu (jeśli wolisz, program komputerowy).

Kaveh

$K$

F = {f : N \to {0, 1} : \forall x \in N, f (2 x) = K (x)} .

$F = \{ f \colon \mathbb{N} \to \{0,1\} : \forall x \in \mathbb{N}, f(2x) = K(x) \}.$

f \in F

$f \in F$

F

$F$

$R$

G = {g : N \to {0, 1} : \exists n \in N \forall m \geq n, g (m) = R (m) .}

$G = \{ g \colon \mathbb{N} \to \{0,1\} : \exists n \in \mathbb{N} \forall m \geq n, g(m) = R(m). \}$

g \in G

$g \in G$

R

$R$

G

$G$

G

$G$

Istnieje więc wiele funkcji, które nie są obliczalne, ponieważ mamy „nieskończenie wiele” stopni swobody - rzeczywistą nieskończoność zamiast „potencjalnej” nieskończoności, jak w przypadku obliczalnym.

Yuval Filmus
źródło