Read the original article here.

---

The Forbidden Code: Unveiling Computation's Bedrock

Chapter X: The One-Instruction Revelation - Building Universes from Nothing

Mainstream programming education often starts with high-level languages, abstracting away the intricate dance of bits and logic happening beneath. We learn about variables, loops, functions, and objects, rarely pausing to consider the absolute, irreducible minimum required for computation. This chapter delves into the realm of the One Instruction Set Computer (OISC), a radical concept that strips away complexity to reveal the fundamental building blocks. In the world of "Forbidden Code," understanding OISCs isn't just an academic exercise; it's about seeing the matrix, understanding how anything is possible with almost nothing, and gaining a profound appreciation for the layers of abstraction we typically take for granted.

1. What is a One Instruction Set Computer (OISC)?

Let's start with the core concept that sounds almost like a paradox.

One Instruction Set Computer (OISC): Also known as a Minimal Instruction Set Computer (MISC), an OISC is a theoretical or experimental computer architecture that has only one instruction in its entire instruction set. Despite this extreme simplicity, carefully designed OISCs can still be Turing complete, meaning they are theoretically capable of performing any computation that a general-purpose computer can.

Think about that for a moment. Every operation – arithmetic, logic, data movement, control flow – must be synthesized using repetitions and variations of just one single command. This is the ultimate challenge in computational minimalism, and it forces a programmer (or compiler) to think about computation in the most fundamental terms.

2. The Grand Challenge: Computing with Monotony

The immediate question is: How can a machine with only one instruction possibly do anything useful? How do you add two numbers, compare values, or execute a loop? The answer lies in the careful selection of the single instruction and ingenious techniques to build all other necessary operations upon this sole primitive.

This is where the "forbidden" aspect comes into play. While you won't write large applications in OISC assembly, the mental exercise of synthesizing complex behavior from such a basic element teaches you deep truths about:

• Computational Primitives: What are the absolute necessary actions a computer must perform?
• Data Representation: How can data (numbers, instructions, addresses) be manipulated by a single operation?
• Self-Modifying Code and Indirect Addressing: Since you can't easily change the operation itself, you often rely on changing the data the operation acts upon, or even changing the instruction's operands in memory (treating code as data).
• The Power of State and Sequencing: Computation is about changing state over time. Even with one instruction, the sequence and the data locations it operates on create complex state transitions.

3. Choosing the Primordial Instruction: Common OISC Architectures

The power of an OISC hinges entirely on the single instruction it possesses. Not just any instruction will do. It must be carefully chosen to be computationally potent enough to allow the synthesis of other operations. Several types of instructions have been proposed and studied for OISCs:

3.1. Subtract and Branch if Negative (SBN)

One of the most famous and well-understood OISC instructions is "Subtract and Branch if Negative."

Subtract and Branch if Negative (SBN): An instruction format often seen as SBN A, B, NextAddr. This instruction performs two actions:

1. It subtracts the value stored at memory address B from the value stored at memory address A, storing the result back into memory address A (Mem[A] = Mem[A] - Mem[B]).
2. It checks the result. If the result (Mem[A]) is negative, the program counter (PC) is set to NextAddr, causing execution to jump to that memory location. Otherwise, the PC is simply incremented to the next instruction (PC = PC + 1).

Why SBN is Powerful: SBN cunningly combines arithmetic (subtraction), memory access (reading/writing operands), comparison (checking for negative), and conditional control flow (branching). With subtraction, you can derive addition (as A + B = A - (-B)). The conditional branch allows for decision-making and looping. The explicit next address allows for jumps. It's a Swiss Army knife packed into a single instruction.

3.2. Move (MOV)

Another class of OISCs uses a variation of a simple move instruction, often combined with indirect addressing or execution capabilities. These are sometimes called Transport Triggered Architectures (TTA) if the act of moving data between specific functional units triggers operations.

Move (MOV) or Load/Store Architecture: An instruction format like MOV A, B. This instruction typically copies the value from memory address B to memory address A (Mem[A] = Mem[B]). In some OISC variations, the move might trigger operations if the source or destination is a special functional unit (like an ALU or PC register).

