Thread: What is the absolute smallest instruction set do you need to make aworking computer?
View Single Post
  #12  
Old September 22nd 19, 05:52 PM posted to alt.comp.os.windows-10,alt.windows7.general,comp.sys.ibm.pc.hardware.chips,comp.sys.intel,alt.comp.hardware.amd.x86-64
Jeff Barnett
external usenet poster
  
Posts: 6
Default What is the absolute smallest instruction set do you need to makea working computer?
Yousuf Khan wrote on 9/22/2019 6:59 AM:
On 9/22/2019 1:47 AM, Jeff Barnett wrote:
The machine I'm trying to recall is Turing Complete. In other words it
can implement an interpreter that can "execute" any Turing machine
with any input tape - it's a theoretical machine. If you are talking
about a machine with real components, that's a horse of a different
color and quite puny in comparison. This 2 register machine, with few
instructions was all the theoretical rage some 60 or 70 years ago and
was described in many text books. I thought your original question was
fishing for what I described.

Well, I don't know anything about "Turing Complete" machines. If such
Turing machines can be run through any current general purpose computer
architecture, then this theoretical machine should be able to run it too.

The concept is not about artificial intelligence, but about general
purpose computing at its most basic level. About 2 or 3 decades ago, we
had the debate about RISC vs. CISC architectures. Without getting into
debates about which of those concepts won in the end, this is taking
that debate to the next level, and asking what is the most basic set of
instructions that can eliminate all other instructions? So they've
eliminated every other instruction, and replaced it with this one
instruction, called SUBLEQ, "Subtract Less Than or Equal To". It only
does subtractions on data, and branches only when the result is less
than or equal to zero. So this is the ultimate RISC architecture, the
OISC (One Instruction Set Computing) architecture.

The page below links to an OISC interpreter and tools.

Oleg Mazonka - Languages - SUBLEQ
http://mazonka.com/subleq/

What I described has zip to do with artificial intelligence and could
never be implemented in real circuits - the registers are of whatever
size the computation needs. It's like a TM tape can get as long as
necessary. Note that the theoretical machine had no memory other than
its two registers and a "code" store. It also worked with minimum
instructions but could do any computable task.
--
Jeff Barnett