Autor Beitrag
Fiete
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 617
Erhaltene Danke: 364

W7
Delphi 6 pro
BeitragVerfasst: Mo 14.07.08 13:19 
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
ausblenden volle Höhe Delphi-Quelltext
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                        // Folgezustände
    FOR F11:=0 TO 2 DO                       // Stop, 1 oder 2
     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; // kein HALT vorhanden
        IF (ZU[0]=1AND BESETZT THEN
         BEGIN
          FOR BAND10:=0 TO 1 DO              // Bandinhalt
           FOR BAND11:=0 TO 1 DO             // 0 - 'Blank' schreiben (löschen)
            FOR BAND20:=0 TO 1 DO            // 1 - 'I' schreiben
             FOR BAND21:=0 TO 1 DO
              IF BAND10+BAND11+BAND20+BAND21>0 THEN // mindestens ein Schreibbefehl
               FOR SCHIEB10:=0 TO 1 DO       // Verschiebungen
                FOR SCHIEB11:=0 TO 1 DO      // 0 - links, 1 - rechts
                 FOR SCHIEB20:=0 TO 1 DO
                  FOR SCHIEB21:=0 TO 1 DO
                   IF SCHIEB10+SCHIEB11+SCHIEB20+SCHIEB21>0 THEN
                   // mindestens ein Schiebefehl nach rechts

   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=0OR (PO>MAX) OR (PO<1OR (ZUG=GRENZE);
    // Programm hält regulär v Bandende erreicht v Band blockiert v Todschleife
    IF F=0 THEN // regulärer Halt
     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 :wink:
Viel Spaß beim Abholzen
Fiete
Einloggen, um Attachments anzusehen!
_________________
Fietes Gesetz: use your brain (THINK)