Endliche Darstellungen und Programmiersprachen Zählbar unendlich

Ich gehe einige der erforderlichen Mathematik in Bezug auf die Automatentheorie und endliche Darstellungen durch.

Ich habe folgendes gelesen:

Wenn ∑ ein endliches Alphabet ist, ist die Menge aller Zeichenfolgen über dem Alphabet (∑ *) zählbar unendlich .
Die Menge aller möglichen Sprachen über ein Alphabet ∑ ist unzählig unendlich .

Wie kann die Menge der möglichen Sprachen aus Σ sein unzählbar unendlich , noch die mögliche Anwendung dieses Alphabet in eine Sprache sein abzählbar ?

Kann ich die Antwortenden bitten, nicht zu viele komplexe Notationen zu verwenden, da ich kein Mathematik-Zauberer bin?

discrete-mathematics Andrew S.
quelle

Verstehst du den Unterschied zwischen zählbar unendlich und unzählbar unendlich oder gibt es nur eine Art von unendlich in deinem Kopf? Haben Sie eine vage Vorstellung davon, wie diese Unterscheidung zustande kam (vgl. Cantor)?

Vielen Dank. Ich komme auf die Idee von unzähligen Unendlichkeiten. Es handelt sich im Wesentlichen um eine Menge, die nicht wie eine Menge reeller Zahlen indiziert werden kann, da beispielsweise die mögliche Anzahl inkrementeller Schritte zwischen beispielsweise 1,0 und 2,0 unermesslich unendlich ist.

Andrew S

"Unermesslich unendlich" ist kein Fachbegriff AFAIK (wenn ja, ignorieren Sie Folgendes). Wenn Sie damit meinen, dass es eine (zählbare oder nicht) unendliche Anzahl von Schritten zwischen 1 und 2 gibt, dann sind Sie in die Falle geraten, die Unendlichkeit zu unterschätzen. Das reelle Zahlenintervall [1; 2] ist zwar unzählbar, aber die Rationalen im gleichen Intervall sind zählbar, obwohl es eine (zählbare) unendliche Anzahl von ihnen und keine diskreten Schritte gibt!

Antworten:

Hier ist eine einfachere Situation, die den Unterschied hervorhebt. Die Menge der endlichen Binärzeichenfolgen ist zählbar. Die Menge der unendlichen Binärzeichenfolgen ist unzählig.

Ein weiteres Beispiel: Der Satz von Zahlen mit endlicher Dezimalerweiterung ist zählbar. Die Menge der Zahlen mit unendlicher Dezimalerweiterung ist unzählig.

Der Grund dafür, dass die Anzahl der Sprachen unzählig ist, ist, dass Sie unendlich viele Möglichkeiten haben: Für jedes Wort können Sie entscheiden, ob es in der Sprache ist oder nicht. Deshalb ist es wie die oben betrachtete unendliche Binärzeichenfolge.

Yuval Filmus
quelle

Die ersten beiden Argumente überzeugen nicht, eine unendliche Menge von Binärzeichenfolgen kann nur unendlich gezählt werden, 0, 1, 10, 11, ..... unendlich (richtig ich, wenn ich falsch liege, was ich wahrscheinlich bin). Ihr letztes Beispiel gefällt mir jedoch.

Andrew S

Die Menge aller endlichen Zeichenketten ist zählbar - das sind 0, 1, 10, 11, ... Die Menge aller unendlichen Zeichenketten ist unzählbar. Sie können nicht einmal einen von ihnen schreiben, da sie alle unendlich sind. Beispiele können sein

0^{ω}

$0^\omega$ (unendlich viele Nullen),

(01)^{ω}

$(01)^{\omega}$ (ein sich wiederholendes Muster),

1010^{2} 10^{3} 10^{4} 10^{5} \dots

$1010^210^310^410^5\dots$ (ein sich nicht wiederholendes Muster) und viele, viele mehr. Unzählig mehr. Mehr als Sie beschreiben können.

Yuval Filmus

@ Andrews, Sie erwägen endliche binäre Zeichenfolgen. Schauen Sie sich Cantors diagonales Argument an, um den entscheidenden Unterschied zu sehen.

vonbrand

Vielen Dank Leute, ich werde heute Nacht schlafen (na ja, ein bisschen).

Andrew S

Ich denke nicht, dass diese Antwort eine wertvolle Intuition liefert. 1) Es gibt nicht trivial zählbare Sätze von unendlichen Strings, z. B. dargestellt durch Turing-Maschinen oder Büchi-Automaten. 2) Die rationalen Zahlen enthalten solche, die unendliche Dezimalerweiterungen haben, aber die Menge ist zählbar. 3) Die Eigenschaft, "unendlich viele Möglichkeiten zu haben", ist zu vage, um nützlich zu sein.

Raphael

Fragen der Form "wie können" sind immer schwer zu beantworten, da sie nach Intuition fragen. Die Intuition hier ist: Unzählig bedeutet "zu viele" im Weg. Warum gibt es "viel mehr" Objekte der einen als der anderen Art? Nun, sie sind es einfach.

Stellen Sie sicher, dass Sie die Fakten verstehen.

Gegeben eine endliche Menge $\Sigma$ konstruiere die Bijektion zu $\mathbb{N}$ für die Menge aller (endlichen) Strings vorbei $\Sigma^*$ .

Hinweis: $\Sigma^n$ ist endlich, also kombiniert man eine verallgemeinerte Nummerierung von $\Sigma^n$ mit $n$ sollte arbeiten.\
Zeigen Sie, dass die Menge aller Tupel von Naturtönen, dh $\mathbb{N}^+ = \bigcup_{i \geq 1} \mathbb{N}^i$ ist zählbar.

Hinweis: Konstruieren Sie die Bijektion für $\mathbb{N}^i$ zuerst (vgl. Cantor) und kombinieren Sie diese erneut mit $i$ .
Zeigen Sie, dass die Leistung von $\mathbb{N}$ dh $2^{\mathbb{N}}$ ist unzählig.

Hinweis: Verwenden Sie die Diagonalisierung.

Wenn Sie dies getan haben, haben Sie alle Werkzeuge, um zum Beispiel das zu zeigen

Alle algorithmischen (oder allgemeiner endlich dargestellten) Konzepte sind aber zählbar
Die Menge aller Funktionen über Naturals oder Real oder ... ist unzählig.

Raphael
quelle