primitive rekursive funktionale Äquivalenz

Ist es bei zwei primitiven rekursiven Funktionen entscheidbar, ob sie dieselbe Funktion sind oder nicht? Nehmen wir zum Beispiel die Sortieralgorithmen A und B, die primitiv rekursiv sind. Obwohl es viele Algorithmen zum Sortieren gibt, beschreiben sie alle dieselbe Beziehung. Kann bei zwei primitiven rekursiven Implementierungen von A und B nachgewiesen werden, dass sie dieselbe Funktion darstellen? Bitte beachten Sie, dass es bei dieser Frage nicht um uneingeschränkte Rekursion geht und daher nicht durch die Eigenschaften von Turing-Maschinen eingeschränkt ist.

Ich weiß, wenn Sie zwei Funktionen haben, die anhalten und eine endliche Domäne haben, kann nachgewiesen werden, dass sie dieselbe Funktion sind, da Sie einfach jede mögliche Eingabe ausprobieren und die Ausgabe jeder Funktion vergleichen können. Meine Verwirrung ist, wenn ich mit Dingen arbeite, die an natürlichen Zahlen arbeiten, weil sie nicht endlich sind.

Wenn dies für die primitiven rekursiven Funktionen nicht entscheidbar ist, ist es für schwächere Klassen wie beispielsweise die elementaren rekursiven Funktionen möglich. Ich weiß auch, dass dies für schwächere Dinge wie Finite-State-Maschinen und deterministische Pushdown-Automaten möglich ist. Vielen Dank.

Es ist bekannt, dass die Äquivalenz selbst für CFGs bzw. CFGs nicht entscheidbar ist. PDAs (siehe auch Wikipedia ). Dies liefert einen Beweis dafür, dass dieselbe Eigenschaft für jedes Modell einer Obermenge von CFL unentscheidbar ist (durch eine einfache Sonderfallreduktion ).

Da das Lösen des Wortproblems für eine bestimmte CFL eindeutig primitiv rekursiv ist (aufgrund Ihres bevorzugten Parsing-Algorithmus), umfasst dies den Satz primitiver rekursiver Funktionen / Algorithmen.

Es ist nicht entscheidbar, durch den relativ einfachen informellen Beweis:

Bei einer beliebigen Turingmaschine können Sie folgende Funktion :$M$$f_M$

$$f_M(n) = \cases{0 \mbox{ if $M$ does not halt in $\leq n$ steps on empty input}\\ 1\mbox{ otherwise}}$$

Es ist eine grundlegende Tatsache der primitiven Rekursion, dass tatsächlich primitiv rekursiv ist (es "simuliert" für Schritte).$f_M$$M$$n$

Jetzt wird die Anweisung

$$M \mbox{ does not halt on empty input}$$

ist äquivalent zu

$$\forall n,\ f_M(n) = {\bf0}(n)$$ wobei die Funktion ist, die immer zurückgibt . Die Sprache der Funktionen, die nicht anhalten, ist unentscheidbar, und daher ist die obige Äquivalenz primitiver rekursiver Funktionen für allgemeines unentscheidbar .$\bf 0$$0$$f_M$

Es ist nicht allzu schwer zu zeigen, dass die Entscheidung über die Äquivalenz primitiver rekursiver Funktionen tatsächlich in liegt, dh genau so schwer wie die Bestimmung der Nichtterminierung von Turing-Maschinen oder die Entscheidung über arithmetische Sätze mit einem einzigen nicht begrenzten universellen Quantifizierer (und möglicherweise begrenzt und ).$\Pi^0_1$$\forall$$\exists$