Warum gibt es mehr nicht berechenbare Funktionen als berechenbare?

Ich lese gerade ein Buch über Algorithmen und Komplexität. Im Moment lese ich über berechenbare und nicht berechenbare Funktionen und mein Buch besagt, dass es viel mehr Funktionen gibt, die nicht berechenbar sind als berechenbar. Tatsächlich heißt es, dass die Mehrheit nicht berechenbar ist. In gewissem Sinne kann ich das intuitiv akzeptieren, aber das Buch gibt weder einen formalen Beweis noch geht es ausführlich auf das Thema ein.

Ich wollte nur einen Beweis sehen / jemanden hier näher darauf eingehen lassen / genauer verstehen, warum es so viel mehr nicht berechenbare Funktionen als berechenbare gibt.

computability turing-machines combinatorics hsalin
quelle

Beim Vergleich zweier unendlicher Mengen muss die Semantik von "more" überarbeitet werden.

Raphael

Antworten:

Es gibt unzählige berechenbare Funktionen:

Jede berechenbare Funktion hat mindestens einen Algorithmus. Jeder Algorithmus hat eine endliche Beschreibung unter Verwendung von Symbolen aus einer endlichen Menge, z. B. endliche binäre Zeichenfolgen unter Verwendung der Symbole $\{0,1\}$ . Die Anzahl der mit bezeichneten endlichen Binärfolgen $\{0,1\}^*$ ist zählbar (dh die gleiche Anzahl wie die Anzahl der natürlichen Zahlen $\mathsf{N}$ ).

Daher kann es sein höchstens abzählbar viele berechenbare Funktionen geben. Es gibt mindestens zählbar viele berechenbare Funktionen, da für jedes die konstante Funktion berechenbar ist. $c\in \{0,1\}^*$ $f(x)=c$

Mit anderen Worten, es besteht eine Korrespondenz zwischen:

die Menge der berechenbaren Funktionen,
die Menge der Algorithmen,
, die Menge der endlichen Zeichenfolgen aus und $\{0,1\}^*$ $\{0,1\}$
, die Menge der natürlichen Zahlen. $\mathbb{N}$

Andererseits gibt es unzählige Funktionen über Zeichenfolgen (oder natürlichen Zahlen). Eine Funktion (oder $f:\mathbb{N} \to \mathbb{N}$ ) weist einen Wert für jeden Eingang. Jeder dieser Werte kann unabhängig von anderen gewählt werden. Es sind also Funktionen möglich. Die Anzahl der Funktionen über natürlichen Zahlen entspricht der Anzahl der reellen Zahlen. $f:\{0,1\}^* \to \{0,1\}^*$ $\mathbb{N}^\mathbb{N}=2^\mathbb{N}$

Da nur zählbar viele Funktionen berechenbar sind, sind die meisten von ihnen nicht berechenbar. In der Tat ist die Zahl der unberechenbaren Funktionen auch . $2^{\mathbb{N}}$

Wenn Sie sich dies intuitiv vorstellen möchten, denken Sie an natürliche und reelle Zahlen oder an endliche Binärzeichenfolgen und unendliche Binärzeichenfolgen. Es gibt weit mehr reelle Zahlen und unendliche binäre Zeichenfolgen als natürliche Zahlen und endliche Zeichenfolgen. Mit anderen Worten (für einen Beweis dieser Tatsache siehe Cantors diagonales Argument und Kardinalarithmetik ). $\mathbb{N} < 2^\mathbb{N}$

Kaveh
quelle

Gute Antwort! Was ich nicht verstehe (mir fehlt hier vielleicht etwas Triviales) ist, wie man

bekommt ?

N^{N} = 2^{N}

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

hsalin

Es ist Kardinalarithmetik. Schreiben Sie die natürlichen Zahlen in einer unendlichen Folge von natürlichen Zahlen in Binärform, die die Intuition ergeben sollen.

Kaveh

Warum muss diese Annahme wahr sein - "Jeder Algorithmus hat eine endliche Beschreibung unter Verwendung von Symbolen aus einer endlichen Menge"? Warum kann ein Algorithmus keine unendliche Beschreibung haben?

Roland Pihlakas

@ RolandPihlakas, das Teil der Definition eines Algorithmus ist (wenn Sie es vorziehen, ein Computerprogramm).

Kaveh

Hier ist eine "explizite" Konstruktion von unzähligen nicht berechenbaren Booleschen Funktionen. Sei eine feste nicht berechenbare Boolesche Funktion, die charakteristische Funktion des Halteproblems. Betrachten Sie die Menge der Funktionen Jedes ist nicht berechenbar und ist unzählbar. $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$

Es gibt also viele nicht berechenbare Funktionen, da wir "unendlich viele" Freiheitsgrade haben - tatsächliche Unendlichkeit statt "potentielle" Unendlichkeit wie im berechenbaren Fall.

Yuval Filmus
quelle