1000 REM TM - simulates a Turing Machine
1010 REM
1020 REM     Written by Michael Grobe...7/84.
1030 REM
1040 REM TM prompts for a file containing a machine definition including:
1050 REM
1060 REM     - a string containing the tape alphabet,
1070 REM     - largest machine state id number,
1080 REM     - number of the initial state,
1090 REM     - number of the initial head position, and
1100 REM     - for each transition:
1110 REM         - the originating state number,
1120 REM         - an input symbol (in tape alphabet),
1130 REM         - an output symbol (in tape alphabet),
1140 REM         - a direction (L, R, or N), and
1150 REM         - the destination state.
1160 REM
1170 REM Separate entries on the same line with commas, and use
1180 REM "." for blanks to avoid certain input problems.
1190 REM The tape is initialized with "."
1200 REM
1210 REM      TM must also be given the initial tape contents.  It will
1220 REM ask whether you wish to supply the contents from the keyboard
1230 REM or from a file.  If from the keyboard, TM will prompt for a
1240 REM single string (<256 characters).  If from a file, TM will
1250 REM prompt for a file name, from which it will read up to 1920
1260 REM characters on any number of separate lines.
1270 REM
1280 REM      TM operates in 3 modes:  step, slow, or fast.  Slow and
1290 REM fast modes change state automatically.  Step waits for a RETURN
1300 REM typed on the keyboard, after each state change.  F1, F2, and F3
1310 REM can be used to change mode during execution.  They put TM
1320 REM into step, slow, or fast mode, respectively.
1330 REM
1340 FALSE=0 : TRUE = NOT FALSE
1350 OPTION BASE 1
1360 TAPELENG = 1920
1370 DIM TAPE$(TAPELENG)
1380 KEY OFF : LOCATE 25,1 : PRINT SPACE$(80) : CLS
1390 ON KEY(1) GOSUB 3070   ' Process F1 - enter step mode.
1400 KEY(1) ON
1410 ON KEY(2) GOSUB 3100   ' Process F2 - enter slow mode.
1420 KEY(2) ON
1430 ON KEY(3) GOSUB 3130   ' Process F3 - enter fast mode.
1440 KEY(3) ON
1450 REM
1460 REM  Read machine file.
1470 REM
1480 INPUT "Enter file containing machine definition: ",FILE$
1490 OPEN "i",#1,FILE$
1500 LINE INPUT #1, ALPHABET$
1510 NUMTAPESYMBOLS = LEN(ALPHABET$)
1520 DIM TAPEALPHABET$(NUMTAPESYMBOLS)
1530 FOR I = 1 TO NUMTAPESYMBOLS
1540   TAPEALPHABET$(I) = MID$(ALPHABET$,I,1)
1550 NEXT I
1560 INPUT #1,MAXSTATEID
1570 DIM DIR$(NUMTAPESYMBOLS,MAXSTATEID), NEWSTATE(NUMTAPESYMBOLS,MAXSTATEID),

         WRITESYMBOL$(NUMTAPESYMBOLS,MAXSTATEID), STATEDEFINED(MAXSTATEID)
1580 REM
1590 INPUT #1, INITIALSTATE
1600 INPUT #1, INITIALHEADPOS
1610 REM
1620 REM  Read transitions.
1630 REM
1640 FOR I = 1 TO MAXSTATEID
1650   STATEDEFINED(I) = FALSE
1660 NEXT I
1670 WHILE NOT EOF(1)
1680   INPUT #1, ORIG, INSYMBOL$, OUTSYMBOL$, ADIR$, DEST
1690   IF ORIG<1 OR ORIG>MAXSTATEID THEN PRINT "illegal origin: ";ORIG : END
1700   IF DEST<1 OR DEST>MAXSTATEID THEN PRINT "illegal destination: ";DEST:END
1710   IF ADIR$<>"R" AND ADIR$<>"L" AND ADIR$<>"N" THEN PRINT

              "illegal direction: ";ADIR  : END
