Eine Variante der Busy-Beaver-Funktion

Als ich diese Frage " Natürliche RE unentscheidbare Probleme, aber nicht Turing-vollständig " las, kam mir folgende Sprache in den Sinn:

Wenn die beschäftigte Biberfunktion ist (maximal erreichbare Punktzahl unter allen anhaltenden Turing-Maschinen mit 2 Symbolen und n-Zustand des oben beschriebenen Typs, wenn sie auf einem leeren Band gestartet werden), definieren Sie die Funktion: $\Sigma(\cdot)$

B B (⟨ M ⟩) = {\begin{cases} 1 & ⟨ M ⟩ computes Σ (\cdot) \\ 0 & otherwise \end{cases}

$BB(\langle M \rangle) = \begin{cases} 1 & \text{$\langle M \rangle$ computes $\Sigma(\cdot)$}\\ 0 & \text{ otherwise} \end{cases}$

Definieren Sie nun die Sprache:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

Ist rekursiv aufzählbar? (Es sollte re: simulieren Sie einfach parallel M mit allen TMs gleicher Länge, und wenn anhält und ein anderes mit einer höheren Punktzahl anhält, fügen Sie M zur Aufzählung hinzu). $L$ $M$ $M'$

Können wir das Halteproblem auf reduzieren ? (Es scheint, dass es das Anhalten der beschäftigten Biber nicht "erfassen" kann) $L$

computability turing-machines Vor
quelle

Istdie Anzahl der Staaten?

| ⟨ M ⟩ |

$|\langle M \rangle|$

Pål GD

Wann werden Sie ein aufzählen , das nicht in ? kann nicht RE sein, es sei denn, Sie listen alle seine Mitglieder auf, und die von Ihnen beschriebene Prozedur zählt nur diejenigen auf, die tatsächlich anhalten.

M

$M$

L

$L$

L

$L$

Steven Stadnicki

@ PålGD: Ja, es ist die Anzahl der Zustände (Stoppzustand ausgeschlossen)

Vor

@StevenStadnicki: Ich habe implizit angenommen, dass nur Maschinen enthält, die anhalten ... vielleicht sollte ich es in der Frage klarstellen (lassen Sie mich ein wenig darüber nachdenken, vielleicht macht es die Frage trivial).

L

$L$

Vor dem

@Kaveh Es ist nicht einmal ein Versprechen Problem - Sie können einfach definieren

als (wie ich die OP soll glauben)

L

$L$

L = {⟨ M ⟩ | M halts \land B B (⟨ M ⟩) = 0}

$L=\{\langle M\rangle | M\ \text{halts} \wedge BB(\langle M\rangle) = 0\}$

Steven Stadnicki

Antworten:

Ich kann nicht glauben, dass ich das vorher nicht gesehen habe - aber ja, mit einem Orakel für Sie das Halteproblem lösen. Offensichtlich gibt uns ein Orakel für "rekursiv" alle nicht beschäftigten Biber-Haltemaschinen, daher lautet die Frage "können wir rekursiv in herausfinden, was die beschäftigten Biber sind?". Definieren Sie als Zählfunktion des 'zweitgrößten Bibers'; das heißt, die zweithöchste erreichbare Punktzahl unter allen haltenden TMs mit zwei Symbolen und Zuständen. Der Trick dabei ist, dass es eine rekursive Funktion so dass $L$ $L$ $L$ $\Sigma_2(n)$ $n$ $f()$ (es ist fast sicher, dass tatsächlich den Trick macht, aber das erfordert das Wissen, dass die BB-Funktion streng zunimmt): bei einer Maschine der Größe , die druckt 1s auf dem Band und dann angehalten, gibt es einige und zwei Maschinen mit einer Größe von jeweils , die genau 1s und genau drucken. $\Sigma(n)\leq\Sigma_2(f(n))$ $f(n)=n+1$ $M$ $n$ $\Sigma(M)$ $c\gt 1$ $\leq cn$ $\Sigma(M)$ 1s auf ihren Bändern - und dies gilt für eine 'beschäftigte Biber'-Maschine , obwohl wir explizit kennen. Dies bedeutetdass ein auf dem ‚zweiten Besetzt Beaver‘ -Funktion für gebunden ist gibt ein für die Besetztbiber Funktion gebunden ; aber dann dieses ist, ist es einfachdas Halteproblem für eine TM zu lösen der Größe - wenn dann sagendass stoppt; Andernfalls finden Sie die am längsten laufende Maschine der Größe in $\Sigma(M)+1$ $M$ $M$ $f(n)$ $n$ $M$ $n$ $\langle M\rangle\in L$ $M$ $f(n)$ $L$ (Dies kann rekursiv erfolgen, da es nur endlich viele Maschinen der Größe ) und simulieren für so viele Schritte, wie diese Maschine zum Anhalten benötigt. Wenn innerhalb dieser Zeit nicht anhält, kann unmöglich anhalten. $\leq f(n)$ $M$ $M$ $M$

Steven Stadnicki
quelle

Vielen Dank; Inspiriert von Ihrer Antwort fand ich eine schnelle (triviale) -: direkte Reduzierung des Halteproblems in einer separaten Antwort.

Vor dem

Dies ist eine überarbeitete Version von Stevens guter Antwort mit einer expliziten Reduzierung des Halting-Problems.

Angesichts build , die ausgeführt werden auf und wenn es nach rechts des Band stoppt geht, schreibt einen 0 und Halt. $\langle M \rangle, w$ $M'$ $M$ $w$

Wenn anhält, ist weil es ein äquivalentes TM derselben Größe gibt, das eine 1 schreibt und anhält; Wir können also den Entscheider für , um zu überprüfen, ob auf anhält ( an anhält, wenn ). $M'$ $BB(M')=0$ $L$ $M$ $w$ $M$ $w$ $M' \in L$

... es stellte sich heraus, dass die Frage in der Tat trivial ist :-)

Vor
quelle