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.

------------------

Social media:

[lastmiles]

I love the little joke at the end .. the distance between 16 bytes and 16GB from infinity is about the same.

[tagnarth]

Been looking forward to this. This series completely opened my eyes to fundamentals of a CPU and EE. (Software engineer by trade, never really dabbled past building my own PCs). Thank you Ben for making this series

[edwardwray]

Mind blown! I watched the whole 8-bit computer video start to finish, and this video just completely changed my perspective on how I view computers.

[cgerman]

On a related note, the x86 mov instruction is Turing complete (yes, that single instruction).

For anyone who's interested, Chris Domas made a mov-only compiler called "Movfuscator"

He has a presentation on YouTube somewhere

[chaitanyaravuri]

I think I have a program that can multiply two numbers using only the instructions that we have right now (so no conditional jumps). The idea is that we can edit the RAM, which means we can both change the storage AND the actual program itself. This means that the data can actually change how the program behaves, and with this we should be able to make a multiplication program.


This is the program that I came up with:
0: LDA 3
1: ADD 17
2: STA 3
3: JMP 31
4: LDA 3
5: SUB 17
6: STA 3
7: LDA 18
8: ADD 16
9: STA 18
10: LDI 1
11: STA 19
12: LDA 17
13: SUB 19
14: STA 17
15: JMP 0
16: X
17: Y
18: 0
19: 0
.
.
.
28: LDA 18
29: OUT
30: HLT
31: JMP 28


I actually needed 5 address bits, or 32 memory locations to make this work, but I still only used the instructions we have available. Lines 0-6 are essentially what are doing the conditional jump that we need for multiplication. What they do is jump to line 31 if the number stored at address 17 is 0. With this it's relatively easy to do the rest of the program, which just adds the number in position 16 to the number in position 18, and stores the sum back in position 18. At the same time, it subtracts 1 from the number in position 17, and loops back to the beginning of the program where again, it checks if position 17 is 0 and if so, goes to the last line, line 31. Then, on line 31, I just jump back a bit so I can output the answer, which is in position 18.


So, basically, positions 16 and 17 are storing the two numbers we want to multiply, and position 18 is storing the result of that multiplication.


The way the conditional jump works is that I am editing the jump statement right before I reach it. In memory, the actual jump statement will be represented as where ABCD is just the code for the jump statement. Ben used 0110, so I'll also use that. The other digits are because that is the position we are jumping to, 31. Right before the program reaches the jump statement, we add the number in position 17 (which I'll call Y from now on) to the number in position 3. But, the number in position 3 is the jump statement. If Y is anything other than 0, we will be editing this jump statement. The jump statement before was If we add anything to this, we will be changing the first four digits of the statement. As long as we add a number that is less than 5 bits we will only change the 4th bit, which means the new code will be 0111. If we just make this code do nothing, then if we add anything other than 0 to the jump statement, the line will then do nothing. Only if we add 0, which means Y = 0, will we actually jump to line 31, as then, the jump statement won't be edited. So, this works as a conditional jump statement that jumps to the last line if Y = 0 (and Y is less than 5 bits).


I'm pretty sure that this means the computer is Turing complete, even without adding a conditional jump statement, but it's just much harder to reason this out, and it's probably easier to just add a conditional jump.

[Violentinsect]

This playlist is one of the most valuable YouTube materials on computers if not "THE MOST VALUABLE" on the subject. The viewer can clearly feel that you love what you do. great job.
Can't thank you enough for taking the time and effort to present this in the most informative way possible.

[Kiteboardshaper]

JNZ, jump if not zero, is my vote for your conditional jump instruction. Was my number 1 decision maker when I was an 8051 assembly programmer.

[duchyre]

Ben, I don't know how i would thank you. You completely changed my perception of computers(/computing) and your 8-bit computer series got me in electronics and in how does a computer work (the elemental stuff no one looks at nowdays). Stay AWESOME, cheers from Czech Republic!

PS: do you think it is possible to simulate a basic quantum computer with hardware? (just like your 8-bit computer)

[ThatsWhatTheManWants]

