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.
|
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:
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(1010), 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.
|
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. |
|
|
|
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:
If in state #2:
If in state #3:
If in state #4:
If in state #5:
If in 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 031 RCL E finished. 032 RCL I 033 X>Y? 034 0 035 RTN 036 LBL 6 Print rule. 037 RCL I 038 PRTX 039 R↓ 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 049 2 been entered. 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↓ 059 LBL 1 Add next bit to tape if start bit has been 060 RCL E entered. 061 × 062 ST+ 0 063 RCL E 064 2 065 × 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 × 083 FRC 084 2 085 × 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 096 4 position. 097 1/X 098 X=Y? 099 GTO 0 100 R↓ 101 R↓ 102 GTO 7 103 LBL 0 104 R↓ 105 R↓ 106 2 107 + 108 RCL I Choose exponent of 10 corresponding to 109 10X current state. 110 × 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↓ 126 FRC 127 EEX 128 2 129 × 130 CF 0 131 GTO 4 132 LBL 0 133 R↓ 134 INT 135 1 136 % 137 SF 0 138 LBL 4 Break rule into components. 139 ENTER 140 FRC 141 1 142 0 143 × 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↓ 153 FRC 154 X=0? Move machine on tape. 155 GTO 0 156 4 157 STx 0 158 R↓ 159 LBL 0 160 2 161 ST÷ 0 162 R↓ 163 R↓ 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