[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]