1720   ISYMBOL = 0
1730   FOR I = 1 TO NUMTAPESYMBOLS
1740     IF TAPEALPHABET$(I)=INSYMBOL$ THEN ISYMBOL = I
1750   NEXT I
1760   IF ISYMBOL=0 THEN PRINT "illegal input symbol: ";INSYMBOL$ : END
1770   TSYMBOL = 0
1780   FOR I = 1 TO NUMTAPESYMBOLS
1790     IF TAPEALPHABET$(I)=OUTSYMBOL$ THEN TSYMBOL = I
1800   NEXT I
1810   IF TSYMBOL=0 THEN PRINT "illegal output symbol: "; OUTSYMBOL$ : END
1820   REM
1830   REM
1840   IF WRITESYMBOL$(ISYMBOL,ORIG)="" THEN 

           WRITESYMBOL$(ISYMBOL,ORIG) = OUTSYMBOL$

        ELSE PRINT "duplicate transition for state: ";ORIG : END
1850   IF DIR$(ISYMBOL,ORIG)="" THEN

           DIR$(ISYMBOL,ORIG) = ADIR$

       ELSE PRINT "duplicate transition for state: ";ORIG : END
1860   IF NEWSTATE(ISYMBOL,ORIG)=0 THEN

           NEWSTATE(ISYMBOL,ORIG) = DEST

       ELSE PRINT "duplicate transition for state: ";ORIG : END
1870   STATEDEFINED(ORIG) = TRUE
1880   STATEDEFINED(DEST) = TRUE
1890 WEND
1900 CLOSE #1
1910 REM
1920 REM  Display the transition matrix on screen and printer if desired.
1930 REM
1940 INPUT "Print transition matrix on printer (y/N)";ANS$
1950 IF ANS$="y" OR ANS$="Y" THEN HARDCOPY = TRUE
1960 PRINT : IF HARDCOPY THEN PRINT : PRINT : PRINT
1970 PRINT "   TRANSITION MATRIX"
1980 IF HARDCOPY THEN LPRINT "   TRANSITION MATRIX"
1990 PRINT : PRINT "  "; : IF HARDCOPY THEN LPRINT : LPRINT "  ";
2000 FOR I = 1 TO NUMTAPESYMBOLS
2010   PRINT TAB(I*7);" ";TAPEALPHABET$(I);
2020   IF HARDCOPY THEN LPRINT TAB(I*7);" ";TAPEALPHABET$(I);
2030 NEXT I
2040 PRINT : PRINT "---"; : IF HARDCOPY THEN LPRINT : LPRINT "---";
2050 FOR I = 1 TO NUMTAPESYMBOLS
2060   PRINT TAB(I*7);"-----";
2070   IF HARDCOPY THEN LPRINT TAB(I*7);"-----";
2080 NEXT I
2090 PRINT : IF HARDCOPY THEN LPRINT
2100 FOR I = 1 TO MAXSTATEID
2110   IF NOT STATEDEFINED(I) THEN GOTO 2200
2120   PRINT I; : IF HARDCOPY THEN LPRINT I;
2130   FOR J = 1 TO NUMTAPESYMBOLS
2140     PRINT TAB(J*7);WRITESYMBOL$(J,I); DIR$(J,I);
2150     IF HARDCOPY THEN LPRINT TAB(J*7);WRITESYMBOL$(J,I); DIR$(J,I);
2160     IF NEWSTATE(J,I)<>0 THEN PRINT NEWSTATE(J,I);
2170     IF HARDCOPY THEN IF NEWSTATE(J,I)<>0 THEN LPRINT NEWSTATE(J,I);
2180   NEXT J
2190   PRINT : IF HARDCOPY THEN LPRINT
2200 NEXT I
2210 PRINT
2220 MORE = TRUE
2230 WHILE MORE       ' loop to simulate TM on each input tape.
2240 STATE = INITIALSTATE
2250 HEADPOS = INITIALHEADPOS
2260 REM
2270 REM  Initialize tape.
2280 REM
2290 FOR I = 1 TO TAPELENG
2300   TAPE$(I) = "."
2310 NEXT I
2320 REM
2330 REM  Read file or keyboard for initial tape contents.
2340 REM
2350 INPUT "Enter initial tape contents from keyboard or file (K/f)";ANS$
2360 IF ANS$="f" OR ANS$="F" THEN GOTO 2440
2370 INPUT "Enter initial tape contents (1 string): ",ALINE$
2380 TAPEPOS = 0
2390 FOR I = 1 TO LEN(ALINE$)
2400   TAPEPOS = TAPEPOS + 1
2410   TAPE$(TAPEPOS) = MID$(ALINE$,I,1)
2420 NEXT I
2430 GOTO 2580
2440 INPUT "file containing initial tape";FILE$
2450 OPEN "i",#1,FILE$
2460 TAPEPOS = 0
2470 WHILE NOT EOF(1)
2480   LINE INPUT #1, ALINE$
2490   LENGTH = LEN(ALINE$)
2500   FOR I = 1 TO LENGTH
2510     TAPEPOS = TAPEPOS + 1
2520     IF TAPEPOS>TAPELENG THEN PRINT "input tape too long." : END
2530     TAPE$(TAPEPOS) = MID$(ALINE$,I,1)
2540   NEXT I
2550 WEND
2560 CLOSE #1
2570 REM
2580 INPUT "Enter execution speed (step, slow, or FAST)";SPEED$
2590 REM
2600 REM  Print tape on screen.
2610 REM
2620 CLS
2630 LOCATE 1,1
2640 FOR I = 1 TO TAPEPOS
2650   PRINT TAPE$(I);
2660 NEXT I
2670 REM
2680 REM  Print char under head in reverse video.
2690 REM
2700 COLOR 0,7
2710 LOCATE ((HEADPOS-1)\80)+1,((HEADPOS-1) MOD 80)+1 : PRINT TAPE$(HEADPOS);
2720 COLOR 7,0
2730 REM
2740 REM  Begin simulation loop.
2750 REM
2760 HALT = FALSE
2770 WHILE NOT HALT
2780   LOCATE 25,1
2790   PRINT "state: ";STATE;TAB(15);"symbol read: ";TAPE$(HEADPOS);
2800   IF SPEED$="step" THEN LOCATE 25,55 : PRINT "Press return when ready"; :

            WHILE INKEY$<>CHR$(13) : WEND : LOCATE 25,55 : PRINT SPACE$(21);

       ELSE IF SPEED$="slow" THEN FOR I = 1 TO 500 : NEXT I
