API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 14th, 2020
312
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.69 KB | None | 0 0
raw download clone embed print report
  1. Simple Functions with the 5-Instruction Set Paper Computer
  2.  
  3. The 5-Instruction Set Computer is basically a Turing-complete
  4. programming langauge that has only 5 instructions:
  5.  
  6. +--+-------+
  7. |1.| isz |
  8. +--+-------+
  9. |2.| jmp |
  10. +--+-------+
  11. |3.| inc |
  12. +--+-------+
  13. |4.| dec |
  14. +--+-------+
  15. |5.| stp |
  16. +--+-------+
  17.  
  18. With just these three instructions, it is possible to emulate any algorithm this universe has to offer. Its up to you to be creative and have an unlimited
  19. paper tape supply!
  20.  
  21. Before we go into what these instructions mean, we need to know what a PROGRAM COUNTER is.
  22.  
  23. Simply put, the PROGRAM COUNTER is the line of the program you are on. Because (most) programs start lists at 0, the program counter starts out at 0.
  24.  
  25. 0 some_instruction <- If you are HERE, the program counter is 0
  26. 1 some_instruction <- If you are HERE, the program counter is 1
  27. 2 some_instruction <- If you are HERE, the program counter is 2
  28. 3 some_instruction <- If you are HERE, the program counter is 3
  29. ...
  30.  
  31. You execute your program by increasing your program counter by +1 every instruction unless otherwise specified (You execute line by line and follow
  32. each instruction as it presented).
  33.  
  34.  
  35. Now we can see what these instructions do!
  36. These instructions are extremely simple. Here they are broken down:
  37.  
  38. 1. ISZ
  39. (IS Zero) ISZ [R]
  40.  
  41. This function checks to see if the specified [R]egister is Zero.
  42. If it is: Add +2 to the program counter (Skip 2 lines)
  43. If it isn't: Add +1 to the program counter (Skip 1 line)
  44.  
  45.  
  46. 2. JMP
  47. (JuMP) JMP [L]
  48.  
  49. This function jumps the program to the specified [L]ine.
  50.  
  51.  
  52. 3. INC
  53. (INCrement) INC [R]
  54.  
  55. This function increments (adds +1) to the specified [R]egister
  56.  
  57. 4. DEC
  58. (DECrement) DEC [R]
  59.  
  60. This function decrements (subtracts -1) from the specified [R]egister
  61.  
  62. 5. STP
  63. (SToP) STP
  64.  
  65. This function terminates the program.
  66.  
  67.  
  68.  
  69. Now that we know what the instructions do, let's make a paper computer!
  70.  
  71.  
  72. If you have a whiteboard or chalkboard, this will be much easier.
  73.  
  74. Draw something that looks like this:
  75.  
  76.  
  77. +---------------+ +---------------+
  78. | 0| | |A| |
  79. +---------------+ +---------------+
  80. | 1| | |B| |
  81. +---------------+---+---------------+
  82. | 2| | |C| |
  83. +---------------+---+---------------+
  84. | 3| | |D| |
  85. +---------------+---+---------------+
  86. | 4| | |E| |
  87. +---------------+---+---------------+
  88. | 5| | |F| |
  89. +---------------+---+---------------+
  90. | 6| | |G| |
  91. +---------------+---+---------------+
  92. | 7| | |H| |
  93. +---------------+---+---------------+
  94. | 8| | |I| |
  95. +---------------+---+---------------+
  96. | 9| | |J| |
  97. +---------------+---+---------------+
  98. |10| | |K| |
  99. +---------------+---+---------------+
  100.  
  101.  
  102. The LEFT column is your PROGRAM. These are the spaces that you will write and execute your program.
  103.  
  104. The RIGHT colum are your REGISTERS. These are the blocks of data that you will manipulate with your program.
  105. By default, they are blank (zero). You can use tally marks, coins, match sticks, anything, to represent the number.
  106.  
  107.  
  108. Say I make an adding program, and I want to add Register A to Register B and have the result in Register C.
  109. I will first write the program, and then put in a number in Register A (say, 5) and a number in Register C (say, 2).
  110.  
  111. After I run the program, Register C will have my answer!
  112.  
  113. Ex:
  114.  
  115. +---------------+ +---------------+ +---------------+ +---------------+
  116. | 0| isz A | |A| 5 | | 0| isz A | |A| 0 |
  117. +---------------+ +---------------+ +---------------+ +---------------+
  118. | 1| jmp 3 | |B| 5 | | 1| jmp 3 | |B| 0 |
  119. +---------------+---+---------------+ +---------------+ +---------------+
  120. | 2| jmp 6 | |C| | | 2| jmp 6 | |C| 10 |
  121. +---------------+---+---------------+ +---------------+ +---------------+
  122. | 3| dec A | |D| | | 3| dec A | |D| |
  123. +---------------+---+---------------+ +---------------+ +---------------+
  124. | 4| inc C | |E| | | 4| inc C | |E| |
  125. +---------------+---+---------------+ +---------------+ +---------------+
  126. | 5| jmp 0 | |F| | | 5| jmp 0 | |F| |
  127. +---------------+---+---------------+ +---------------+ +---------------+
  128. | 6| isz B | |G| | --> | 6| isz B | |G| |
  129. +---------------+---+---------------+ +---------------+ +---------------+
  130. | 7| jmp 9 | |H| | | 7| jmp 9 | |H| |
  131. +---------------+---+---------------+ +---------------+ +---------------+
  132. | 8| stp | |I| | | 8| stp | |I| |
  133. +---------------+---+---------------+ +---------------+ +---------------+
  134. | 9| dec B | |J| | | 9| dec B | |J| |
  135. +---------------+---+---------------+ +---------------+ +---------------+
  136. |10| inc C | |K| | |10| inc C | |K| |
  137. +---------------+---+---------------+ +---------------+ +---------------+
  138. |11| jmp 6 | |L| | |11| jmp 6 | |L| |
  139. +---------------+---+---------------+ +---------------+ +---------------+
  140.  
  141.  
  142.  
  143. Here's some sample programs to help get you started.
  144.  
  145. Samples:
  146.  
  147. +------------------------+
  148. |Hello World (1/0 Toggle)|
  149. +------------------------+
  150. Infinitely toggles Register A from 0 to 1 and back again.
  151.  
  152. 0 inc A
  153. 1 dec A
  154. 2 jmp 0
  155.  
  156.  
  157. +----------+
  158. |Simple Add|
  159. +----------+
  160. Adds Register B to Register A.
  161. Solution is in Register A
  162.  
  163. 0 isz B
  164. 1 jmp 3
  165. 2 stp
  166. 3 dec B
  167. 4 inc A
  168. 5 jmp 0
  169.  
  170.  
  171. +---------------+
  172. |Simple Subtract|
  173. +---------------+
  174.  
  175. Subtracts Register B from Register A. Stops if either Register A
  176. or Register B reach 0.
  177.  
  178. 0 isz A
  179. 1 jmp 3
  180. 2 stp
  181. 3 isz B
  182. 4 jmp 6
  183. 5 stp
  184. 6 dec B
  185. 7 dec A
  186. 8 jmp 0
  187.  
  188.  
  189. +-----------------+
  190. |Boolean Functions|
  191. +-----------------+
  192. Register A: Input A
  193. Register B: Input B
  194. Register X: Output
  195. You can change the register names as you need
  196.  
  197. AND OR XOR NAND NOR XNOR NOT
  198.  
  199. 0 isz A isz A isz A 0 isz A isz A isz A isz A 0
  200. 1 jmp 3 jmp 5 jmp 7 1 jmp 4 stp jmp 5 stp 1
  201. 2 stp isz B isz B 2 inc X isz B isz B inc X 2
  202. 3 isz B jmp 5 jmp 5 3 stp stp stp stp 3
  203. 4 jmp 6 stp stp 4 isz B inc X jmp 8 4
  204. 5 stp inc X inc X 5 stp stp isz B 5
  205. 6 inc X stp stp 6 jmp 2 jmp 8 6
  206. 7 stp isz B 7 stp 7
  207. 8 stp 8 inc X 8
  208. 9 jmp 5 9 stp 9
  209.  
  210. IMPLY NIMPLY
  211.  
  212. 0 isz A isz A
  213. 1 jmp 4 jmp 3
  214. 2 inc X stp
  215. 3 stp isz B
  216. 4 isz B stp
  217. 5 jmp 2 inc X
  218. 6 stp stp
  219.  
  220. In order to chain these gates, be sure to change the internal STP's to JMP to the
  221. last line of that function to allow the program to continue.
  222.  
  223.  
  224. +---------------+
  225. |Signed Subtract|
  226. +---------------+
  227.  
  228. Subtracts Register B from Register A. Signed. Negative flag is in X.
  229. May be able to optimize this.
  230.  
  231. 0 isz A
  232. 1 jmp 5
  233. 2 isz B
  234. 3 jmp 11
  235. 4 stp
  236. 5 isz B
  237. 6 jmp 8
  238. 7 stp
  239. 8 dec B
  240. 9 dec A
  241. 10 jmp 0
  242. 11 inc X
  243. 12 dec B
  244. 13 inc A
  245. 14 isz B
  246. 15 jmp 12
  247. 16 stp
  248.  
  249.  
  250. +-----------------+
  251. |Unsigned Multiply|
  252. +-----------------+
  253.  
  254. Multiplies Register A by Register B. Solution is in Register C.
  255. Unsigned (wiill ignore negative flag).
  256.  
  257. One-way multipication: Two-way multipication:
  258.  
  259. 0 isz B 0 isz B
  260. 1 jmp 3 1 jmp 3
  261. 2 stp 2 stp
  262. 3 dec B 3 dec B
  263. 4 isz A 4 isz A
  264. 5 jmp 7 5 jmp 7
  265. 6 jmp 11 6 jmp 11
  266. 7 dec A 7 dec A
  267. 8 inc C 8 inc C
  268. 9 inc D 9 inc D
  269. 10 jmp 4 10 jmp 4
  270. 11 isz B 11 isz B
  271. 12 jmp 14 12 jmp 14
  272. 13 stp 13 stp
  273. 14 isz D 14 isz D
  274. 15 jmp 17 15 jmp 17
  275. 16 jmp 0 16 jmp 0
  276. 17 dec D 17 dec B
  277. 18 inc A 18 inc C
  278. 19 jmp 14 19 dec D
  279. 20 inc A
  280. 21 jmp 14
  281.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!