Talk:OISC

I replaced back Bounded-storage machine with Linear bounded automaton (LBA), because the first is an informal name and it does not define or correspond to Computational class category at all. The article describing BSM focuses on the input defined by the language. There are two different input concepts: the first referring to Turing machine input, which is the initial state of the tape; and the second is the language defined input, which can change the state of the abstract machine during computation. The second type of input does not have anything to do with the Computational class, because it is a part of the language's pragmatics (in opposite to language's semantics). Only LBA properly define the class to which all real processors belong. The input in the second sense, can be infinite for an LBA machine, e.g. reading from a port, but this does not change the machine computational ability. --Oleg 00:49, 9 September 2009 (UTC)

I would have thought that real processors belong to the computational class of finite state automata, as their memory is bounded by the fixed amount of available memory during the computation - it doesn't grow by feeding in more input unless your input comes on a rewritable storage medium. Rdococ (talk) 14:28, 1 August 2021 (UTC)

"The simplest known OISC is arguably FlipJump." I believe that this is wrong, here is why. The OISC that it took inspiration from, named Bit-Bit-Jump, can perform conditional jumps, because it can copy any one bit to overwrite the next instruction pointer's 8th least significant bit. If the bit that was copied is a 0, then the instruction pointer decrements by 256 (if it overwrote a 1) or stays the same if it stayed a 0. If the bit that was copied is a 1, then the instruction pointer increments by 256 (if it overwrote a 0), or stays the same if it stayed a 1. Then, the instruction pointer and 192 bits below it are read and stored into the BBJ register. The first 64 bits is the 64-bit Absolute Memory Address to copy one bit from, the second 64 bits is the 64-bit Absolute Memory Address to overwrite one bit with, and the last 64 bits is the 64-bit Absolute Memory Address of the next instruction pointer. If the conditional statement evaluated as false, then it jumps to execute one path. If the conditional statement evaluated as true, then it jumps to execute another path. Okay, now that I have proved how Bit-Bit-Jump can evaluate conditional statements, it is time to prove whether FlipJump can evaluate conditional statements. So, FlipJump is an simplification of Bit-Bit-Jump, because it does not copy any bits, it simply inverts them using a single NOT gate. Now, one must ask the question: How does FlipJump overwrite the next instruction's 7th least significant bit? It doesn't. It can only flip it, which means that FlipJump cannot evaluate conditional statements like Bit-Bit-Jump can. Therefore: Bit-Bit-Jump is actually the simplest OISC and not FlipJump, because it can actually perform computation using a bunch of Bit-Bit-Jump Assembly Macros. Besides, Bit-Bit-Jump is not complicated at all, I implemented it in six lines of Verilog here as proof: (https://gitlab.com/VitalMixofNutrients/vISA/-/raw/vISA/sources/sim/verilator/BBJ/BBJ.v). If I implemented FlipJump instead, it would still take six lines of code. (First line is FlipJumpReg[127:0] <= memory[FlipJumpIPAddr-:128]; Second line is FlipJumpIPAddr[63:0] <= FlipJumpReg[127:64]; Third line is FlipJumpBitAddr[63:0] <= FlipJumpReg[63:0]; Fourth line is tmp[0:0] <= memory[FlipJumpBitAddr]; Fifth line is assign tmp[0:0] <= ~tmp[0:0]; Sixth line is memory[FlipJumpBitAddr] <= tmp[0:0];) TLDR: FlipJump cannot evaluate conditional statements, and it takes the same amount of lines of code to implement in Verilog as Bit-Bit-Jump, making it unfit for being the "simplest" "OISC" (Can't be a OISC without the evaluation of conditional statements, no matter how impossible their evaluation may seem.) --VitalMixofNutrients (talk) 02:37, 5 September 2021 (UTC)

Generality of the OISC concept

What I would like to discuss is the general concept of an OISC as an abstract machine -- a computational model that uses only one instruction (typically Turing-complete) -- with various general types of memory model.

