Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Busy Beaver A34
Bei Aufgabe A34 hat unsere Gruppe gesamt 0 Punkte erreicht.
Hat jemand einen Ansatz, wie man da ordentlich rangeht?
Die nächste Bonusaufgabe sieht ja wieder ähnlich aus.
Die Kurzfassung meiner Lösung lautet:
So wie ich die Aufgabenstellung der A34 gelesen habe, musste man zeigen, dass es keine bijektive Funktion gibt, die auf BB1 abbildet.
Da BB(n) schon nicht berechenbar ist, sollten können wir (n,BB(n)) schon gar nicht erst angeben.
Wenn wir wie in Aufgabe A28 (die Aufgabe, in der man die Äquivalenz von rekursiver Aufzählbarkeit einer Sprache und die Existenz einer bijektiven Funktion, die auf die Sprache abbildet, zeigen soltle) vorgehen, dann klappt das ja nicht, da wir die Maschine Mg (aus der Vorlesung) weder mit einer natürlichen Zahl starten, dann aber nicht auf einen Wert aus BB(n) kommen können.
Somit gäbe es keine bijektive Funktion, die auf Elemente der Sprache BB1 abbildet und damit ist BB1 nicht rekursiv aufzählbar.
Anscheinend war das jedoch komplett falsch mit 0 von 4 Punkten. Korrektur habe ich noch nicht.
Weiß irgendjemand was dabei so falsch ist, bzw. was ein richtiger Ansatz gewesen wäre? Ich komme einfach nicht auf den Fehler an der Überlegung.
Wenn ich die Aufgabe nicht verstanden habe, dann habe ich ja wohl keine Chance die Aufgabe 40 halbwegs richtig zu bearbeiten.
Der Fehler ist, dass (n,BB(n)) =/= BB(n) ist. Der Widerspruch klappt, aber nur wenn du eine bij. Funktion f:{0,1}* → BB angibst. Du brauchst also eine Maschine, die unter der Annahme, dass BB1 berechenbar ist BB berechnet.
1 „Gefällt mir“