Für Turing-Experten,
fleißige Biber (engl. Busy Beaver) sind Turingmaschinen, die möglichst viele 'I' von einer beliebigen Startposition aus auf das leere Band (nur 'B's)schreiben und zum Anhalten kommen.
Das Simulationsprogramm erzeugt alle TP's und führt sie virtuell aus, wobei eine Anzahl von 400 Bewegungen des L/S-Kopfs als Todschleife interpretiert wird und deshalb abbricht.
Da einige TP's unsinnige Werte enthalten wie mehrere Stopbefehle, nur Schieben in einer Richtung, nur Schreiben von 'B', werden solche TP's vorher ausgemustert und nicht getestet.
Beispiel für Biber2
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61:
| FOR F10:=1 TO 2 DO FOR F11:=0 TO 2 DO FOR F20:=0 TO 2 DO FOR F21:=0 TO 2 DO BEGIN FILLCHAR(ZU,SIZEOF(ZU),0); INC(ZU[F10]);INC(ZU[F11]); INC(ZU[F20]);INC(ZU[F21]); BESETZT:=TRUE; FOR K:=0 TO 2 DO IF ZU[K]=0 THEN BESETZT:=FALSE; IF (ZU[0]=1) AND BESETZT THEN BEGIN FOR BAND10:=0 TO 1 DO FOR BAND11:=0 TO 1 DO FOR BAND20:=0 TO 1 DO FOR BAND21:=0 TO 1 DO IF BAND10+BAND11+BAND20+BAND21>0 THEN FOR SCHIEB10:=0 TO 1 DO FOR SCHIEB11:=0 TO 1 DO FOR SCHIEB20:=0 TO 1 DO FOR SCHIEB21:=0 TO 1 DO IF SCHIEB10+SCHIEB11+SCHIEB20+SCHIEB21>0 THEN BEGIN INC(ANZAHL); FILLCHAR(B,SIZEOF(B),0); F:=1;PO:=MAX2;ZUG:=0; REPEAT CASE F OF 1 : IF B[PO]=0 THEN BEGIN B[PO]:=BAND10;INC(PO,2*SCHIEB10-1);F:=F10 END ELSE BEGIN B[PO]:=BAND11;INC(PO,2*SCHIEB11-1);F:=F11 END; 2 : IF B[PO]=0 THEN BEGIN B[PO]:=BAND20;INC(PO,2*SCHIEB20-1);F:=F20 END ELSE BEGIN B[PO]:=BAND21;INC(PO,2*SCHIEB21-1);F:=F21 END; END; INC(ZUG) UNTIL (F=0) OR (PO>MAX) OR (PO<1) OR (ZUG=GRENZE); IF F=0 THEN BEGIN AN:=0;FOR I:=1 TO MAX DO IF B[I]=1 THEN INC(AN); IF AN>=MAXIMUM THEN BEGIN Inc(BiberNr); Zeile:=IntToStr(BiberNr)+'. Biberprogramm'; Ausgabe.Items.Add(Zeile); Zeile:='1 '+ZEICHEN[0]+ZEICHEN[BAND10]+RICHT[SCHIEB10]+IntToStr(F10); Ausgabe.Items.Add(Zeile); Zeile:='1 '+ZEICHEN[1]+ZEICHEN[BAND11]+RICHT[SCHIEB11]+IntToStr(F11); Ausgabe.Items.Add(Zeile); Zeile:='2 '+ZEICHEN[0]+ZEICHEN[BAND20]+RICHT[SCHIEB20]+IntToStr(F20); Ausgabe.Items.Add(Zeile); Zeile:='2 '+ZEICHEN[1]+ZEICHEN[BAND21]+RICHT[SCHIEB21]+IntToStr(F21); Ausgabe.Items.Add(Zeile); Zeile:='Es sind '+IntToStr(AN)+' Striche.';Ausgabe.Items.Add(Zeile); MAXIMUM:=AN; Zeile:='Züge = '+IntToStr(ZUG)+' Position = '+IntToStr(PO); Ausgabe.Items.Add(Zeile);Ausgabe.Items.Add(''); END END END; |
Analog sind die anderen Suchprogramme aufgebaut
In jeder Version werden die gefundenen TP's angezeigt und zusätzlich gespeichert.
Bei Biber5 ist viel Geduld nötig oder bessere Programmierung
Viel Spaß beim Abholzen
Fiete