(1) The usual model in which an instruction does not alter the location of any elements in a sequence of memory elements (e.g., bits or integers), but may alter the values of one or more elements. (E,g, an arbitrary element cannot be deleted or inserted in this model, as this could change the location of the other elements.) With this model, the possibilities are vast. For example, consider a language that uses a number of instructions, I₀, I₁, ..., I_n, each of which takes two parameters (a one-parameter instruction just ignores the second parameter), with an integer memory model. This may be reduced to an OISC merely by the following single instruction:

(i, j, k) :: 
if i=0 then do I0(j,k) 
else if i=1 then do I1(j,k)  
...
else if i=n-1 then do In-1(j,k)
else do In(j,k)

E.g., a Minsky machine is reduced to an OISC by the single instruction

(i,j,k) :: if i=0 then do JZD(j,k) else do INC(j)

where JZD(j,k) means "if [j]=0 then jump to k else decrement [j]", INC(j) means "increment [j]", and [j] refers to the content at location j.

Of course, the Turing machine model itself can be similarly reduced to such a generalised OISC.

(2) More-general instructions, not confined to the type discussed in (1). E.g., rather than merely increasing/decreasing/copying one integer in a sequence of integers (or one bit-value in a sequence of bits), an instruction may delete or insert an element in the sequence of elements that comprise memory, allowing the location of the other memory elements to change in the process. flump is of this kind. --r.e.s. (Talk) 17:58, 18 September 2009 (UTC)

The Minsky OISC can be reduced to:

 (i,j) :: if j=0 then INC(i) else JZD(i,j)

if the first line has index 1.

Mafi 10:15, 19 September 2009 (UTC)

Yes, that's a neat idea. Similarly, if all but one of a set of n+1 instructions take just one parameter, with the remaining instruction taking two parameters, then the instruction set can be reduced to a single instruction (i,j), where (i,0),...,(i,n-1) represent the respective one-parameter instructions, and memory indexing begins with index n. (I've taken the liberty of indenting your reply.)--r.e.s. (Talk) 13:04, 19 September 2009 (UTC)

The fact that the single "Minsky OISC" instruction requires only two parameters reflects the fact that its logic is arguably less complex than that of the other common OISC instructions. E.g., incrementing and decrementing nonnegative integers are much simpler operations than binary operations on the set of all integers (negative and nonnegative). --r.e.s. (Talk) 14:08, 19 September 2009 (UTC)

You could even reduce it to:

 (v) ::
 i = oddbits(v)
 j = evenbits(v)
 if j=0 then INC(i) else JZD(i,j)

Here's one example how oddbits and evenbits work:

 v = 7 = 111 base 2
 i = 111 = 11 base 2 = 3 
     ^ ^
 j = 111 = 1 base 2 = 1
      ^

-- Mafi 15:55, 19 September 2009 (UTC)

Ok, it doesn't make sense on a real computer, but it does if the program is saved on a tape whose alphabet is much longer than the number of used registers because then you can store longer programs on the tape.

-- Mafi 20:57, 19 September 2009 (UTC)

I think these are just encoding tricks that amount to "cheating" ;) We could also encode a k-parameter instruction (k ≥ 2), not just a 2-parameter one, as a 1-parameter instruction.--r.e.s. (Talk) 03:28, 20 September 2009 (UTC)

---

Here's an explicit "Turing OISC" corresponding to a TM model with tape alphabet {0,1} and a right-infinite tape:

(i,j,k) :: if the current tape-cell contains i then (ACT(j); goto program-cell k)

where 

ACT(0) :: write 0 into the current cell
ACT(1) :: write 1 into the current cell
ACT(2) :: if the value left of the pointer is 0 or 1 then move the pointer left
ACT(3) :: move the pointer right
ACT(4) :: HALT

• EDIT: I've corrected the above instruction, as it is intended to reflect the 4-tuple form of "internal state" description for TMs, as explained in a reply below. -- r.e.s. 02:05, 22 September 2009 (UTC)

