Ist der Schnittpunkt unendlich vieler rekursiver Mengen rekursiv?

7

Ist der Schnittpunkt von unendlich vielen rekursiven Mengen iUi(wo jeder Satz anders ist) rekursiv? Rekursiv aufzählbar? Ich weiß, dass die Vereinigung nicht rekursiv sein muss, weil sie entscheidet, ob ein Element in der Menge enthalten istUi ist dasselbe wie die Entscheidung über das Halteproblem, da Sie für jedes Element entscheiden müssen, ob die Funktion, die if berechnet xUi für einige i wird beendet.


quelle
Sollten "unendlich rekursive Mengen" "unendlich viele rekursive Mengen" sein?
Andrej Bauer
@ AndrejBauer ja
Nach dieser Überlegung ist alles dasselbe wie die Entscheidung über das Stoppproblem. Ich möchte wissen, ob die Eingabenummer gleich 42 ist. Dazu muss ich entscheiden, ob das Programm, das nur anhält, wenn die Eingabenummer 42 ist, angehalten wird.
user253751

Antworten:

6

Da Sie bereits über Gewerkschaften Bescheid wissen, können Sie dies herausfinden, indem Sie sich an die Gesetze von de Morgan erinnern: Das Komplement einer Gewerkschaft ist das Komplement der Überschneidung von Komplementen. In diesem Sinne: lassenUisei die Menge von (Indizes von) Turing-Maschinen, die nicht innerhalb anhalteniAusführungsschritte. Also die ErgänzungNUi ist die Menge von (Indizes) jener Maschinen, die innerhalb der ersten anhalten i Schritte.

Jetzt haben wir:

ichU.ich=N.ich(N.U.ich)=N.H.
wo H.ist der Haltesatz. Die Ergänzung vonH. ist weder rekursiv noch rekursiv aufzählbar.

Übrigens geben Sie an, dass "Sie entscheiden, ob sich ein Element in der Menge befindet U.ich ist das gleiche wie die Entscheidung über das Halteproblem ... ", was nicht unbedingt wahr ist. Zum Beispiel, wenn ich setze U.ich={42}} für alle ich, dann alle U.ichsind entscheidbar. Sie müssen darauf achten, was IhreU.ichsind.

Andrej Bauer
quelle
8

Für jedes ichN., nehmen S.ich=N.{ich}}. Sie können jetzt jedes gewünschte Set als erstellenX.=ichX.S.ich.

Ebenso ist es einfacher zu lassen, dass eine Vereinigung rekursiver Mengen überhaupt etwas sein kann T.ich={ich}} und jetzt ein beliebiger Satz X. ist X.=ichX.T.ich.

David Richerby
quelle