“We wouldnt expect a computer to be able to compute the meaning of life”

*Asimov starts sweating nervously*

[gcewing]

At 17:30 I half-expected him to say "Here's an infinitely long tape I ordered from ebay..."

[tonypalmeri]

I've never built my own computer, and probably will never find the time to do so.... But I almost feel like I've had the experience of doing so, just by watching your videos. Your presentation is clear and compelling, and has given me a much better understanding of what's actually going-on "down-deep" in a computer's circuitry... things that I've mostly already understood at an abstract level but always wanted to understand all the way down, in detail, to the physical level. Thank you for making these videos, and I definitely look forward to more.

[christianfieldhouse]

Very smart of you not to build in any speculative execution - there will be no Spectre attacks on the Ben Eater Machine.

[FunLCakeman]

I absolutely love this series. It starts with the chemistry of transistors and ends up organically teaching assembly language and Turing-completeness in a way that's completely organic. Each step logically follows from the last.

[esven]

It is possible to use those instructions to create a multiply command with values below a certain bit length. You can permute the stored instructions to create a conditional jump. It's not necessarily with the limitations of this computers memory but with the same instruction set it is indeed possible. In this case I'll do multiplication with repeated addition.

You start with two arguments somewhere in memory, these are the numbers to be multiplied together.

The first of these arguments we'll call the iterator since it will count down each time we execute the loop. As well designate an address in memory we'll call the product because it will store the product of multiplication.

ADD the second argument and the product together and store the result over the product.

Load the iterator, subtract 1 and store it again then add (0110 <current instruction address +3>) to the result.

Store it to <current instruction address +1>

The next command in the fetch is now equivalent to jump <offset> with the offset being the iterator.

All commands in memory addressable by a number the bit length of the largest argument you accept should be jumps, which will jump the program back to where we loaded from memory and then added the product and the second argument together. The only exception to this is the command immediately after which should jump out of that loop to the commands LDA <product>, OUT, HLT

Our program execution then for lets say the values 4 and 3 should be.

loop1:
iterator = 3
product = 3
JMP offset 4

loop2:
iterator = 2
product = 6
JMP offset 3

loop3:
iterator = 1
product = 9
JMP offset 2

loop4:
iterator = 0
product = 12
JMP offset 1
<break>

Additionally such a command would be possible using ADD as a bitshift.

Adding a value to itself is the same as bitshifting it left once. So by bit shifting one argument by the bit length of the other, adding the two together then using that conditional jump trick you could create a situation where you have a unique jump address for every combination of arguments. Given this I do think the original instruction set is Turing complete given an arbitrarily long instruction bitlength and an arbitrarily large amount of memory in which to compute.

[hyqhyp]

"When we need more RAM, we'll add it" is Nachum Dershowitz's answer to the common critique of everyday computers missing infinite RAM and hence not being as powerful as Turing machines.

[mshine]

I was wondering how you were going to end this series. I thought it might be similar to just saying "tadah! I'm done!'. But no. You lit the metaphorical dynamite and said: "here, hold this, it'll blow your mind"

[dipi]

3:10 about minimal instruction sets: Christopher Domas famously wrote a code obfuscator and even a complete gcc plugin. He showed that Intel’s MOV instruction is Turing complete.
(At 39:13 in that talk Christopher even shows a 3D-floating-point framework driven by MOV instructions exclusively — an incredible feat of concept proving, in my opinion!)

[MauPP]

Ben: Hey, I built a computer
Alan: *bUt CAn iT "If" ????*

[gsittly]

Entscheidungsproblem is pronounced a bit like Entshydeongsproblehm or entshydoungsproblehm with r spelled harder than in english and emphasised on "shy", ou like in "you". 😊 It really means "decision problem". It's german, because Kurt Gödel was the first person writing a paper 1931 about the Entscheidungsproblem which was reformatted by Alan Turing 1936.
Btw as a computer scientist I love your videos. Best chilling learning and educational videos about this for everyone who wants to get in touch with these computer stuff even when you may be a beginner. Very well done 😊

[pcred]

Woah, where did you find an infinite piece of paper like that? I want one.








:)