291 lines
13 KiB
Plaintext
291 lines
13 KiB
Plaintext
[Attempt at Turing machine for Rosetta Code.]
|
|
[EDSAC program, Initial Orders 2.]
|
|
|
|
[Library subroutine M3 prints header and is then overwritten.]
|
|
PFGKIFAFRDLFUFOFE@A6FG@E8FEZPF
|
|
*!!NR!STEPS@&#..PZ [..PZ marks end of header]
|
|
|
|
T48K [& (delta) parameter: Turing machine tape.]
|
|
P8F [Overwrites most of initial orders.]
|
|
|
|
T50K [X parameter: once-only code.]
|
|
P100F [Gets overwritten by the Turing machine tape.]
|
|
|
|
[Put the following as high in memory as possible,
|
|
to make room for the Turing machine tape.]
|
|
T52K [A parameter: rules and initial pattern. Also marks end]
|
|
P781F [of Turing tape, so must go immediately after tape area.]
|
|
|
|
T55K [V parameter: program-wide variables.]
|
|
P810F [Even address, 9 locations]
|
|
|
|
T46K [N parameter: constants.]
|
|
P820F [Even address]
|
|
|
|
T47K [M parameter: main routine.]
|
|
P859F
|
|
|
|
T51K [G parameter: library subroutine P7]
|
|
P988F [Even address, 35 locations.]
|
|
|
|
[============================= A parameter ===============================]
|
|
E25K TA GK
|
|
[0] [End of Turing tape area]
|
|
[Comment-in the desired task, or add another (2 symbols only).]
|
|
[Counts are stored in the address field.]
|
|
[Each rule is defined by an EDSAC pseudo-order, as follows:
|
|
Function letter: L = left, R = right, S = stay
|
|
Address field = new state number
|
|
Code letter: F if new symbol = 0, D if new symbol = 1.
|
|
No rule is needed for the halt state.]
|
|
[0]
|
|
[Simple incrementer: states are q0 = 0, qf = halt = 1
|
|
P1F [1 state, excluding the halt state
|
|
S1D RD [2 rules for each state (symbols 0 and 1)
|
|
P1F [1 word in tape area to be initialized
|
|
PF P3D [location 0 relative to tape, init to 7]
|
|
[3-state busy beaver: states are a = 0, b = 1, c = 2, halt = 3]
|
|
P3F [3 states, excluding the halt state]
|
|
R1D L2D [2 rules for each state (symbols 0 and 1)]
|
|
L0D R1D
|
|
L1D S3D
|
|
PF [0 words to be initialized (start with empty tape)]
|
|
[5-state busy beaver: states are A = 0, ..., E = 4, halt = 5
|
|
P5F 5 states, excluding the halt state
|
|
R1D L2D 2 rules for each state (symbols 0 and 1)
|
|
R2D R1D
|
|
R3D L4F
|
|
L0D L3D
|
|
S5D L0F
|
|
PF 0 words to be initialized (start with empty tape)]
|
|
|
|
[============================= X parameter ===============================]
|
|
E25K TX GK
|
|
[The following once-only code is loaded into the Turing machine tape area.]
|
|
[It runs at start-up, then gets overwritten when the tape is cleared.]
|
|
[Enter with acc = 0.]
|
|
[0] T2V [initial state assumed to be state 0]
|
|
T3V [tape head starts at position 0 on Turing tape]
|
|
T#V [reset count of steps]
|
|
T4V [initialize maximum position]
|
|
T5V [initialize minimum position]
|
|
[Calculate number of available tape positions; store in address field]
|
|
A22N [T order for exclusive end of tape]
|
|
S21N [T order for start of tape]
|
|
L4F [times 16, since each location holds 16 positions]
|
|
T25N [store for later use]
|
|
[Set up the loop in the main program that writes the initial pattern.
|
|
The main program has a list of position-value pairs.
|
|
This follows the list of rules, 2 rules per Turing machine state.]
|
|
[9] AA [number of states]
|
|
LD [times 2, because 2 rules per state]
|
|
A2F [plus 1 for the count of states]
|
|
A9@ [make A order to load number of position-value pairs]
|
|
T14@ [plant order]
|
|
[14] AM [load number of pairs (in address field)]
|
|
LD [times 2 for length of table]
|
|
TF [temp store in 0F]
|
|
A14@ [load order that was planted above]
|
|
A2F [make order to load first position]
|
|
U13M [plant in main routine]
|
|
AF [make A order for exclusive end]
|
|
T28M [plant in main routine]
|
|
[Set up order to load rules]
|
|
A26@
|
|
A2F
|
|
T18N
|
|
[Here with acc = 0. Jump to main routine.]
|
|
EM
|
|
[26] AA
|
|
|
|
[============================= V parameter ===============================]
|
|
E25K TV GK
|
|
[0] PFPF [number of steps (35-bit, must be at even address)]
|
|
[2] PF [current state of Turing machine]
|
|
[3] PF [current tape position, stored in address field]
|
|
[4] PF [maximum position on the tape so far]
|
|
[5] PF [minimum position on the tape so far]
|
|
[6] PF [rule for current state and symbol]
|
|
[7] PF [working group of 16 cells (1 EDSAC location)]
|
|
[8] PF [mask to select bit for current cell]
|
|
|
|
[============================= N parameter ===============================]
|
|
E25K TN GK
|
|
[17-bit masks: 11111111111111110, 11111111111111101, ..., 10111111111111111]
|
|
[0] V2047F V2046D V2045D V2043D V2039D V2031D V2015D V1983D
|
|
V1919D V1791D V1535D V1023D C2047D B2047D G2047D M2047D
|
|
[16] OF [add to A order to make T order with same address]
|
|
[17] AN [A order to load first mask in table]
|
|
[18] AF [A order to load first rule]
|
|
[19] A& [A order for start of tape]
|
|
[20] AA [A order for end of tape]
|
|
[21] T& [T order for start of tape]
|
|
[22] TA [T order for exclusive end of tape]
|
|
[23] P2047F [mask to pick out state from a Turing machine rule]
|
|
[24] P15F [mask to extract bit number from position]
|
|
[25] PF [number of tape positions available (calculated)]
|
|
[26] @F [carriage return]
|
|
[27] &F [line feed]
|
|
[28] K4096F [null]
|
|
[29] K2048F [set letters on teleprinter]
|
|
|
|
[============================= M parameter ===============================]
|
|
E25K TM GK
|
|
[Once-only code jumps to here with acc = 0]
|
|
[Clear the tape; this overwrites the once-only code]
|
|
[0] A21N [load T order for start of tape]
|
|
E3@ [always jump (since T > 0)]
|
|
[2] A22N [loop here after testing for end]
|
|
[3] T4@ [plant order to clear 1 location]
|
|
[4] TF [execute order]
|
|
A4@ [load order just executed]
|
|
A2F [inc address]
|
|
S22N [test for end]
|
|
G2@ [if not end, loop back]
|
|
[Here with acc = 0]
|
|
[Set up the starting pattern, i.e write 1's at zero or more positions on the tape.]
|
|
[To save space, the orders marked (*) are set up by the once-only code.]
|
|
[9] A13@ [load A order for next relative addess]
|
|
S28@ [compare with A order for exclusive end]
|
|
E29@ [if all done, jump out with acc = 0]
|
|
TF [clear acc]
|
|
[13] AF [(*) load relative address from table]
|
|
G17@ [jump if < 0]
|
|
A21N [make T order, addr counted from low end of tape]
|
|
E18@ [join commoon code (always jumps since T > 0)]
|
|
[17] A22N [make T order, addr counted from high end of tape]
|
|
[18] T23@ [plant T order in code]
|
|
A13@ [make order to load value from table]
|
|
A2F
|
|
T22@ [plant in code]
|
|
[22] AF [load value from table]
|
|
[23] TF [store in tape]
|
|
A22@ [make A order for next address]
|
|
A2F
|
|
T13@ [plant in code]
|
|
E9@ [always loop back]
|
|
[28] AF [(*) A order for exclusive end of list]
|
|
[29]
|
|
[Next step, i.e. set up new symbol, state and tape position.]
|
|
[Acc must be 0 here.]
|
|
[Get tape position and deduce corresponding EDSAC location and bit number.]
|
|
[29] H24N [mask for bit number]
|
|
C3V [acc := bit number]
|
|
UF [save bit number in 0F address field]
|
|
A17N [make order to load from mask table]
|
|
T44@ [plant order in code]
|
|
A3V [position]
|
|
SF [remove bit number part]
|
|
R4F [divide by 16 for relative address]
|
|
[If it's a non-negative address, add it to the start of the tape in EDSAC memory.]
|
|
[If it's a negative address, add it to the end of the tape.]
|
|
G40@ [jump if negative address]
|
|
A19N [make A order to load from tape]
|
|
G41@ [always jump to common code, since A < 0]
|
|
[40] A20N [here if negative address]
|
|
[41] U46@ [store order to load current group of 16 bits]
|
|
A16N [convert to T order at same address]
|
|
T69@ [store T order (a fair way down the code)]
|
|
[44] AF [load mask]
|
|
T8V
|
|
[46] AF [load group]
|
|
T7V
|
|
[Get rule for this state and symbol (where symbol = 0 or 1)]
|
|
H8V
|
|
C7V [acc := bit group with current bit cleared]
|
|
S7V [acc := 0 if bit is 0, -1 if bit is 1]
|
|
E54@
|
|
TF [clear acc]
|
|
A2F [to inc rule address if symbol is 1]
|
|
[54] A2V [add state twice (because each state has 2 rules)]
|
|
A2V
|
|
A18N [manufacture A order to load rule]
|
|
T58@
|
|
[58] AF [load rule]
|
|
T6V [to work space]
|
|
[Write new symbol (0 or 1) to tape. New symbol is in low bit of rule.]
|
|
HN [H register := 111...1110]
|
|
C6V
|
|
S6V [result = 0 if new symbol is 0; -1 if it's 1]
|
|
H8V [H register = mask 1...101...1 for current bit]
|
|
G67@ [jump to set the bit]
|
|
C7V [clear the bit]
|
|
E69@ [always jump (because top bit in tape store is always 0)]
|
|
[Set bit, assuming acc = -1 here (reason why it works is a bit complicated)]
|
|
[67] C7V
|
|
S8V
|
|
[69] TF [manufactured order]
|
|
[Update position of tape head, i.e. inc by 1, dec by 1, or no change.]
|
|
[Move is in top 2 bits of rule, thus]
|
|
[1x = move left, i.e. dec position (function letter can be L)]
|
|
[00 = move right, i.e. inc position (function letter can be R)]
|
|
[01 = stay, i.e. don't change position (function letter can be S)]
|
|
A6V
|
|
G83@ [left if top bit is 1]
|
|
[72] LD [else test next bit]
|
|
G95@ [skip move if next bit is 1]
|
|
[74] TF [here to move right]
|
|
A3V [inc position]
|
|
A2F
|
|
U3V
|
|
[Here we update the maximum position if latest >= maximum.]
|
|
[This is unnecessary if latest = maximum, but code is simpler this way.]
|
|
S4V [test against maximum position]
|
|
G95@ [skip if latest < maximum]
|
|
A4V [restore after test]
|
|
T4V [update maximum]
|
|
E91@ [always jump, to check for overflow]
|
|
[83] TF [here to move left]
|
|
A3V [dec position]
|
|
S2F
|
|
[86] U3V
|
|
S5V [test against current minimum position]
|
|
E95@ [jump if >= minimum]
|
|
A5V [restore acc after test]
|
|
T5V [update minimum]
|
|
[After updating maximum or minimum position, check that
|
|
available memory hasn't been exceeded.]
|
|
[91] A4V [maximum position]
|
|
S5V [subtract minimum position]
|
|
S25N [compare against number available]
|
|
E107@ [jump out if overflow]
|
|
[The next order also serves as a constant]
|
|
[95] TF [clear acc for next part]
|
|
[Increment the number of steps]
|
|
A#V
|
|
YFYF
|
|
T#V
|
|
[Finally set the new state.]
|
|
[100] H23N [mask for state bits in rule]
|
|
C6V [acc := new state]
|
|
SA [is it the last state?]
|
|
E111@ [if yes, halt the Turing machine]
|
|
AA [restore acc after test]
|
|
T2V [update state]
|
|
E29@ [loop back for next step]
|
|
[Overflow, i.e. non-negative tape positions (ascending in EDSAC memory)
|
|
collide with negative tape positions (descending).]
|
|
[107] O29N [set teleprinter to letters]
|
|
O107@ ON [print 'OV' to indicate overflow]
|
|
E116@ [jump to exit]
|
|
[Print number of steps]
|
|
[111] TF A#V [clear accc, load number of steps]
|
|
TD [number of steps to 0D for print subroutine
|
|
[114] A114 @GG [call print subroutine]
|
|
[116] O26N O27N [print CR, LF]
|
|
O28N [print null to flush teleprinter buffer]
|
|
ZF [stop]
|
|
|
|
[============================= G parameter ===============================]
|
|
E25K TG
|
|
[Library subroutine P7. 35 locations, even address. WWG page 18.]
|
|
[Prints non-negative integer, up to 10 digits, right-justified.]
|
|
GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSFL4F
|
|
T4DA1FA27@G11@XFT28#ZPFT27ZP1024FP610D@524D!FO30@SFL8FE22@
|
|
|
|
[========================== X parameter again ===============================]
|
|
E25K TX GK
|
|
EZ [define entry point]
|
|
PF [enter with acc = 0]
|
|
[end]
|