Why MOV can be Powerful: On its own, a simple MOV instruction seems useless for computation. However, its power emerges when combined with:

1. Implicit Operations on Special Registers: Moving data to or from certain memory-mapped locations or registers might trigger operations (e.g., moving a value to the "addition" register loads an operand). This is the core idea in TTA.
2. Self-Modifying Code: By treating instructions themselves as data in memory, a MOV instruction can change the operands of a subsequent instruction, effectively changing its behavior.
3. Moving to the Program Counter (PC): A MOV PC, Address instruction is an unconditional jump.

3.3. Subtract without Borrow (SUBLEQ / SUBGT)

Instructions that perform subtraction and then branch based on the result relative to zero (e.g., "Subtract and Branch if Less than or Equal to Zero" or "Subtract and Branch if Greater Than Zero") also form the basis of Turing-complete OISCs, similar to SBN. SUBLEQ (Subtract and Branch if Less than or Equal to Zero) is another common theoretical model.

4. Building the Universe: Synthesizing Operations with One Instruction

This is the "forbidden art" – taking the single instruction and building everything else from it. Let's focus primarily on the SBN instruction as it provides clear examples of arithmetic and control flow synthesis. Assume our SBN instruction is SBN A, B, NextAddr: Mem[A] = Mem[A] - Mem[B]. If Mem[A] < 0, jump to NextAddr, otherwise proceed to the instruction at PC + 1. We'll also assume we have access to pre-defined memory locations holding constants like ZERO (containing 0) and ONE (containing 1).

4.1. Zeroing a Memory Location

How do you set a variable X to zero?

• SBN X, X, AfterZero (Subtract Mem[X] from Mem[X], result is 0. Store 0 in Mem[X]. 0 is not negative, so proceed to AfterZero). This is a fundamental operation needed constantly.

4.2. Moving Data (DEST = SRC)

How do you copy the value from memory location SRC to DEST? This is trickier than it seems, as SBN modifies the destination. A common pattern involves using a temporary location and the zeroing technique:

1. SBN TEMP, TEMP, L1 (Zero out TEMP)
2. L1: SBN TEMP, SRC, L2 (Subtract Mem[SRC] from Mem[TEMP] (which is 0). Result is -Mem[SRC]. Store -Mem[SRC] in TEMP. If -Mem[SRC] < 0 (i.e., Mem[SRC] > 0), branch to L2, otherwise continue).
3. L2: SBN DEST, DEST, L3 (Zero out DEST)
4. L3: SBN DEST, TEMP, L4 (Subtract Mem[TEMP] (which holds -Mem[SRC]) from Mem[DEST] (which holds 0). Result is 0 - (-Mem[SRC]) = Mem[SRC]. Store Mem[SRC] in DEST. If Mem[SRC] < 0, branch to L4, otherwise continue).
5. L4: ... (Continue program)

Notice the complexity! A simple MOV takes multiple SBN instructions. This highlights the immense overhead of working at this level.

4.3. Addition (A = A + B)

How do you add Mem[B] to Mem[A]? Remember A + B = A - (-B). We need to compute -Mem[B] first, then subtract that from Mem[A].

1. SBN TEMP, TEMP, L1 (Zero out TEMP)
2. L1: SBN TEMP, B, L2 (Compute -Mem[B] and store in TEMP. Branching behavior here is irrelevant for the addition step, only for control flow derived later).
3. L2: SBN A, TEMP, L3 (Subtract -Mem[B] from Mem[A]. Mem[A] = Mem[A] - (-Mem[B]) = Mem[A] + Mem[B]. Branching behavior again potentially irrelevant for the addition itself).
4. L3: ... (Continue program)

Again, addition requires a sequence of instructions and a temporary variable.

4.4. Unconditional Jump (JMP Label)

How do you always jump to a location Label? We need to force the branch condition (Mem[A] < 0) to be true. Assume we have a memory location ZERO containing 0 and ONE containing 1.

• SBN ZERO, ONE, Label (Subtract Mem[ONE] (1) from Mem[ZERO] (0). Result is -1. Store -1 in ZERO. -1 is negative, so jump to Label). This is a common idiom for unconditional jumps in SBN architectures. It temporarily modifies the value at ZERO, but since we only jump, the value doesn't matter after the branch occurs.

