20080603, 22:05  #1 
Nov 2005
181 Posts 
Simplest general purpose CPU?
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 16bit 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 8bit address bus, you can still cheat your way to (slowly) emulating a 32bit 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 2bit instruction set with an 8bit program counter and 256byte 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 fixedlength, 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 4opcode 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. Last fiddled with by nibble4bits on 20080603 at 22:06 
20080604, 02:11  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
3^{2}·647 Posts 
I thought the Busy Beaver would be the simplest Turing complete machine.

20080604, 05:12  #3 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×599 Posts 
A very wide binary abacus would do.

20080604, 07:05  #4 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10131_{10} Posts 
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 
20080604, 11:16  #5 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×599 Posts 
At the city science fair my high school senior year, first place in the math division went to a wooden fourbit adder that could be handcranked through its operations. Very cleancut, clear presentation.
Last fiddled with by cheesehead on 20080604 at 11:32 
20080604, 14:17  #6 
Nov 2005
181_{10} Posts 
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 12 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 2digit 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) Last fiddled with by nibble4bits on 20080604 at 15:03 
20080604, 17:04  #7  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·11·307 Posts 
Quote:
Paul 

20080604, 17:16  #8 
"Lucan"
Dec 2006
England
6,451 Posts 

20080605, 11:32  #9  
Nov 2005
181 Posts 
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...hineisproved Here's a small quote from his artical. Quote:
Last fiddled with by nibble4bits on 20080605 at 11:57 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Purpose Built rig?  pool party  GPU Computing  37  20170601 04:16 
What is the purpose of these these forums? Who is welcome?  only_human  Soap Box  78  20120621 13:12 
What about general purpose sieving of k*b^n+/1?  jasong  GPU Computing  1  20120403 10:52 
Simplest universal Turing machine  davieddy  Science & Technology  4  20071126 04:59 
Purpose of p1 factoring  drew  Marin's Mersennearies  2  20050629 15:00 