Nennen wir Sigma(n) die maximale Zahl der mit n Zuständen schreibbaren 1. Dann ist die Funktion Sigma nicht berechenbar (weil sie zu schnell wächst).
Trotzdem gibt es Abschätzungen und auch konkrete Schranken für kleine Argumente, erhalten durch vollständiges Aufzählen der interessierenden Maschinen.
Das geht natürlich im Allgemeinen nicht gut - wir müssen sehr viele Maschinen auflisten und für jede das Halteproblem lösen. Für kleine n können wir aber in den meisten Fällen die Bandmuster durch reguläre Sprachen beschreiben.
Im Vortrag werde ich für n = 5 auf diese Weise den bisher aussichtsreichsten Kandidaten analysieren, aber auch eine Maschine zeigen, deren Bandmuster nicht periodisch, sondern selbstähnlich explodieren.
Literatur: Heiner Marxen: Busy Beaver
Übungsaufgabe: Welche Maschine leistet Sigma(2) = 4? (Zwei Zustände, und ein zusätzlicher Haltzustand.)
this page is best viewed with any browser