• Please review our updated Terms and Rules here
  • Exhibitor application for VCF West 2022 is now open! If you are interested in exhibiting, please fill out the form here.

Fewest computer Instructions need to make a computer..

Marty

Veteran Member
Joined
Jul 26, 2009
Messages
3,141
Location
Boulder , Colorado USA
Hi All;

I have been reading a book.. And in it He mentions about Fewest instructions needed to program a computer, And so I am asking what Everyone Else would think would Qualify for this List of Instructions needed..

I Quote from the Book, "Computing in the Middle Ages" by Severo M. Ornstein.. (Page 5)
" After I'd mastered the EDSAC's bootstrap program, Howie lent me a manual describing Whirlwind and how to program it.
Under his tutelage I worked my way through the manual and wrote out the suggested exercises. Of course these programs were never going to be executed since Whirlwind was hundreds of miles away in Cambridge, Massachusetts, and remote computing still lay far in the future. Besides, Whirlwind had far more important things to do. Mine were just paper exercises designed to teach one how to write programs.
After I became somewhat proficient, Howie made the startling announcement that most of the instructions I'd been using were actually unnecessary and were provided only to save memory and make programs run faster. He explained that there were, in fact only a handful of truly basic instructions and that all the others could be emulated (i.e., the machine could be made to perform precisely the same function) by programs made up of only this basic set.
I tested the validity of this claim by programming one or two of the more complicated instructions using the basic set, and once again I was stunned: the bloody thing seemed to consist almost of entirely sheer ingenuity, balanced atop the merest pinpoint of material reality. "

So for my starting list I can think of Add, ( I know that there was a computer that didn't have an Add instruction, but a Subtract Instruction instead).. But, I will for this discussion lump them both in as the same basic Instruction..
So, I have Add, Load and Store (I will put these as basic I/O Instructions), a Jump or Conditional Jump Instruction and possibly a Logic Nand Instruction.. Since other basic Logic can be combined and made from a Nand..

So, with that what would You all take away from my List and what Would You Add to my List ?? Feel free to change add or subtract from what I have put down..

THANK YOU Marty
 

Marty

Veteran Member
Joined
Jul 26, 2009
Messages
3,141
Location
Boulder , Colorado USA
Hi All;

I spoke to a friend of mine and He came up with the following..
He said that the following would need to be Included in the Mix, for the unit..
Direct and Indirect Addressing, take out the Nand Logic, and put in it's place And, Or and Xor ..
So, it would have Add (Subtract), Mov, And, Xor, (Or, could be included for ease of use or not), Jump and Conditional Jump, Call/Return, and Direct Addressing, Indirect Addressing (which could give You Stack Capability software or Hardware or even a Hardware Stack) and Immediate.. (i.e., putting a value into a given Register)..
What I am looking for is given the Whirlwind or EDSAC or even a PDP 8 or a PDP 11, Instruction Set, what would be taken out of the official Instruction Set and what is on the list above that would remain..
Not a turing machine type of thing and not a machine that it would take gobs of memory to Implement something simple, like word processing..
Smp I like Your Link.. Yes, of this type..

THANK YOU Marty
 

g4ugm

Veteran Member
Joined
Feb 22, 2011
Messages
2,736
Location
NorthWest England (East Pondia)
So for my starting list I can think of Add, ( I know that there was a computer that didn't have an Add instruction, but a Subtract Instruction instead).. But, I will for this discussion lump them both in as the same basic Instruction..
So, I have Add, Load and Store (I will put these as basic I/O Instructions), a Jump or Conditional Jump Instruction and possibly a Logic Nand Instruction.. Since other basic Logic can be combined and made from a Nand..

1) You can't lump add and subtract together. The logic for a subtractor is rather different to that of an of an adder. The SSEM which was the first electronic (i.e. Von Neuman) computer doesn't have an add instruction, it has load complement which negates numbers and a subtract. You don't need an unconditional jump, just make sure you set the condition appropriately.

2) the key instruction for "Turing Complete" is the "conditional jump". The SSEM doesn't do this in the normal. It has a "test" which skips an instruction, usually a jump...

3) It does not have an add instruction but it does have an adder which is needed to increment the program counter....

So whilst you can have many options I would say if you have an accumulator, Load, Store, subtract, clear & jump.
 

Marty

Veteran Member
Joined
Jul 26, 2009
Messages
3,141
Location
Boulder , Colorado USA
Hi All;

