Simplest general purpose CPU?

[nibble4bits]

There is a class and a student states that any general purpose CPU can emulate another, assuming there's enough resources. In other words if you have enough RAM and instruction cycles/patience, your old 486 desktop can run software written for your shiny new machine. The instructor then challenges the student to describe the simplest computer they can think of capable of emulating a 486 CPU and for extra credit, using as many mechanical components as possible except maybe for the RAM.

In practice, it's easy to add memory page swapping on a real system using a memory mapped paging unit. This is how something with a 16-bit address bus such as the 6502 can recognize 128KB of RAM with the Apple II's expansion card. This means that even if you only implement a 8-bit address bus, you can still cheat your way to (slowly) emulating a 32-bit bus. This places the burden of mapping out that memory to what is equivalent to an external register and multiplexing logic. Again, this is allowed in the problem. The memory attached to the CPU, including the stack is not counted toward's the complexity. The registers used internally however are.

What is the simplest CPU instruction set the student could define? Less electronics are better. I can think of some very imaginative ways to avoid using a lot of electronic parts by using mechanical parts in their place.

I thought I'd pose this puzzle because I'm crazy enough to actually think of solutions to problems like this one. I think a 2-bit instruction set with an 8-bit program counter and 256-byte stack is possible but annoying. There's some interesting processors you could design if you're into this esoteric sort of thing. There are some amazing hacks to get branching even though the instruction set has no such opcode. It is prefered that the instruction set be of fixed-length, bits wise.




If you used a motor as your clock source, you can create something like a cam, but with wiring set up to control your fetch logic, register preload, etc. This saves you some electronic gates by moving them off the board and into your mechanics. Of course this gives a new meaning to the word 'crank' on this forum if you actually built something like this. :P
The stack can allow wraparound so that your stack<->register transfers don't have to be balanced. You'll see what I mean when you actually try to come up with a 4-opcode set using a seperate data and instruction bus. A stack is almost mandatory to reduce the size of the instruction set unless you want variable length opcodes which make the logic a lot more complicated.
The NAND gate is in theory capable of implementing any other logic device if you have enough of them.
To invert a binary value, NAND it with all 1s. To set a binary value to all 1s, NAND it with it's inverse. To set a value to zero, first make it all ones, then invert it. There are goofy ways to get arbitary values. I'll leave this up to your imagination.
4 NAND gates is able to implement an XOR gate. A binary adder with carry is just an AND and XOR gate.

[retina]

I thought the Busy Beaver would be the simplest Turing complete machine.

[cheesehead]

A very wide binary abacus would do.

[xilman]

I suggest you check out the crazy ideas of a guy named Charles Babbage. He has a design which doesn't require any electronics.


Paul

[cheesehead]

At the city science fair my high school senior year, first place in the math division went to a wooden four-bit adder that could be hand-cranked through its operations. Very clean-cut, clear presentation.

[nibble4bits]

LOL Cheesehead has the idea. Yes, there were mechanical computers long before vacuum tubes, but they're almost all very complicated. An abacus is the least. ;)

Does anyone have any circuit diagrams to implement a busy beaver CPU (not including infinite tape memory). This can't be too hard but it is likely very rarely constructed. I see at the end of that busy beaver article a nice set of tables.

The little man is a very simple introduction to CPUs and seems like it wouldn't be too hard to implement in hardware. I wrote an emulator for it in class a couple years back. It took about 1-2 pages of source code, so the hardware is likely very simple.

It's nice to see that I got your interest. Now tell me what you would create, as a student. The design that I have uses two tapes in order to simplify addressing. I've attached the current notes on it. It is not complete but the specifications are still useful for giving you ideas.

_______________________
If the computer is base 3, what is the smallest number of gates that is needed in order to add two 2-digit base 3 numbers with a 3 digit result in one clock cycle? 10 cycles? 100? Is it even possible to determine? Is defining the optimium implementation the same difficulty as finding a lower bound on gate count?

For a list of ternary (aka trinary) gates:
http://en.wikipedia.org/wiki/Ternary_logic
http://www.trinary.cc/

That part about the USSR having ternary computers is pretty interesting.


::

Hmm I should make a thread about CPU design in the programming section later, after this problem is exhausted. (No pun intended)

[xilman]

Originally Posted by nibble4bits

I think a 2-bit instruction set with an 8-bit program counter and 256-byte stack is possible but annoying.

Note that a machine with the single instruction Decrement_and_Skip_if_Zero has been shown to be Turing-complete. As there is only one instruction, it may as well be the default and there is no need for any bits in the instruction set!

Paul

[davieddy]

http://technology.newscientist.com/a...ent-25000.html

[nibble4bits]

Oooooooh, nice!

I'll have to check that one out. Thank you for the news link. There reason I started this thread was to see what solutions people would think of, and how varied they can be.

A better link (Dang javascript!):
http://blog.wolfram.com/index.php?ye...hine-is-proved

Here's a small quote from his artical.

One might think that computational ability would be a more gradual phenomenon: that as one increased the complexity of the rules for a system, the system would gradually show greater computational ability.

But PCE says that’s not how it works. It says that above a very low threshold, all systems will be exactly equivalent in their computational capabilities.

Wolfram, 2008.

This has some interesting implications for us as well as any type of computer. I suggest you read his web log.