2810   TSYMBOL = 0
2820   FOR I = 1 TO NUMTAPESYMBOLS
2830     IF TAPE$(HEADPOS) = TAPEALPHABET$(I) THEN TSYMBOL = I
2840   NEXT I
2850   IF TSYMBOL = 0 THEN LOCATE 25,1 : PRINT "illegal tape symbol"; : END
2860   IF WRITESYMBOL$(TSYMBOL,STATE)="" THEN HALT = TRUE : GOTO 2980
2870 REM
2880   TAPE$(HEADPOS) = WRITESYMBOL$(TSYMBOL,STATE)
2890   OLDPOS = HEADPOS
2900   MOVE$ = DIR$(TSYMBOL,STATE)
2910   IF MOVE$="L" THEN IF HEADPOS > 1 THEN HEADPOS = HEADPOS - 1

       ELSE LOCATE 25,1 : PRINT "can't move head past left end"; : END
2920   IF MOVE$="R" THEN IF HEADPOS < TAPELENG THEN HEADPOS = HEADPOS + 1

       ELSE LOCATE 25,1 : PRINT "can't move head past right end"; : END
2930   IF OLDPOS<>HEADPOS THEN LOCATE ((OLDPOS-1)\80)+1,((OLDPOS-1) MOD 80)+1 :

            PRINT TAPE$(OLDPOS);  ' reprint old head char without reverse video
2940   COLOR 0,7      ' print char under head in reverse video
2950   LOCATE ((HEADPOS-1)\80)+1,((HEADPOS-1) MOD 80)+1 : PRINT TAPE$(HEADPOS);
2960   COLOR 7,0
2970   STATE = NEWSTATE(TSYMBOL,STATE)    ' set new state
2980 WEND
2990 LOCATE 25,1
3000 PRINT "Halt at state ";STATE; "....... Press return when done.";
3010 WHILE INKEY$<>CHR$(13) : WEND
3020 LOCATE 25,1 : PRINT SPACE$(80) : CLS
3030 INPUT "Run same machine again with new tape (y/N)";ANS$
3040 IF ANS$<>"Y" AND ANS$<> "y" THEN MORE = FALSE
3050 WEND
3060 END
3070 ' Subroutine to process F1 as "step wise execution"
3080 SPEED$="step"
3090 RETURN
3100 ' Subroutine to process F2 as "slow automatic execution"
3110 SPEED$="slow"
3120 RETURN
3130 ' Subroutine to process F3 as "fast automatic execution"
3140 SPEED$="fast"
3150 RETURN
10 SPEED$="slow"
3120 RETURN
3130 ' Subrout