I bought a CPU on ebay that had only one instruction implemented. I believe it was Halt and Catch Fire.

I learned this 50 years ago in a computer class. The instruction was subtract and store.

"You had ONE instruction"

I'm reminded of an old saying that, every piece of software has inefficiencies, meaning some instructions can be taken out without changing the functionality. And every piece of software has bugs in it, bits and parts that don't function as required. So by inference one can conclude that every piece of software can ultimately be reduced to a single instruction that doesn't work.

MOV is also Turing-complete.

The instruction set is bloat -Luke Smith, probably

This brings me back down memory lane, where I was writting code *on paper* for educational purposes. I took computer classes and for like a whole semester we didn't even touched a computer!

The earliest 6800 chips (not 68000 they were way later) were sort of 1 instruction in that if you executed it, it would never execute another instruction again. The assembler mnemonic was HCF . Halt and Catch Fire (and some really sarcastic developer really did put that in their assembler software). Basically there was a screw up where it set one accumulator, reset the other, and then dumped them both simultaneously onto the internal data bus. All in one clock cycle too. Quite efficient.

This only works because the instruction itself is doing multiple things at the same time: loading from two different addresses, storing into another, and branching. It's kind of like saying "this knife can open wine bottles and also provide light" and learning that it's a Swiss Army knife with a bottle opener and a mini-flashlight as part of its base.

I remember many years ago someone saying you could implement a cpu with just a subtract instruction. Thanks for finally completing my knowledge! I can now die happy :)

Next we need to build this CPU with just NAND gates. :D

Aristotle writes in his physics that we only need three principles to describe the whole world. Here we have one solution how.

Machine code: Wtf "On the other hand there is an assembler"... Assembler: Wtf

The 1 instruction is HALT.

A friend in college actually built a one-instruction computer (not sure if it completely worked) as an electronics project that he did somewhere around late high school (I think). He described that one instruction as "subtract, and branch if negative." Somehow that sounds similar to what I think "SUBLEQ" stands for.

One instruction with a complex inner instruction set ;)

This is supreme!!! ♥ Waiting for the next one in the series!!!

I cannot believe the quality of your channel content. You are AWESOME!

on the other hand: there is a glimpse of how emulators are created.

Stellar video! Very nice. Loved every bit of it.

I, for one, would love to see more detail about the Assembler, pretty please!

... and now build this CPU with only NAND gates ;-)

Because you always change the sign (due to using subtract), if you need to add you just subtract from 0. This means addition takes 2 operations and 1 extra memory location (to store the 0) compared to also having an addition operator. Because you need extra entropy in the form of data storage to pull this off, the subtraction-only computer is actually an addition and subtraction computer, but one of the ops is stored with the data itself (assuming Two's Compliment). You can't pull this off without the second operation being in the data itself, because ultimately negative values don't really exist in binary. Negative numbers are simply positive numbers (or rather, vectors - and positive and negative are the direction of the vector) with a yet-to-be-executed operator encoded along with them. -2 is "subtract 2's worth of value". +2 is "add 2's worth of value". 2 is a number. -2 is nearly a number, but convention says if the second value isn't supplied, use 0. Fractions are the same, two numbers yet to be divided. They aren't values in their own right yet. It's a beautiful example of how the line between operations and data is way more blurred than one might think. The addition of 1 needs also needs a "1" to be stored somewhere. This requires another bit of memory to store, and so in totality the subtraction-addition-and-increment is as entropy dense as a computer that has three op codes, addXY, addXY (but sign flip Y), and add1. They are the same amount of "complex", it is only that the former has more constants, and the latter more operations. TL;DR: It's only a single operation computer because of how the term "operation" is defined, and really when one says "special subtraction" one really means "the default is subtraction but constants stored in data can also modify it's behaviour". I'm not trying to nit-pick or be a dick or anything, i'm just trying to explain how you can't actually get Turin Completeness with 1 operation, you have to be a little crafty with the definition of operation.

you should be able to design a cpu with only one instruction and two registers. one register contains the set of bits to be changed, the other register contains a set of bits that defines which bits are to be flipped. it would be a nightmare to try design the rest of the computer around the cpu, and I wouldn't want program for it, but you could do it. it would be up to the programmer to decide which bits needed to flip for any particular situation, making it not fun to program, but you could do it and it would be a very fast cpu. because it's just the one instruction it would be relatively simple to design the system for as many bits as you wanted. you could design the machine to use 256 bit registers, 1024 bit registers, whatever. actually getting it to accomplish anything would be a nightmare, but if someone were willing to tackle making a usable programming language for it, it would be very very fast.

SUBLEQ is Turing-complete. Awesome!

Well, you could just consider a group of many instructions to be one instruction where the opcode is considered an argument to the one instruction. Of course, it wouldn't be a very simple instruction.

This was very cool! Thanks for sharing.

Hey Gary! Another neat One Instruction Set Computer design is a Transport-Triggered Architecture, where you only have MOV, but by MOVing data into special registers you can perform arbitrarily defined operations on that data; you might have two registers, ACC and SUB, and to compute a minus b you MOV a ACC, MOV b SUB, where the SUB register takes in data and subtracts it from ACC at every clock cycle.

Cool! Reminds me of a Textbook I read in University called Nand-to-tetris which went through the steps of building an entire VM that has a playable version of tetris, just from building an initial nand gate

SUBLEQ is actually a complex instruction as it contains branching instruction. So your computer is actually CISC machine. Period. Proving: If I follow your logic, I can then make "single-instruction" CPU with instruction like SUBLEQSINJMPRET... Technically it would be "single instruction", with a lot of implicit logic behind the scenes.

Thank you, you are always thought-provoking!

Substract and Check value and Conditional Jump in a single instruction!

This reminds me of NAND gate one of a universal gate .

As it turns out, the move instruction is also Turing complete. I remember someone made a compiler that uses only move instructions a few years ago.

Wonderful! I've heard about the MOVE-processor in the 90's. Nice to see the concept now in practice. And although I haven't done machine code since halfway the 90's, your video feels like slipping on an old glove :)

