The Museum of HP Calculators

# Turing Machine for the HP-67/97

This program is supplied without representation or warranty of any kind. The author and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

 Turing Machine Shift Tape start Label n Rule Tape Start P? Key A B C D E

A Turing machine is a very simple theoretical type of computer; however, anything which any modern computer can compute, a Turing machine with a sufficient number of states will also be able to.  The machine moves around on an infinite tape containing a string of symbols; in this program the standard binary bits (0 and 1) are used.  The Turing machine's "program" is a sort of table of rules.  Depending on the "state" the machine is in, which in this program is a whole number from 1 to 23, and the tape symbol that it is on, it can write a new symbol in its current position (or write the same symbol in order to not change it), move either left or right on its tape, and switch to another state.  There is a special state, "halt", which stops the operation of the machine.  The machine starts operating in state #1.  A sample rule might look like this:

"If in state #17:
on top of a 0 on the tape:  write a 1 on the tape, move left, and go to state #6;
on top of a 1 on the tape:  write a 0 on the tape, move right, and halt."

The first thing that must be input to the program is the number of states that the machine uses, denoted by n.  Press A to input this value.  The program will then display "1.00"; this is a prompt to enter the rule for state #1.  After entering this rule, press B, and the machine will display "2.00", which is a prompt to enter the rule for state #2.  Continue entering rules and pressing B, until the last rule has been entered and a display of "0.00" appears.  Then start to enter the numbers initially on the tape from right to left; press C after each one of these, or f C if the machine is to start positioned on the symbol just entered.  Finally, press D to start the machine.

A rule must be input to the program in "sswm.sswm" format.  The "ss" is the state number to go to; it can be from 01 to 23, or 00 for halt.  It is important that leading 0s on the state numbers be entered.  The "w" is the symbol to write on the tape, which is either 0 or 1; and the "m" is the direction to move, 0 for left and 1 for right.  If the machine reads a 0 from the tape, it will use the left half of the rule, and if it reads a 1 it will use the right half.  Thus, if inputting the sample rule above, one would type "0610.0001".

The program will display the machine's current state with a number like "2.abcdefghi  xx".  The digits a through i are the part of the tape nearest the machine, and e is the symbol which the tape is actually on.  xx is the state number that the machine is currently in.  All of these input and output formats should become much clearer with the example below.

Optionally, the program allows a printout of the input entered and a record of the machine's operation.  This option is selected by pressing E until "1.00" appears in the display.

## Remarks

No checking is done to determine if rules entered are valid.  If an invalid value for n is entered or an invalid state number is found while running, a flashing display will result which can be cleared by pressing R/S.

By default, the Turing machine's tape is full of 0s.  This program can store up to log2(10^10), or approximately 33, consecutive symbols on its tape; all symbols on either side of this block will appear as 0s.

All data storage registers are used.

## Instructions

 Step Instructions Input Data/Units Keys Output Data/Units 1 Load side 1 and side 2. 2 Optional: Select print mode. E 1.00/0.00 3 Input number of states, 1 <= n <= 23. n A 1 4 Input rule. state k rule B k+1 or 0 if last rule 5 Go to step 4 until all rules have been input. 6 Input bits on tape, from right to left. Normally: bit C Bit on which the machine starts: bit f C 7 Go to step 6 until whole tape has been entered. 8 Start the machine. D 2.tape  state 9 When (if) the machine halts, go to step 3 for another case.

## Examples

Here is a set of rules for a simple 6-state Turing Machine which, when started on the leftmost end of a block of "1"s on a tape that otherwise contains only "0"s, will make a new block of "1"s double the length of the original one, destroying the original in the process.

If in state #1:
on top of a 0 on the tape:  write a 0 on the tape, move right, and halt;
on top of a 1 on the tape:  write a 0 on the tape, move right, and go to state 2.
If in state #2:
on top of a 0 on the tape:  write a 0 on the tape, move right, and go to state 3;
on top of a 1 on the tape:  write a 1 on the tape, move right, and go to state 2.
If in state #3:
on top of a 0 on the tape:  write a 1 on the tape, move right, and go to state 4;
on top of a 1 on the tape:  write a 1 on the tape, move right, and go to state 3.
If in state #4:
on top of a 0 on the tape:  write a 1 on the tape, move left, and go to state 5;
on top of a 1 on the tape:  write a 1 on the tape, move right, and go to state 4.
If in state #5:
on top of a 0 on the tape:  write a 0 on the tape, move left, and go to state 6;
on top of a 1 on the tape:  write a 1 on the tape, move left, and go to state 5.
If in state #6:
on top of a 0 on the tape:  write a 0 on the tape, move right, and go to state 1;
on top of a 1 on the tape:  write a 1 on the tape, move left, and go to state 6.

Input this set of rules to the program and run it on a tape containing "...0000000011100000000...".

