Home
Creators
Search Recent Random
Posts
Search DMs Popular Hash Lookup Tags Random
Importer
Import FAQ
Register Favorites Keys Review DMs Logout
Community
Telegram ThePornDude
Home Creators Posts Import Register Favorites Logout

How to make a computer Turing complete (Patreon)

Published:
2018-01-05 15:37:56
Imported:
2026-06
haven't archived this post yet. have a subscription? use the importer!

Content

The 8-bit computer isn’t done! In fact it’s not even a computer yet...

Files

Previews only

Making a computer Turing complete

The 8-bit breadboard computer is certainly limited. But is it capable enough to even be a computer? In this video we explore how Turing Machines and the Lambda Calculus defined the whole class of "computable problems." And we talk about the relatively minor change needed to make the 8-bit breadboard computer Turing complete. More 8-bit computer: https://eater.net/8bit Support me on Patreon: https://www.patreon.com/beneater ------------------ Social media: Website: https://www.eater.net Twitter: https://twitter.com/ben_eater Patreon: https://patreon.com/beneater Reddit: https://www.reddit.com/r/beneater

Comments

Rob Bruno

Great thoughts, can't wait for the next installment. Thanks for the hard work.

Anonymous

I have been waiting for it for so long - it is worth it. Watched it and couldn't wait for next video!

Anonymous

looking forward to the next video now.

Don Prefontaine

Thoroughly enjoyable, Ben. Lookin' forward to your next computationally introspective moment.

Anonymous

Thank you Ben, looking forward to the next video. I have been playing with bar graph LED's and resistor networks to replace the individual components and plan on making something semi permanent on solderable breadboards.

Anonymous

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

Anonymous
>>9312758

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.