Dave, Thank You for the thoughtful responses..
"" So whilst you can have many options I would say if you have an accumulator, Load, Store, subtract, clear & jump. ""
I would say add this to the list of options..
On the Adder, Subtractor Issue, If I am correct taking the ALU Adder and the Xor, I could have either an Adder or a Subtractor circuit, and so I could Lump them together, and I know that creating one, sometimes made it extremely hard to do the other, and at other times it would be easy to do.. Depending on the underlaying logic design..
Who knows we may end up with about half a dozen possibilities to choose from and to Implement on Breadboard, just to see what/which one wins as far as what it could do.. Or making them in Logisim and doing a comparison..

THANK YOU Marty
 

Marty

Veteran Member
Joined
Jul 26, 2009
Messages
3,141
Location
Boulder , Colorado USA
Hi All;

Chuck, Thank You for Your Inclusion.. OK !! And Cruff, for the origional Inclusion..
I think I will have to Read this more than once to understand it, and how it fits in with the rest.. Accumulator/Register type of machine..
But, I'LL Accept it and Include it in the List..

THANK YOU Marty
 
Last edited:

Chuck(G)

25k Member
Joined
Jan 11, 2007
Messages
39,125
Location
Pacific Northwest, USA
There were plenty of accumulator-less machines. In some respects they can be more flexible than the other kind.

Consider the lowly IBM 1620, a popular small computer of the late 50s, early 60s. No accumulator; not even an ALU, although it did have an incrementer/decrementer; arithmetic was done by table lookup in memory. No fixed word size either--numbers could be as long as you wanted to make them. Decimal--and no boolean operations. Addressing modes? Well, there were instructions that could take up to a 5 digit constant as an operand; otherwise you performed instruction modification.

Yet, it supported FORTRAN and an operating system and was notable enough to be despised by Edgars Dijkstra. It was pretty friendly as a first computer for many a student.

In a way, it's sad that current CPU implementations have driven older ones into oblivion.
 

g4ugm

Veteran Member
Joined
Feb 22, 2011
Messages
2,736
Location
NorthWest England (East Pondia)
Why on earth is an accumulator even necessary? There have been many machines with no accumulators or explicit registers.

The answer remains "one". There are plenty of emulators for OISC. Here's a 1988 paper showing how other instructions can be synthesized.

You are right Chuck, in fact you don't even need a program counter. Some machines actually make every instruction a jump and embed the address of the next instruction into the instruction meaning they don't even need a program counter. However they may still need a register to hold that address until its needed?

In terms of a physical implementation though, i think that eliminating the accumulator may actually make the implementation logic more complex, as in order to combine two memory locations you need to read them both. Now with a separate accumulator it easy to arrange for the accumulator and a memory location to be read at the same time and combined in one operation. With most store technologies you can only read one unit at once, so you may need to actually implement a "register", even though you don't call it a register, to store data while working on it.
 

g4ugm

Veteran Member
Joined
Feb 22, 2011
Messages
2,736
Location
NorthWest England (East Pondia)
It was pretty friendly as a first computer for many a student.

I must admit I never found the 1620 with Fortran IID very friendly, but then I was a young hot-headed pupil who had to put his cards in the Mail (there only was Snail Mail then) only to get a failed listing back because I had multiplied a Float by "2" rather than "2.0" , yea, happy days.
 

g4ugm

Veteran Member
Joined
Feb 22, 2011
Messages
2,736
Location
NorthWest England (East Pondia)
Hi All;

Dave, Thank You for the thoughtful responses..
"" So whilst you can have many options I would say if you have an accumulator, Load, Store, subtract, clear & jump. ""
I would say add this to the list of options..
On the Adder, Subtractor Issue, If I am correct taking the ALU Adder and the Xor, I could have either an Adder or a Subtractor circuit, and so I could Lump them together, and I know that creating one, sometimes made it extremely hard to do the other, and at other times it would be easy to do.. Depending on the underlaying logic design..
Who knows we may end up with about half a dozen possibilities to choose from and to Implement on Breadboard, just to see what/which one wins as far as what it could do.. Or making them in Logisim and doing a comparison..

THANK YOU Marty

Well actually the SSEM/Baby does not have any concept of an Digital ALU. The adder and subtractor both use "Kirchoff" adders which are, I believe in essence Analogue circuits. I understand that they allow an Adder (or subtractor) to be built with fewer Valves/Tubes than a logic gate based adder. The Circuits of the SSEM replica are here:-

