Wie man argumentieren, dass, wenn wir das Halteproblem lösen könnte, dann könnten wir damit beschäftigt Biber lösen?

Question

Dies ist eine der Aufgaben von meiner Aufgabe. Ich habe eine Simulation Turing-Maschine, die eine beschäftigt Biber Funktion simulieren kann. Ich habe einige der Forschung getan um dieses Problem zu beweisen, aber immer noch nicht bekommen, damit ich vielleicht erraten Sie mir hier helfen kann. Eine gute Quelle für mich oder Beispiel zu gehen, wie dies zu argumentieren wäre gut.

Answer 1

Die Funktion BB ist definiert als die maximale Anzahl von Schritten eine Turing-Maschine von einer bestimmten Größe sein kann, durchführen und halt noch. (Eine andere Art, es auszudrücken ist, dass alle Turing-Maschinen der Größe x wird entweder halt in weniger als BB (x) Stufen oder laufen für immer).

Angenommen, Sie eine Turing-Maschine von Komplexität x haben, dann könnten Sie bestimmen, ob sie stoppen würde oder nicht laufen lassen, für BB (x) Zeitschritte - wenn es bis dahin nicht angehalten hatte, dann per Definition nie wird.

Ebenso, wenn Sie das Halteproblem lösen könnte, könnte man alle möglichen Turing-Maschinen der Größe x bewerten, beseitigen diejenigen, die nicht aufzuhalten, und nehmen BB (x) das Maximum der Laufzeiten der Reste zu sein.

Natürlich BB (x) ist nicht berechenbar - und in der Tat wächst schneller als jede mögliche berechenbare Funktion Sie nennen könnte -. Daher ist es nicht einmal angenähert werden kann

Answer 2

Sie können den Beweis finden Sie suchen hier , unten der Beweis, dass das Busy Beaver Problem ist unberechenbare.