Gibt es abzählbare Mengen, die nicht berechenbar sind?

Eine Menge ist zählbar, wenn sie eine Abweichung von den natürlichen Zahlen aufweist, und ist berechenbar aufzählbar (ce), wenn ein Algorithmus vorhanden ist, der ihre Mitglieder auflistet.

Jede nicht endliche rechnerisch aufzählbare Menge muss abzählbar sein, da wir aus der Aufzählung eine Bijektion konstruieren können.

Gibt es Beispiele für abzählbare Mengen, die nicht berechenbar sind? Das heißt, zwischen dieser Menge und den natürlichen Zahlen besteht eine Abweichung, aber es gibt keinen Algorithmus, der diese Abweichung berechnen kann.

computability semi-decidability Peter Olson
quelle

Die festgelegte Terminologie ist berechenbar . Viele Leute werden sagen, dass "abzählbar" und "aufzählbar" Synonyme sind. Ich habe die Frage entsprechend bearbeitet.

Andrej Bauer

@AndrejBauer, berechenbar und rekursiv sind synonims, oder?

Rus9384

@ rus9384 Ja. In Bezug auf das Vokabular sollte Klarheit herrschen, wie Robert Irving Soare in Turing-Post Relativized Computability und Interactive Computing (2011) schreibt : Bis 1995 war die Verwirrung unerträglich geworden. Ich habe einen Artikel über Berechenbarkeit und Rekursion für den Bullen geschrieben. von Sym. Logik (1996) über die Geschichte und die wissenschaftlichen Gründe, warum wir "berechenbar" und nicht "rekursiv" als "berechenbar" verwenden sollten. "Rekursiv" sollte "induktiv" bedeuten, wie es für Dedekind und Hilbert der Fall war. Anfangs waren nur wenige bereit, eine solche Änderung

vorzunehmen

Antworten:

Gibt es Beispiele für abzählbare Mengen, die nicht aufzählbar sind?

Ja. Alle Teilmengen der natürlichen Zahlen sind zählbar, aber nicht alle von ihnen sind aufzählbar. (Beweis: Es gibt unzählige verschiedene Untergruppen von aber nur unzählige Turing-Maschinen, die als Enumeratoren fungieren könnten.) Jede Untergruppe von , die Sie bereits kennen, ist also nicht rekursiv aufzählbar. Beispielsweise die Menge aller Zahlen, die Turing codieren Maschinen, die bei jeder Eingabe anhalten. $\mathbb{N}$ $\mathbb{N}$

David Richerby
quelle

@JorgePerez Nein und nein .

David Richerby

Dies beweist die Existenz, gibt aber kein Beispiel.

BlueRaja - Danny Pflughoeft

@ BlueRaja-DannyPflughoeft, ein Beispiel anzugeben ist dasselbe wie eines aufzuzählen. "Kannst du ein Beispiel für etwas geben, wofür du kein Beispiel geben kannst? Nein? Daher gibt es nichts, wofür du kein Beispiel geben kannst." Das ist mathematischer Konstruktivismus auf den Punkt gebracht.

Wildcard

Wäre das Bild der beschäftigten

eine solche Menge? Seit

Σ

$\Sigma$

Σ

$\Sigma$ streng zunimmt, bildet es trivialerweise eine Bijektion mit

, aber es gibt keine Turing-Maschine, die

aufzählen kann .

N

$\mathbb{N}$

Σ

$\Sigma$

Orlp

@Wildcard Nein, ein Beispiel anzugeben ist dasselbe wie eines zu definieren , nicht wahr ? Es gibt Sätze, die definiert werden können, aber nicht von einem Algorithmus aufgezählt werden können, wie z. B. den Satz aller Turing-Maschinen, die nicht anhalten.

Tanner Swett

Ja, jede unentscheidbare (nicht halbentscheidbare) Sprache hat diese Eigenschaft.

Betrachten Sie zum Beispiel die Menge . $L = \{(x,M) \mid M \text{ does not halt on input } x \}$

Angenommen, wir haben einen Algorithmus, der die Mitglieder dieser Menge auflisten kann. Wenn es einen solchen Algorithmus geben würde, könnten wir dieses verwenden, um das Halteproblem mit den Eingängen mit dem folgenden Algorithmus zu lösen : $x,M$

Wechseln Sie zwischen der Ausführung von Maschine für Schritte $M$ $n$ und das Aufzählen - te Element von . $x$ $n$ $L$