http://www.cs.man.ac.uk/CCS/SSEM/volunteers/controladder.html

if you are interested...
 

Marty

Veteran Member
Joined
Jul 26, 2009
Messages
3,141
Location
Boulder , Colorado USA
Hi All;

G4ugm, Thank You for the Link, Yes I am Interested, I had never before seen any Diagrams for the SSEM/baby.. Like the EDSAC all I had seen was the Logic Diagrams, and at one time wanted to build it in TTL as well, I haven't decided whether to re-add it to my list of TTL builds..

I have access to the Logic Diagrams for the EDSAC to follow and it has a Serial Adder, so in essence I could make a TTL version of it..
It is on my list of computers to make in TTL, I just at present Don't have the Sockets and the wire..
So, not in any particular order, I want to build the PDP 8i Microcode, which is in progress once I get the Digital Group thing done..
And then want to do a PDP 11/xx, I haven't decided which one, the EDSAC as mentioned above and the 8080 Microprocessor..
If I have enough money for wire and sockets and live long enough..
My Origional goal was to build an 8080 TTL equivalent, and all of the rest of these are to help me Understand what would be needed to do that, circuit and logic wise.. I have also considered doing the 4004 and the 8008, to help me Understand what would be needed..
I had before started to build the 8080 Equivalent, but, I used the wrong register Implementation, I now know more of what it would need to do so.. And the Board got stripped and has been used for a few other projects since then.. And I am now in a better position to do so, now, again..

THANK YOU Marty
 
Last edited:

g4ugm

Veteran Member
Joined
Feb 22, 2011
Messages
2,736
Location
NorthWest England (East Pondia)
No probs, I built an SSEM in FPGA but its a cheat as it does parallel arithmetic, but the actual execution rate is the same as the Manchester replica. They actually have a TTL (or perhaps CMOS) implementation in the Museum. I found I learnt a lot about how the machine works while doing this. My next one will be a Pegasus.
 

ClassicHasClass

Veteran Member
Joined
Mar 22, 2013
Messages
1,583
Location
Sunny So Cal
SUBLEQ machines are probably the most practical of the OISCs. There's even a (basic but functional) C compiler for them: http://mazonka.com/subleq/hsq.html

I wrote SUBLEQ machine implementations in (32-bit integer) PowerPC and (16-bit integer) 6502 assembly. These run substantially faster than C versions. There's even a SUBLEQ machine in SUBLEQ, which is great for virtualization.

SUBLEQ's main drawback is its appallingly low code density, since even simple procedural instructions that are not expected to execute out of sequence must still encode the next instruction location, and every instruction is a full three machine words.
 

Chuck(G)

25k Member
Joined
Jan 11, 2007
Messages
39,125
Location
Pacific Northwest, USA
I must admit I never found the 1620 with Fortran IID very friendly, but then I was a young hot-headed pupil who had to put his cards in the Mail (there only was Snail Mail then) only to get a failed listing back because I had multiplied a Float by "2" rather than "2.0" , yea, happy days.

The joy of the 1620 is that the typical course of instruction was first learning the machine code and writing some simple programs in it (so-called "Absolute" coding system). The 1620 was very friendly for this--the I/O is very simple and there were console lights to tell you what was happening. A "Hello world" program would easily fit on a single card.

Then came SPS - the assembly language of the 1620. No more keeping track of address references, etc.

Finally, FORTRAN--you had II-D, which meant that you also had a 1311 disk drive on the machine and could run Monitor II-D--and you also had the indirect addressing feature.
 

g4ugm

Veteran Member
Joined
Feb 22, 2011
Messages
2,736
Location
NorthWest England (East Pondia)
Sadly I never got to program the machine in assembler. Before being allowed to use the 1620 we hade to write a machine code program on "DENICE" our schools computer that had been built by Hector Parr. I guess this brings us back On-Topic as this was a minimal computer of similar capacity to Baby. It was loosely based on the Wireless World Computer but with a reduced instruction set. It did have a lamp for each memory location. You entered data by selecting a word and then filling in serially with a pair of buttons, one of "0" and one for a "1"..

I hope to get some more info about it from Hector. Docs for the Wireless World Computer are here:-

http://www.smrcc.org.uk/members/g4ugm/Manuals/wirelessworldcomputer.pdf
 
Last edited:
Top