BASIC for 8-bit computer
I tested the program in an emulator of Sharp MZ-800. Writing the simulation itself is not too difficult, but the handling of the input takes a lot of lines of code as I have to split the input strings.
I have modified the input format a bit. Before the transition rules there is one line containing the number of rules that will follow.
The program has built-in limits: the tape is 200 characters long and the maximum number of symbols and states is 20.
Code:
1 REM TURING MACHINE SIMULATOR
2 REM READ TAPE SYMBOLS
3 DIM N(2),H$(2,20)
4 INPUT A$:A$="_"+A$
5 FOR I=1 TO LEN(A$):H$(1,I-1)=MID$(A$,I,1):NEXT
6 N(0)=LEN(A$)-1
8 REM READ STATES
9 INPUT A$
10 K=0:J=1
11 FOR I=1 TO LEN(A$)+1:GOSUB 50:I=J:H$(0,K)=C$:K=K+1:NEXT
12 N(1)=K-1
13 H$(2,0)="<":H$(2,2)=">":N(2)=2
15 REM READ INITIAL AND ACCEPTING STATES
16 INPUT C$:X=0:GOSUB 57:IN=R
17 INPUT C$:GOSUB 57:AC=R
20 REM READ TAPE
21 DIM A(200):INPUT A$
22 FOR I=1 TO LEN(A$):C$=MID$(A$,I,1):X=1:GOSUB 57:A(I+99)=R
23 NEXT
25 DIM NS(N(0),N(1)),NC(N(0),N(1)),NM(N(0),N(1))
26 INPUT S
27 REM READ TRANSITION TABLE
28 FOR I=1 TO S
29 INPUT A$:J=1
30 X=0:GOSUB 50:GOSUB 57:S0=R:X=1:GOSUB 50:GOSUB 57:C0=R:GOSUB 50
31 X=0:GOSUB 50:GOSUB 57:NS(S0,C0)=R
32 X=1:GOSUB 50:GOSUB 57:NC(S0,C0)=R
33 X=2:GOSUB 50:GOSUB 57:NM(S0,C0)=R-1
34 NEXT
36 REM SIMULATE
37 J=100:S=IN
38 A0=A(J):S0=S:A(J)=NC(S0,A0):S=NS(S0,A0):J=J+NM(S0,A0)
39 IF S<>AC GOTO 38
40 REM PRINT OUTPUT
41 FOR I=0 TO 99:IF A(I)=0 THEN NEXT
42 FOR I1=200 TO 101 STEP -1:IF A(I1)=0 THEN NEXT
43 FOR I=I TO I1
44 C$=" ":IF I=100 THEN C$="|" ELSE IF I=J THEN C$="^"
45 O$=O$+H$(1,A(I)):P$=P$+C$
46 NEXT
47 PRINT O$:PRINT P$
48 END
49 REM GET NEXT WORD
50 FOR Z=J TO LEN(A$):C$=MID$(A$,Z,1)
51 IF C$<>" " THEN NEXT
52 C$=MID$(A$,J,Z-J):J=Z+1
53 RETURN
56 REM FIND WORD IN A LIST
57 FOR R=0 TO N(X):IF C$=H$(X,R) THEN RETURN
58 NEXT
59 RETURN
Input:
01
Mov B Bi OK
Mov
OK
01100100
9
Mov 0 = Mov 0 >
Mov 1 = Mov 1 >
Mov _ = B _ <
B 0 = B 0 <
B 1 = Bi 1 <
B _ = OK _ >
Bi 0 = Bi 1 <
Bi 1 = Bi 0 <
Bi _ = OK _ >
Output:
10011100
|