hält entweder an oder hält nicht an $M$ $x$ . Wenn es anhält, werden wir irgendwann ein in dem wir einen Haltezustand erreichen. Wenn es nicht aufhört, werden wir schließlich in unserer Aufzählung erreichen. $n$ $(M,x)$

Wir haben also eine Reduktion und können daraus schließen, dass es keine solche Aufzählung gibt.

Beachten Sie, dass solche Aufzählungen für teilentscheidbare Probleme existieren können. Sie können beispielsweise die Menge aller angehaltenen Maschinen-Eingabe-Paare auflisten, indem Sie nach Schritten alle möglichen Spuren aller Ausführungen von Turing Machine auflisten und diejenigen herausfiltern, die nicht in einem angehaltenen Zustand enden. $n$

jmite
quelle

Gibt es keine Sprachen mit unzähligen Komplexitäten?

Rus9384

@ rus9384 Ich bin mir nicht sicher, was du meinst. "Unzählbar" ist ein Maß für die Größe; "Komplexität" ist ein Maß dafür, wie schwierig es ist, sich zu entscheiden. Es gibt jedoch keine unzähligen Sprachen mit endlichen Zeichenfolgen: Wenn eine Sprache unzählig sein soll, müssen Sie unendliche Zeichenfolgen zulassen (oder ein unzähliges "Alphabet" oder beides).

David Richerby

@DavidRicherby, nun, jmite behauptet, dass jedes unentscheidbare Problem mit endlichen Zeichenketten arbeitet? Ich denke das gilt nur für jedes Turing-erkennbare, unentscheidbare Problem.

Rus9384

@ rus9384 Jede Sprache über einem endlichen Alphabet ist zählbar, und die Berechenbarkeit ignoriert normalerweise unendliche Alphabete. Siehe auch diese Frage .

jmite

@ rus9384 ja, eine sprache ist eine reihe von endlichen strings über einem endlichen alphabet. So etwas ist zählbar. Wenn Sie eine unzählige Sprache erhalten möchten, müssen Sie eine oder beide Instanzen von "endlich" aus dieser Definition entfernen. Aber wenn jemand nur "Sprache" sagt, bedeutet dies eine Reihe endlicher Zeichenfolgen über einem endlichen Alphabet.

David Richerby

In Berechenbarkeit Theorie beschäftigen wir uns mit Teilmengen von , wobei . Diese Sprache ist abzählbar, und so jede Teilmenge ist abzählbar. Darüber hinaus gibt es viele unentscheidbare, aber rekursiv aufzählbare Sprachen, deren Ergänzungen nicht rekursiv aufzählbar sind. Diese Sprachen sind Teilmenge von und sind daher abzählbar. $\Sigma^*$ $\Sigma = \{0,1\}$ $L \subseteq \Sigma^*$ $\Sigma^*$

fade2black
quelle

Wir beschäftigen uns nicht unbedingt mit binären Zeichenfolgen. Es gibt viele Fälle, in denen wir uns möglicherweise für Zeichenfolgen interessieren, und Menschen, die die Rechenbarkeit als "Rekursionstheorie" bezeichnen, befassen sich in der Regel direkt mit Mengen natürlicher Zahlen. (Das heißt, die Zahlen selbst werden als primitiv betrachtet und nicht als z. B. binäre Zeichenfolgen codiert.)

David Richerby

@DavidRicherby vor ein paar Wochen hast du mir das Gegenteil in den Kommentaren zu Yuvals Antwort behauptet. Und dies ist nicht der erste ähnliche Fall.

fade2black

Yuval gibt eine Menge Antworten und ich gebe eine Menge Kommentare ab, also müsstest du genauer sein. Ich stehe mit Sicherheit zu meinem obigen Kommentar, wenn ich also irgendwann das Gegenteil sagte, dann war ich entweder falsch oder verwirrt oder Sie haben mich missverstanden oder ich sprach über ein bestimmtes Szenario oder so etwas. Es tut mir leid, wenn ich Sie verwirrt habe, vor allem, wenn ich etwas Unklares oder Falsches gesagt habe!

David Richerby

@DavidRicherby, in der Tat kann jedes endliche Alphabet auf binär reduziert werden, also verstehe ich nicht, wie das wichtig ist. Oder haben wir in diesem Fall unendlich viele Buchstaben (wobei jede Zahl ein eindeutiges Symbol hat)?

Rus9384

{0, 1}

$\{0,1\}$