If a NAND gate is universal, why you don't have NAND OISCs

Question

If a NAND gate can be used to construct all other of the basic logic gates, then I'm wondering why you don't/can't have a purely NAND-based One Instruction Set Computer (OISC). All the OISC single instructions are complicated like "addleq, add and branch if less than or equal to zero", but I don't see why you can't just have an OISC be "nand, perform nand operation". Wondering what I am missing.

• gnasher729: Without branching, the best you can do is a very long sequence of nand operations. Doesn't sound very general to me.
• user99558: @gnasher729 most likely the following works: Define $ip := \texttt{Mem[}0\texttt{]}$ and transpile each addleq instruction using $\big[\texttt{Mem[}1\texttt{]},\dots,\texttt{Mem[}N\texttt{]}\big]$ as scratch space into a (very) long nand-sequence. $N$ depends on word size, but fix and therefore you can use the remaining memory for programming.
• user99558: (even if $N$ wasn't fix, you could use even/odd indexing or the like)
• user99558: Actually, not sure if this works since nand is not able to propagate bits, more trickery is needed (defining nand to work on $\texttt{Mem[}a\texttt{]}_i$ and $\texttt{Mem[}b\texttt{]}_{i+1}$ could work?).

Answer 1

The NAND gate is "universal" in that a network of NAND gates can implement any combinational or sequential logic function.

So to construct a "program" out of NANDs all you need is a way of specifying the network that interconnects them.

So if every NAND gate in your "computer" has a address, and the list of instructions is of the form inputA,inputB you might have a start on a "computer" with one instruction that's a NAND. (I think you'll have to come up with a parallel semantics, no instruction pointer.)

Answer 2

With such an instruction set, all you could express are straight-line programs. Without branches, you can't have loops. Thus, the program would not be able to handle arbitrary-length inputs: it would be limited to dealing with fixed-size inputs (or inputs with a fixed known upper bound on the size of the input). So, that wouldn't be very satisfactory.

• user99558: What prevents us to modify the instruction pointer in case it's stored at memory location 0ドル$?
• user99558: Different (even more interesting, but more tricky to get right) idea: Initially $\texttt{Mem[}0\texttt{]}$ is non-zero, the program will loop indefinitely until said memory location is zero. Pretty sure this will work too.
• D.W.: @KVN, performing an arbitrary operation on the instruction pointer (such as an increment, or a compare-and-set branch) requires multiple NAND operations, i.e., multiple instructions. That's trouble. After you perform the first instruction (the first NAND operation on the instruction pointer), the IP gets updated, and you jump off somewhere strange (not the end result of the multi-NAND computation, but to a program location based on some intermediate result). It might be possible to deal with this somehow, but it's not entirely clear how, and the programming model sounds horrifying.