4.5. Conditional Jumps (Beyond Negative)

The SBN instruction directly provides "branch if negative". How do you achieve other conditions like "branch if zero", "branch if positive", "branch if equal", "branch if not equal", etc.? You build them up using combinations of subtractions and the "branch if negative" primitive.

• Branch if Zero (BEQ A, B, Label): Jump to Label if Mem[A] == Mem[B]. This is equivalent to checking if Mem[A] - Mem[B] == 0. And X == 0 is equivalent to !(X < 0) AND !(0 < X). So, you might compute A - B, check if it's negative. If it is, don't jump to Label. If not, compute B - A (using temporary storage or carefully managing registers) and check if that is negative. If neither A-B nor B-A is negative, then A-B must be zero, and you jump to Label. This requires multiple SBN instructions and clever sequencing.

• Branch if Greater Than (BGT A, B, Label): Jump to Label if Mem[A] > Mem[B]. This is equivalent to Mem[B] - Mem[A] < 0.

  1. SBN TEMP, TEMP, L1 (Zero TEMP)
  2. L1: SBN TEMP, A, L2 (TEMP becomes -Mem[A])
  3. L2: SBN TEMP, B, L3 (TEMP becomes -Mem[A] - Mem[B]) Wait, this isn't right. B - A is B + (-A). Need a temp that holds -A. Correct logic for BGT A, B, Label (If A > B, which is same as B - A < 0):
  4. SBN TEMP, TEMP, L1 (Zero TEMP)
  5. L1: SBN TEMP, A, L2 (TEMP becomes -Mem[A])
  6. L2: SBN B, TEMP, L3 (Mem[B] = Mem[B] - (-Mem[A]) = Mem[B] + Mem[A]. Still not B-A...)

  Let's rethink BGT A, B, Label using B - A < 0. Need to compute B - A without destroying A or B if possible, then check the result.

  1. SBN TEMP_B, TEMP_B, L1 (Zero TEMP_B)
  2. L1: SBN TEMP_B, B, L2 (Copy B to TEMP_B. Need multiple steps as shown in 4.2 MOV) - This shows how painful it is!

  A simpler approach for conditional jumps is often to compute the difference and then use multiple branches to filter: To implement BGT A, B, Label (A > B <==> B - A < 0):

  1. SBN TEMP, TEMP, L1 (Zero TEMP)
  2. L1: SBN TEMP, A, L2 (TEMP = -A)
  3. L2: SBN B, TEMP, L3 (B = B - (-A) = B + A) -- This is wrong, modifies B.

  Let's use the SBN Dest, Source, NextAddr format meaning Mem[Dest] -= Mem[Source]. If result < 0, goto NextAddr. Otherwise, goto next instruction. To jump to Label if Mem[A] > Mem[B] (i.e., Mem[B] - Mem[A] < 0):

  1. SBN TEMP, TEMP, L1 (Zero TEMP)
  2. L1: SBN TEMP, B, L2 (Compute -Mem[B]. TEMP now holds -Mem[B]. Branching irrelevant here.)
  3. L2: SBN A, TEMP, L3 (Compute Mem[A] - (-Mem[B]) = Mem[A] + Mem[B]. Branching irrelevant.) -- Still not getting B-A.

  Okay, let's use the standard SBN definition where SBN A, B, C means Mem[A] -= Mem[B]. If Mem[A] < 0, jump to C. Otherwise, go to next instruction. Need ZERO (addr with 0), ONE (addr with 1), TEMP1, TEMP2. To implement JUMP_IF_A_GT_B (A > B <==> B-A < 0) to LABEL:

  1. SBN TEMP1, TEMP1, L1 (Zero TEMP1)
  2. L1: SBN TEMP1, A, L2 (TEMP1 becomes -A)
  3. L2: SBN B, TEMP1, L3 (Mem[B] becomes Mem[B] - (-A) = Mem[B] + A) -- Still modifies B! This is the key difficulty: SBN is destructive to the destination.

  To compute B - A non-destructively and check if negative:

  1. SBN TEMP1, TEMP1, L1 (Zero TEMP1)
  2. L1: SBN TEMP1, A, L2 (TEMP1 becomes -A)
  3. L2: SBN TEMP2, TEMP2, L3 (Zero TEMP2)
  4. L3: SBN TEMP2, B, L4 (TEMP2 becomes -B) -- No, this doesn't help.

  Let's use the method that calculates the difference in a temp location. To compute Diff = B - A:

  1. SBN TEMP1, TEMP1, L1 (Zero TEMP1)
  2. L1: SBN TEMP1, A, L2 (TEMP1 = -A)
  3. L2: SBN TEMP2, TEMP2, L3 (Zero TEMP2)
  4. L3: SBN TEMP2, B, L4 (TEMP2 = -B)
  5. L4: SBN TEMP1, TEMP2, L5 (TEMP1 = -A - (-B) = B - A. Branch if B-A < 0). If branch occurs, jump to LABEL. If not, proceed to L5.
  6. L5: ... (If A was NOT > B) This sequence computes B-A into TEMP1 and branches if the result is negative (i.e., if A > B). This is the pattern: compute the value needed for the comparison in a temporary location, then apply SBN to that temporary location vs ZERO (or another value if needed) to trigger the branch.

