mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-06-03, 22:05   #1
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

2×7×13 Posts
Default 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 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.

Last fiddled with by nibble4bits on 2008-06-03 at 22:06
nibble4bits is offline   Reply With Quote
Old 2008-06-04, 02:11   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10110000000102 Posts
Default

I thought the Busy Beaver would be the simplest Turing complete machine.
retina is online now   Reply With Quote
Old 2008-06-04, 05:12   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

A very wide binary abacus would do.
cheesehead is offline   Reply With Quote
Old 2008-06-04, 07:05   #4
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

32·11·103 Posts
Default

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
xilman is offline   Reply With Quote
Old 2008-06-04, 11:16   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

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.

Last fiddled with by cheesehead on 2008-06-04 at 11:32
cheesehead is offline   Reply With Quote
Old 2008-06-04, 14:17   #6
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

2668 Posts
Default

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)
Attached Files
File Type: zip A really simple CPU.zip (1.3 KB, 127 views)

Last fiddled with by nibble4bits on 2008-06-04 at 15:03
nibble4bits is offline   Reply With Quote
Old 2008-06-04, 17:04   #7
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

100111110101012 Posts
Default

Quote:
Originally Posted by nibble4bits View Post
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
xilman is offline   Reply With Quote
Old 2008-06-04, 17:16   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

647410 Posts
Default

http://technology.newscientist.com/a...ent-25000.html
davieddy is offline   Reply With Quote
Old 2008-06-05, 11:32   #9
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

2·7·13 Posts
Default

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.
Quote:
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.

Last fiddled with by nibble4bits on 2008-06-05 at 11:57
nibble4bits is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Purpose Built rig? pool party GPU Computing 37 2017-06-01 04:16
What is the purpose of these these forums? Who is welcome? only_human Soap Box 78 2012-06-21 13:12
What about general purpose sieving of k*b^n+/-1? jasong GPU Computing 1 2012-04-03 10:52
Simplest universal Turing machine davieddy Science & Technology 4 2007-11-26 04:59
Purpose of p-1 factoring drew Marin's Mersenne-aries 2 2005-06-29 15:00

All times are UTC. The time now is 14:45.

Thu Aug 13 14:45:31 UTC 2020 up 11:21, 1 user, load averages: 1.24, 1.32, 1.40

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.