One Instruction Set Computer

Re:One Instruction Set Computer by cellularmitosis on Sunday December 08, 2019 @01:39AM (#21734648)

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?

[ Parent | on HN ]

Re:One Instruction Set Computer by excessive on Sunday December 08, 2019 @02:59AM (#21734833)

I 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

[ Parent | on HN ]

Re:One Instruction Set Computer by f00zz on Sunday December 08, 2019 @05:34AM (#21735241)

This (educational) ISA has just NAND and ADD: https://user.eng.umd.edu/~blj/RiSC/RiSC-isa.pdf

[ Parent | on HN ]

Re:One Instruction Set Computer by cellularmitosis on Sunday December 08, 2019 @10:55AM (#21736482)

Exactly what I was looking for, thanks so much!

[ Parent | on HN ]

Re:One Instruction Set Computer by mypalmike on Sunday December 08, 2019 @05:18AM (#21735205)

You can build ADD and INC from NAND.

[ Parent | on HN ]