4.6. Loops

Loops (like while or for) are built using a combination of conditional jumps and operations to modify a counter or condition variable. A simple countdown loop might look like this (using pseudocode and SBN concepts):

LoopStart:
  SBN Counter, ONE, LoopEnd  ; Decrement Counter. If Counter < 0, jump to LoopEnd.
  ; ... instructions inside the loop ...
  SBN ZERO, ONE, LoopStart   ; Unconditional jump back to LoopStart
LoopEnd:
  ; ... code after the loop ...

This requires Counter to be initialized to a positive value, ONE to hold 1, and ZERO to hold 0.

5. The Theoretical Underpinning: Turing Completeness

The ability to synthesize basic arithmetic (addition, subtraction, zeroing), data movement, and conditional branching (including unconditional jumps) is the key to the theoretical power of OISCs.

Turing Completeness: A system of data-manipulation rules (like a programming language, logical calculus, or instruction set) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine. This means it can perform any computation that a general-purpose computer can.

Because OISCs like SBN can emulate the operations of a basic register machine (which is known to be Turing complete), they themselves are Turing complete. This proves that in principle, a single instruction is all you need to compute anything computable.

6. Why Bother? The Philosophy of Minimalism and the "Forbidden" Insight

Given the extreme difficulty and inefficiency of programming an OISC, why are they studied?

• Understanding Fundamentals: OISCs force you to confront the absolute basics of computation. How can data be represented? How can state be changed? How can control flow be managed? It strips away the comfortable layers of abstraction and reveals the underlying machinery.
• Challenging Assumptions: We're taught that computers need complex instruction sets (RISC vs. CISC debates). OISCs prove this isn't strictly true from a computability standpoint, though it's essential for performance and programmability. Studying OISCs makes you question why things are designed the way they are.
• Compilers and Abstraction: Thinking about how to compile higher-level constructs (like if statements, for loops, arithmetic expressions) down to a single instruction set provides deep insight into the process of compilation and the nature of abstraction layers in computing. It's the ultimate exercise in target architecture mapping.
• The Elegance of Constraint: There's a certain beauty in seeing how complex behavior emerges from such severe constraints. It's akin to understanding how all matter is built from a few fundamental particles and forces.
• Minimal Hardware: Theoretically, an OISC could be implemented with incredibly simple hardware, perhaps useful in highly constrained environments (though practical performance is a major hurdle).

In the context of "The Forbidden Code," OISCs are the ultimate lesson in looking beneath the surface. While you might not code in SBN, understanding how a simple subtraction and conditional branch is enough to build addition, loops, and decisions gives you a powerful perspective. It's the computational equivalent of understanding that complex biological life emerges from simple chemical reactions governed by physical laws. It demystifies computing by showing its most basic, raw form. It's the bedrock they don't teach you in standard classes because it's hard, impractical for everyday tasks, but reveals profound truths about the nature of computation itself. Mastering this concept means you understand the roots from which all complex software and hardware ultimately grow.