The program resides at addresses 0,1,...,3n-1 and the tape (plus a pointer) begins at address 3n. By convention, all programs end with the pair of triplets (0,4,4)(1,4,4) -- an unconditional HALT that may or may not eventually be executed -- and cell 3n is initialised to the value 2. All tape cells to the right of this contain 0, except possibly for input values. Program execution starts at address 0, and halts when and if HALT is enacted. ACT(0) and ACT(1) write 0 and 1 into the current tape-cell; ACT(2) and ACT(3) move the tape-cell pointer left (when possible) and right. The tape-cell pointer is a single movable value of 2 among the tape-cells, which are all 0 or 1. The current tape-cell is the one to the immediate right of the '2'. Moving the pointer means exchanging it with the value to its left or right. Notice that program-cells may be restricted to contain values in the set {0,1,...3n-1}, the tape-cells contain 0s and 1s only, and the pointer has the value 2; i.e., all the OISC memory cells have fixed finite capacity, but there are infinitely many of them. (An alternative formulation of this OISC could use a program cell as a tape-cell pointer, but this cell, unlike all the others, would have an unbounded value.) --r.e.s. (Talk) 13:33, 20 September 2009 (UTC)

• EDIT: Rather than use a 4-parameter instruction of form "(i,m,j,n) :: if the current tape-cell contains 0 then (ACT(i); goto m) else (ACT(j); goto n)", the present 3-parameter form requires the instructions to appear in pairs, just as do the 4-tuples in this version of the classical TM.-- r.e.s. 14:26, 22 September 2009 (UTC)

That looks nice. But it can be reduced to:

(i) ::
if i=0 then set the current cell to 0
if i=1 then set the current cell to 1
if i=2 then flip the current cell
if i=3 then move pointer left (if possible)
if i=4 then move pointer right
if i=5 then halt
else jump to line i-5 if current cell contains 1 (the first line has index 1)

By adding an explicit goto instruction we need only two parameters. Then I used the idea you wrote under my Minsky Oisc reduction but with 0 and 1 instead of 1 and 2.

--Mafi 13:56, 20 September 2009 (UTC)

My intention was to show that the classical TM model is already essentially in OISC form. The most-common TM formulation uses 5-tuples for the internal states (which would correspond to a 4-parameter OISC), but I used the somewhat less-common 4-tuple form for the internal states, which corresponds to a 3-parameter OISC. For anyone not acquainted with it, the 4-tuple formulation uses a pair of tuples of the following form for each state q (q = 1,2,...,n, say):

<q,0,a_0,q_0>

<q,1,a_1,q_1>

where q is the current state, the second element (call it s) is the current 0 or 1 being read; a_0 stands for the write action or tape-head movement, and q_0 stands for the next state, when s is 0; and similarly for a_1, q_1 when s is 1.--r.e.s. (Talk) 20:51, 20 September 2009 (UTC)

I don't see how "generalized OISC" is any different than an ordinary non-OISC computer. With this definition of OISC, the VAX can be considered an OISC of form (i,j,k,l,m,n,o), where i corresponds to a table that is equivalent to VAX instructions, and j-o are the arguments.

if i=0 then halt
if i=1 then do nothing
if i=2 then return from exception or interrupt
if i=3 then perform a break-point fault
...
if i=11 then compute cyclic redundancy check
if i=12 then probe the value at j for read access
...
if i=56 then use a set of pattern operators to convert BCD to formatted ASCII
if i=57 then search a string for a substring
...
if i=228 then branch if bit j in k is set, and clear bit j in k
...
if i=22013 then evaluate a polynomial treating operands as 64-bit extended floating point
...
if i=43005 then multiply the vector pointed to by k by the value of j and store it in l
...
if i=65279 then initiate a bug fault with j interpreted as a message code

Would this be considered OISC? Ian 09:08, 26 February 2011 (UTC)

