The Museum of HP Calculators
The Museum of HP Calculators
This program is Copyright © 2001 by Alex Fink.
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.
| Shift | |||||
| Label | |||||
| Key | |||||
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.
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.
| Load side 1 and side 2. | ||||
| Optional: Select print mode. | ||||
| Input number of states, 1 <= n <= 23. | ||||
| Input rule. | ||||
| Go to step 4 until all rules have been input. | ||||
| Input bits on tape, from right to left. | ||||
| Normally: | ||||
| Bit on which the machine starts: | ||||
| Go to step 6 until whole tape has been entered. | ||||
| Start the machine. | ||||
| When (if) the machine halts, go to step 3 for another case. |
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
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
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 1 add to tape
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
Go back to the software library
Go
back to the main exhibit hall