When I click on this and saw you starting to explain the subleq instruction, I've immediately imagined something like what you has described. Maybe because in my times as IT engineering student, I learned to program for the URM machine. The Unlimited Register Machine, has only 4 instructions. All registers start at zero. Instruction Z(r), resets/zero the register, instruction S(r) put in the register the successor of is value. Instruction T(r1, r2) transfer/copy from register r1 to register r2, and J(r1,r2,i) jumps to instruction i, if registers r1 and r2 are equal. So one can create programs to add, to subtract, then with those we can create multiplications and divisions, and so on. Curiosity, all programs for URM are numerable, that is, there is a way to transform any program into a single number, or to transform a number (no matter how big it is) back into a program. As for the SUBLEQ, you didn't told how to set values in memory. Will 7, 5, 1, 25, or 173 magically appear in memory, if we have to use them? However this OISC is awesome!

Now imagine being the guy tasked to write a C compiler to this instruction set

That's an impressive idea, given that a textbook turing machine, while only slightly more complex, is NOT a single instruction machine... XD

Damn! Thanks for this video, amazing video, like always, thanks for the time and effort!

11:20 Doing some figuring on paper leads me to believe that maybe address -1 is the output. This is what I wrote when trying to decode this: a=0 Z=0-p (p=[H]) a=0-(0-p) a:0 (-1) If H==100 then a=0 Z=0-100=-100 a=0-(-100)=100 a:100 (-1) This shows me that (if im interpreting this right) the value at address 100 which is the letter H is being subtracted from the value at address -1. So that leads me to beleve the address -1 is reserved for screen output. Thanks for taking the 30 sec to explain that.

My brain has only one instruction, and it's NOP.

Nice video, it'd be good to see that CPU implemented in logic.. And not just VHDL or simulated logic... Using some old fashioned NAND gates.

I want to see how all that works. Please make more videos about it!

thank you, this will help alot in my project

would be curious to program an FPGA to do just that !

If we were able to transform such code efficiently to the assembler of every CPU, we would have a plattform independent assembler.

Gary... You are awsome. Good explanation.

It's been a while I've watched Gary's videos. Good to be back 😌😌

its great when people realize how simple it is after being told how it actually works!

position Z is acting as a registry: holds value, helps in processing, is returned to 0. it's a registry, for all intents and purposes.

Excellent video! Wow, i would hate to program that processor, though. Writing a language like Sweet16 would be laborious. I designed a CPU instruction set with only 16 instructions, so that we could keep the opcode to 4 bits. My instruction set is: Add, AND, NOT, OR, SHR (shift right), SUB, XOR, LDA #, PSH, Pop, RDA (read memory into A), STA (store), JC (jump if carry set), JN (jump if negative), JZ (jump if zero)... That's it. I used to program in Z-80 assembly, so this is what I thought I could live with if I had to write a language in it. I'm amazed you have done that! I have subscribed.

That kind of clever esoteric piece of software. Like it!

Great video. There is also a really nice talk here on UKposts by Christopher Domas on how you can actually get away with only using the MOV instruction on x86. Branching is the biggest issue there, so you basically have to loop through all your code for every branch. But it's really neat, and a cool obfuscation method :) Look up "the movfuscator" on youtube.