Computer and opcodes

The point of OISC is the absence of an opcode. The processor does not have to recognize the instruction. If you call this instruction recognition a part of instruction execution, then yes, you can call it an OISC. But do not forget that OISC is the Ultimate RISC. The aim of RISC is to reduce the number of instructions for hardware simplification, not renaming the instructions. --Oleg 00:59, 21 September 2009 (UTC)

Why are you referring to opcodes, when I explicitly showed the OISC instructions without them? The name of an OISC instruction is not the same as an opcode; e.g., subleq, sbn, etc., are the names of OISC instructions that require no opcode. Also, please do not forget that some sources (e.g., the MIS 2003 research paper) consider an OISC as an abstract computational model, independently of any RISC hardware design objective; in other words, the meaning of OISC has been extended beyond the narrow RISC category in which you view it.--r.e.s. 14:27, 21 September 2009 (UTC)

As long as the operand is tested for values (if-then) it is an opcode, regardless hidden or explicit.

As for the OISC definition, here our understandings are different. My understanding is that OISC is a one-instruction set computer, which is a computer. I do not call Turing machine or any other abstract machine a computer (that, again in my opinion, corresponds to the dictionary definition of computer). The fact that Subleq is Turing-complete if implemented on an abstract machine is a bonus, not a requirement. The requirement is that Subleq can be implemented in hardware and be able to simulate or interpret (in polynomial order) any other computer, i.e. Subleq instruction must be enough to build a computer.

If some "consider an OISC as an abstract computational model", they should call it "one-instruction set abstract computational model" or "one-instruction Turing-complete language". Otherwise they have to say, that from now on OISC is not a computer; it is a more general concept; and the letter C is present in the OISC abbreviation just for historical reasons. --Oleg 00:26, 22 September 2009 (UTC)

Can you cite a reference for your theory of "hidden opcodes"? Is the if-then in the subleq instruction a "hidden opcode"?

According to your opinion there is no such thing as an abstract computer. Countless authors differ with you about that, and regard Turing machines, Minsky machines, and other such abstract machines as examples. Physical computers are often regarded as limited implementations of these abstract computers. The latter are also often regarded as computational models (e.g., the abstract OISC discussed in the MIS 2003 paper). It matters not that you believe such authors ought to share your opinion -- the fact is, they do not.-- r.e.s. 14:26, 22 September 2009 (UTC)

No and no. I cannot give any reference to support the term "hidden opcodes". I doubt it can be formalized because there is no distinct line between bits representing opcode and bits of an operand. I referred to it in informal sense (Note, I said "you can call it an OISC"). Subleq does not have a "hidden opcode" because the instruction does not have any bits to be tested if-then.

I agree that physical computers are limited implementations of abstract machines. I just do not call an abstract machine a computer, I call it abstract machine.

The original papers describing the Ultimate RISC, all referred to physical computers, not abstract machines. --Oleg 02:53, 23 September 2009 (UTC)

I have to agree that the letter C in the OISC abbreviation can stand for computer in more general sense that a computer can be a physical computer or an abstract machine (or abstract computer), so I have to take my words that an OISC is a computer back. Allowing this, however, makes discrepancy between the words RISC, CISC, and OISC, because RISC and CISC imply narrower concept of computer. --Oleg 03:11, 23 September 2009 (UTC)

I would agree with Oleg's objection to "hidden opcodes". If an OISC's single instruction can behave differently depending on the contents of memory, then effectively the memory can contain a language with an arbitrary number of instructions ("hidden opcodes"), and the OISC's instruction becomes "step the interpreter". I think this is legitimate if rewriting the in-memory instructions is a core principle of the language (eg. to gain Turing completeness), but if not then I would consider it to be "cheating" in the same way that Unary claims to be a one-symbol language. -- Warbo 12:52, 27 April 2012 (UTC)

does an OISC have to be Turing complete?

--None1 (talk) 11:38, 24 January 2024 (UTC)