Keystrokes                     Outputs
5 A                            1.00         (input state 1 rule)
0001.0201 B                    2.00         (input state 2 rule)
0301.0211 B                    3.00         (input state 3 rule)
0411.0311 B                    4.00         (input state 4 rule)
0510.0411 B                    5.00         (input state 5 rule)
0600.0510 B                    6.00         (input state 6 rule)
0101.0610 B                    0.00         (input tape)
1 C 1 C 1 f C                  2.00
current position
v
D                              2.000011100 01<- state
2.000011000 02
2.000110000 02
2.001100000 02
2.011000000 03
2.110100000 04
2.011011000 05
2.001101100 05
2.000110110 06
2.000011011 06
2.000001101 06
2.000011011 01
2.000010110 02
2.000101100 02
2.001011000 03
2.010110000 03
2.101100000 03
2.011100000 04
2.101111000 05
2.010111100 05
2.001011110 05
2.000101111 05

2.000010111 06
2.000001011 06
2.000010111 01

2.000001111 02
2.000011110 03
2.000111100 03
2.001111000 03
2.011110000 03
2.111100000 03
2.111100000 04

2.111111000 05
2.011111100 05
2.001111110 05
2.000111111 05
2.000011111 05
2.000001111 05
2.000000111 06

2.000001111 01
2.000011111 00<- state
^
current position

## The Program

LINE  KEYS
001   LBL E    Toggle print mode.
002   F1?
003   GTO 0
004   1
005   SF 1
006   RTN
007   LBL 0
008   0
009   CF 1
010   RTN
011   LBL A
012   CLRG     Clear registers.
013   P<>S
014   CLRG
015   INT
016   GSB 5    Check whether number of states is valid.
017   F1?      Print number of states.
018   PRTX
019   F1?
020   SPC
021   STO E    Initialize necessary variables.
022   1
023   STO I
024   CF 0
025   RTN
026   LBL B    Store rule for state.
027   F1?
028   GSB 6
029   STO (i)
030   ISZ I    Display number of next state, or 0 if finished.
031   RCL E
032   RCL I
033   X>Y?
034   0
035   RTN
036   LBL 6    Print rule.
037   RCL I
038   PRTX
039   R down
040   PRTX
041   SPC
042   RTN
043   LBL C    Determine whether start bit has been entered.
044   F1?
045   PRTX
046   F0?
047   GTO 1
048   ST+ 0    Add next bit to tape if start bit has not been entered.
049   2
050   ST÷ 0
051   RTN
052   LBL c    Enter starting bit.
053   F1?
054   PRTX
055   SF 0
056   1
057   STO E
058   R down
059   LBL 1    Add next bit to tape if start bit has been entered.
060   RCL E
061   x
062   ST+ 0
063   RCL E
064   2
065   x
066   STO E
067   RTN
068   LBL D    Configure machine for running.
069   1
070   STO I
071   DSP 9
072   SCI
073   F1?
074   SPC
075   LBL 3    Prepare display of current position.
076   8
077   STO E
078   0
079   LBL 7    Isolate one bit.
080   RCL 0
081   RCL E
082   x
083   FRC
084   2
085   x
086   INT
087   +        Append bit to end of display.
088   1
089   0
090   ÷
091   RCL E
092   2
093   ÷
094   STO E
095   6        Repeat for each bit within 4 of current position.
096   4
097   1/X
098   X=Y?
099   GTO 0
100   R down
101   R down
102   GTO 7
103   LBL 0
104   R down
105   R down
106   2
107   +
108   RCL I    Choose exponent of 10 corresponding to current state.
109   10^X
110   x
111   PSE      Display current position.
112   F1?
113   PRTX
114   RCL I
115   X=0?     End program if in halt state.
116   GTO 8
117   RCL (i)
118   RCL 0    Isolate current bit.
119   INT
120   2
121   ÷
122   FRC
123   X=0?     Select corresponding part of rule.
124   GTO 0
125   R down
126   FRC
127   EEX
128   2
129   x
130   CF 0
131   GTO 4
132   LBL 0
133   R down
134   INT
135   1
136   %
137   SF 0
138   LBL 4    Break rule into components.
139   ENTER
140   FRC
141   1
142   0
143   x
144   ENTER
145   INT
146   F0?      Write new bit to tape.
147   GTO 0
148   1
149   -
150   LBL 0
151   ST+ 0
152   R down
153   FRC
154   X=0?     Move machine on tape.
155   GTO 0
156   4
157   STx 0
158   R down
159   LBL 0
160   2
161   ST÷ 0
162   R down
163   R down
164   INT
165   X!=0?    Check whether next state is valid.
166   GSB 5
167   STO I    Set next state.
168   GTO 3
169   LBL 5    Ensure that X is from 1 to 23.
170   1
171   X>Y?
172   GTO 2
173   CLX
174   2
175   3
176   X<>Y
177   X>Y?
178   GTO 2
179   RTN
180   LBL 2    Flash screen on error.
181   PSE
182   GTO 2
183   LBL 8    Retain display of tape when halted.
184   X<>Y
185   RTN

## Register, Label, and Flag Use

R0    tape
R1-RD used (rules)
RE    used
I     current state
LBL A n
LBL B rule
LBL C tape
LBL D start
LBL E P?
LBL c starting tape
LBL 0 used
LBL 2 error
LBL 3 main loop
LBL 4 interpret rule
LBL 5 range check
LBL 6 print
LBL 7 display
LBL 8 end
F0    used
F1    print