i'm gonna write a xilinx rtl for this i think

In this way the execution of a program can be visualized in the square address x address as the temporal progression from one point to another. An instruction is a point in the room address x address x address. The program itself is a discrete sequence of points in this room.

i really like this! this can be very efficient if pipelined and jmps are better managed

2:19 And I was thinking who is Link in description. lol

Now implement it with NAND-gates!

I designed a mov computer in 1990. Has registers only. Many of which are specialized and are ports to funcional units. The functional units are ALU, stack, jumping, memory etc. Constants could be taken from the next instruction. Can be extremely small or do multiple instructions in parallel. I mainly focused on the latter and it seemed to work well for digital signal processors. Instruction size of 16 bits combined in words of 32 or 64 bits. DSPs ofren use wide instructions. Moves can also happen while the function unit is still working, like memory access. This allows very simple parallism if organized correctly. Never made it to hardware though. Later added a few condition upcodes from moves to the same place. This can be used when you want an extremely small instruction size of 8 bits with only 16 registers/ports.

Amazing, I wouldn't have even thought of this! If I had to guess, I would've thought maybe 10 instructions was the minimum possible, and I wouldn't have even known which of those instructions were necessary. Never would've guessed just 1 instruction, and that's an implied instruction at that, so no real opcode for it. I wonder if people are going to use this 1 instruction instruction-set as a proof of concept for future processors?

I implemented a SUBLEQ machine as my 20% project at Google

Having multiple instructions is bloat.

There are other one instruction sets as well. I've built a couple in FPGAs. My latest is a transport triggered architecture, where the one instruction is a move from one register to another. All functional units (think your ALU, load/store unit, etc) have known addresses on the bus, and the instruction might also specify a sub address which allows the functional unit to perform multiple operations. One register that's connected to the functional unit will be the "trigger" instruction -- such that, whenever you schedule an instruction, and it's decoded, executed, if that instruction moves data into a functional unit's trigger register, the operation will be performed that was specified -- i.e., if i say to move the value `5` into the ALU's trigger function and specify the ALU's operation as addition, then it'll use the other input as the current value on the data bus, and the execution of the CPU happens as a side effect of the moving of data between registers. These are also known as exposed datapath computers. Really neat, and solve the VLIW register file pressure problem.

Amazing that this seems to work, I wish Gary had been my computer teacher.

*GARY!!!* *Good Morning Professor!* *Good Morning Fellow Classmates!*

What are the advantages of using this type of CPU?

Awesome. You blew my mind.

Loved this video. =) Always nice to learn something new about CPU designs. ^^

Therry Davis would have liked this...

mov in x86 is Turing complete. Just saying. There is a movfuscator, a single instruction compiler for x86.

Amazing video!

Glad that we figured out to multiply or decide by 2 is to just shift the bit once.

Simple; Power On, Power Off.

It must have been bad at listening to instructions. An extra stupid CPU.

Would love the follow up video mentioned!

All boolean operations can be made with just a series of "Nand" gates. For example tie the inputs of a Nand gate together you get a Not gate. Put that not gate on the output of another Nand gate and you now have an And gate. Arrange Nand and And in parallel and you can create OR/NOR with a bit more you can create XOR. You now have the 6 basic boolean operators from which you can design any digital circuit including a cpu. A Nand gate is the simplest gate to make as it only requires two transistors.

Why not copy a to b like this: b = z - a b = z - b Assuming z is always 0 then this should work just fine, but takes half as many operations. Edit: Looked it up, and it doesn't work because the instructions can't be represented in subleq. All instructions must be precisely on the form: x = x - y

What you are describing is NOT a RISC machine. It imay well be a one instruction machine - but it is a complex instruction.

A crazy idea, and quite entertaining. Cool.

That reminds me of the "Computer '74", a project of the Dutch magazin "elektuur". The name not only stands for the year, but also for the piles of 74xx chips used to build that monster. It was programmed in octal, it had no opcodes but every command consisted of two addresses: from and to. It also had a hardware multiplier and a hardware divider!! It has not only memory addresses, but also special addresses for the adder, divider, and of course an address for the program counter. Funfact: It already had a diode matrix for the microcode.

You basically take control of load, store, sub and jlz instructions in one instruction. Nice.

You can still have different mnemonics on different use of the SUBLEQ instruction. That is often done in ordinary architectures, like MIPS and ARM.

Great video!!

