3 ms·
I’ve just recently started looking into implementing a minimal ALU, and I’ve been having trouble finding good resources to answer the question “other than a one
by cellularmitosis 7y ago
I’ve just recently started looking into implementing a minimal ALU, and I’ve been having trouble finding good resources to answer the question “other than a one-instruction computer, what is the smallest number of instructions needed in a Turing-complete RISC?”
I’m guessing it would be NAND, ADD, increment, and some sort of branch?
NAND covers all of the bitwise ops. If you have ADD, NOT and increment, you can get SUB. If you have ADD and SUB, you can get MUL and DIV.
Am I missing anything?
- excessive 7y agoI don't mean this the wrong way, but since you know one instruction is sufficient, the next smallest number is two. Maybe by RISC, you meant a small orthogonal set? Load/Store/ALU ops separated? So ADD and NAND work on registers with transfers using LOAD and STORE? Seems like you'd need a branch, unless the instruction pointer was one of your registers. Brainfuck has 8 ops, 2 of which are for input and output. It's Turing complete, and the operations are super simple, but I'm not sure it's RISC-ish. https://en.wikipedia.org/wiki/Brainfuck#Commands https://en.wikipedia.org/wiki/Brainfuck#Commands
- mypalmike 7y agoYou can build ADD and INC from NAND.
- f00zz 7y agoThis (educational) ISA has just NAND and ADD: https://user.eng.umd.edu/~blj/RiSC/RiSC-isa.pdf https://user.eng.umd.edu/~blj/RiSC/RiSC-isa.pdf
- cellularmitosis 7y agoExactly what I was looking for, thanks so much!