How to make a computer Turing complete
The 8-bit computer isn’t done! In fact it’s not even a computer yet...
Comments (7)
I really enjoy your videos. I understand your point about the need for a conditional branch instruction. But, without taking anything away from the point you were making in the video, I thought you might like to know that your computer CAN multiply two numbers together, even WITHOUT a conditional branch instruction. Here is the code: 0: LDI 0 1: STA 15 2: LDI 1 3: STA 14 4: LDA 7 5: SUB 14 6: STA 7 7: <x> 8: LDA 15 9: ADD 13 10: STA 15 11: OUT 12: JMP 4 13: <y> The numbers to be multiplied (X and Y) are initially stored in memory locations 7 and 13. The product is stored in memory location 15 and is output to the display. X and Y have to be less than 16. This restriction serves two purposes. First, it guarantees that the product will fit in a single byte, so that we don't have to worry about manipulating 16 bit values. Second, it allows memory location X to serve as a conditional statement. This it the key to the program. The program calculates the product through repeated addition of Y. Every time through the loop, the value of X is decremented by 1. If X is between 0 and 15, then memory location 7, if interpreted as a assembly language command, is a NOP. But when X is decremented to -1, it becomes a HLT instruction. This allows the program to run through the main loop exactly X times before halting. (Technically, Y can be any one-byte number. But if it is larger than 16, then the program will compute X*Y mod 256, i.e. just the low order byte of the product.) Thanks again for making these videos. Best, Matthew
Upon further reflection, I realized that X can be larger than I originally thought. For example, if X=16, then memory location 7 will be interpreted as a "LDA 0" command. Performing this LDA command doesn't do anything useful. But since the next command loads a new value into the accumulator anyway, the LDA doesn't do any harm. Likewise, the program will still work if memory location 7 contains an ADD or SUB command. The program may fail if memory location 7 contains a STA command, since it will overwrite part of the program. In short, the program will work for values of X up to 63 (or 67 if you don't mind overwriting the first four bytes of the program, which are only used for initialization anyway). Of course, we're still limited by the requirement that the product fit into a single byte.
Thoroughly enjoyable, Ben. Lookin' forward to your next computationally introspective moment.
looking forward to the next video now.
Thanks!
I have been waiting for it for so long - it is worth it. Watched it and couldn't wait for next video!
Great thoughts, can't wait for the next installment. Thanks for the hard work.