I thought this might be bbj (byte byte jump, it's on esoteric langs) but I've realised I might be misremembering it. thank you for a tech video without binary the abstraction is nice

A concept we discussed at school way back in time was a single instruction CPU whose only instruction was MOVE - take data from one location in memory and write it to another location. Now, it was cheating somewhat since it relied on existence of coprocessors which would watch certain memory locations and do arithmetic operations on them, putting result into another location. But while the SUBLEQ CPU is essentially an academic toy as pretty much any calculation is extremely inefficient, the MOVE CPU is much closer to how a real CPU microcontroller works. And it was still single instruction CPU in the sense that all instructions were move instructions.

Hi Gary! Interesting, but I am not sure if the increase in the number instructions is really giving a massive improvement in performance, even if we eliminate the instruction decoding. I read about a single instruction set CPU developed in Leyden university that I thought was very interesting, because it only has a load instruction with a very large number of registers that were input or output for arithmetic or logical instructions. That allows for the compiler to organize the code into multiple instruction pipelines. Therefore the parallel performance can be scaled by adding additional arithmetic/logical registers to the CPU. I thought that was a very interesting feature of that design. As to the subleq, to it really has only utility in illustrating the feasibility, similar to the original Turing machine. Sure you can write universal code with it, but I will be a collosal pain and is probably not very fast.

I might just have to give programming another try. Thanks!

This is both a RISC and CISC architecture, since the latter is about the complexity of the indviidual operations. And I consider this minus one to be quite complex (involving two addresses and conditional jump.) Additionally, it is counter the idea behind RISC -- to only have simple instructions -- but since the formal definition of RISC deals with the cardinality of the set primarily, it is indeed RISC.

It's kind of funny that the ultimate RISC is also the ultimate CISC -- the main distinguishing feature between RISC/CISC is not really fewer instructions, but restriction of source/destination operand types to exclude memory access in RISC, so they used to be called "load-store" architectures because you had to use instructions like LW and SW to transfer data between memory and registers. Although MOV on x86 is even more bloated than SUBLEQ, allowing for all sorts of crazy operations (like copying a word between two memory locations and incrementing index registers at the same time in one instruction).

Super intriguing

How to create a one instruction computer: Take ANY instruction set, redefine every instruction as EXEC with options. Job done!

Whoaaaa, cool, this will be the subject of a FPGA/CPLD design, for sure I will use it.

Binary subtraction is actually a form of *addition.* It works like this: 1. Each bit of the _subtrahend_ ( i.e., the number that is to be subtracted from the other number, called _minuend_ ) is _inverted_ (i.e., if it's a one, it's changed to a zero, and vice versa), giving the _ones' complement_ of the subtrahend. 2. The ones' complement is then incremented by one to give the _twos' complement_ of the subtrahend. 3. The twos' complement is then *added* to the minuend, to give the result that includes a carry (i.e., an extra one to the left of the result, which is always discarded). At the hardware-level, computers always add; they *never* subtract.

My first thought was to use add, but subtract is far better I guess :D

Cool, please go ahead with the 'hello world' explanation!

That "special subtract", given the implicit move and branch, is a complex instruction

This SUBLEQ is more of a 1 instruction CISC Computer. RISC Architecture is more about getting things done in 1 or the fewest possible clock cycles with optimized hardware.

Surprisingly there is just a little bit of commonality with the architecture I been working on. My memory structure is unimaginably different. There are a good number of bytes that work together each with their own functionality, I was referring to them as registers. But they actually aren't, Just realized my architecture doesn't have registers! But it's definitely not a single instruction, and everything is a link list kind of branch. It doesn't have an arithmetic unit, you write the logic to form the arithmetic alongside of the code you're writing to do the math... each and every time. Because of the memory structure it's parallelism is literally unlimited. Your code basically becomes permanent physical threads. Please reach out to me Gary! After seeing this I realized I could remove a lot of my instructions making the architecture not so expensive!

Amusing. Of course there were a number of early machines that only had a subtract instruction and not other arithmetics, so that part of the idea isn't all that radical. And certainly 3-address machines with a branch-on-condition address existed fairly commonly in the past. The IBM 1401 comes to mind. You can actually reduce the hardware complexity of the machine by replacing the single instruction with "move bit a to b and branch to c if zero". Then you don't need an arithmetic unit at all, your data path is 1 bit wide, no adder or multi-bit comparator. All of these designs suffer from not having index registers or an index capability in the addressing. But you can add that complexity while still keeping a single instruction; you just define several memory addresses to be index registers and have an address pattern that will implicitly add (or subtract) an index value from the address in the instruction.

So you have a minimum of two commands, compare & branch. But you have to load registers, memory.... You need to account for the cycles to accomplish each instruction. Then factor in that things like MVCL looses control and can result in unknown values. So best practice suggests a DEFRC is added. I prefer a loop with MVC than a MVCL. You only have 500ms before you must loose control.