If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below. |
|
|
|
Thread Tools | Rate Thread | Display Modes |
#1
|
|||
|
|||
What is the absolute smallest instruction set do you need to make aworking computer?
What's your guess? 100 instructions? 50 instructions? 10? Would you
believe just 1 instruction!? And that instruction is implied, you don't even need an opcode for that! And you're not going to believe what that one instruction is either! This video explains how it's possible. https://youtu.be/jRZDnetjGuo Yousuf Khan |
Ads |
#2
|
|||
|
|||
What is the absolute smallest instruction set do you need tomake a working computer?
On 2019-09-21, Yousuf Khan wrote:
What's your guess? 100 instructions? 50 instructions? 10? Would you believe just 1 instruction!? And that instruction is implied, you don't even need an opcode for that! And you're not going to believe what that one instruction is either! This video explains how it's possible. https://youtu.be/jRZDnetjGuo Interesting. In terms of commercially-successful CPUs the most minimal I've worked with was the DEC PDP-8, which had 8 instructions (3-bit opcode). However, one of those (OPR) permitted the programmer to combine several operations into one instruction cycle by setting the appropriate bits. The PDP-8 was a 12-bit word-oriented machine sold from 1965-1979. Early models used discrete transistors, the last models were CMOS microprocessors. There was also a serial model that operated on one bit at a time - slow!! No stack was employed - subroutines worked via the caller writing the return address into the first word of the called routine. Fun times! -- ----------------------------------------------------------------------------- Roger Blake (Posts from Google Groups killfiled due to excess spam.) NSA sedition and treason -- http://www.DeathToNSAthugs.com Don't talk to cops! -- http://www.DontTalkToCops.com Badges don't grant extra rights -- http://www.CopBlock.org ----------------------------------------------------------------------------- |
#3
|
|||
|
|||
What is the absolute smallest instruction set do you need to make a working computer?
On Sun, 22 Sep 2019 00:49:48 -0000 (UTC), Roger Blake wrote:
Interesting. In terms of commercially-successful CPUs the most minimal I've worked with was the DEC PDP-8, which had 8 instructions (3-bit opcode). A nand gate can implement all Boolean operations, can't it? |
#4
|
|||
|
|||
What is the absolute smallest instruction set do you need to makea working computer?
Yousuf Khan wrote on 9/21/2019 10:46 PM:
On 9/21/2019 9:21 PM, Arlen Holder wrote: On Sun, 22 Sep 2019 00:49:48 -0000 (UTC), Roger Blake wrote: Interesting. In terms of commercially-successful CPUs the most minimal I've worked with was the DEC PDP-8, which had 8 instructions (3-bit opcode). A nand gate can implement all Boolean operations, can't it? And so the answer is, the only instruction you need is a Subtract instruction! A special subtract instruction that branches only when the result is less than or equal to zero. The video explains how that works. I haven't looked at the video but (trying to remember from the 1960s) you need 2 registers and places to branch on either crossing 0. Essentially one register is the right half and the other the left half of the "tape" and you are working with 2 characters, etc., etc.. etc. -- Jeff Barnett |
#5
|
|||
|
|||
What is the absolute smallest instruction set do you need to makea working computer?
On 9/21/2019 9:21 PM, Arlen Holder wrote:
On Sun, 22 Sep 2019 00:49:48 -0000 (UTC), Roger Blake wrote: Interesting. In terms of commercially-successful CPUs the most minimal I've worked with was the DEC PDP-8, which had 8 instructions (3-bit opcode). A nand gate can implement all Boolean operations, can't it? And so the answer is, the only instruction you need is a Subtract instruction! A special subtract instruction that branches only when the result is less than or equal to zero. The video explains how that works. Yousuf Khan |
#6
|
|||
|
|||
What is the absolute smallest instruction set do you need to makea working computer?
On 9/22/2019 12:04 AM, Jeff Barnett wrote:
I haven't looked at the video but (trying to remember from the 1960s) you need 2 registers and places to branch on either crossing 0. Essentially one register is the right half and the other the left half of the "tape" and you are working with 2 characters, etc., etc.. etc. This particular computer doesn't have any registers, it works directly on memory. Now obviously in the background, the real chip might have virtual registers that it uses as a buffer area, but that's completely out of the control of the instruction set itself. |
#7
|
|||
|
|||
What is the absolute smallest instruction set do you need to makea working computer?
Yousuf Khan wrote on 9/21/2019 11:00 PM:
On 9/22/2019 12:04 AM, Jeff Barnett wrote: I haven't looked at the video but (trying to remember from the 1960s) you need 2 registers and places to branch on either crossing 0. Essentially one register is the right half and the other the left half of the "tape" and you are working with 2 characters, etc., etc.. etc. This particular computer doesn't have any registers, it works directly on memory. Now obviously in the background, the real chip might have virtual registers that it uses as a buffer area, but that's completely out of the control of the instruction set itself. 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. If you are interested in possible real machines, I believe that Dave Ferguson got a patent in the 1950s or 1960s for a machine that only had very few op code bits - 2 or 3. The meaning of those bits depended on the previous instruction executed so one had to be extraordinary clever in planning code sequences. SDS started to build a machine based on that concept though I'm not sure it was ever put on the market. Ferguson actually coded the most unbelievable hack that I ever ran into but first a word of background: in the 1950s and 1960s IBM card readers could either read a card by columns or by rows. There were cards that you could read to boot various computers such as a 709, 7094, 1401, etc. But note that you needed a different card if the reader was set in row or column. The operators got it wrong all the time and were quite frustrated. Ferguson developed a card punch pattern that would boot some specific machine no matter how the reader was set. To understand the degree of difficulty, booting meant reading some instructions from a mag tape some of which overlapped the instructions brought in from the card reader. There were timing considerations too. That last paragraph has absolutely nothing to do with this thread's theme but will I was remembering it, I thought I'd share the story. -- Jeff Barnett |
#8
|
|||
|
|||
What is the absolute smallest instruction set do you need to make a working computer?
Yousuf Khan wrote:
What's your guess? 100 instructions? 50 instructions? 10? Would you believe just 1 instruction!? And that instruction is implied, you don't even need an opcode for that! And you're not going to believe what that one instruction is either! This video explains how it's possible. https://youtu.be/jRZDnetjGuo https://en.wikipedia.org/wiki/One_in...n_set_computer Concept proposed back in 1956. It is a computational model used for teaching. It would be too slow for physical implementation. That it can be done doesn't mean anyone cares. |
#9
|
|||
|
|||
What is the absolute smallest instruction set do you need to makea working computer?
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/ |
#10
|
|||
|
|||
What is the absolute smallest instruction set do you need to makea working computer?
On 9/22/2019 2:26 AM, VanguardLH wrote:
https://en.wikipedia.org/wiki/One_in...n_set_computer Concept proposed back in 1956. It is a computational model used for teaching. It would be too slow for physical implementation. That it can be done doesn't mean anyone cares. Maybe, maybe not. It may not have been anything more than a curiosity in the 50's. Back then memory was very slow, and the caching technologies that have evolved over the decades was not available yet back then. So back then you had to make sure you explicitly put everything into registers. But these days, with your typical x86 machine being really a RISC processor emulating a CISC processor, and they've come up with so many automatic caching techniques that registers are no longer needed, and you can really work directly on memory without any performance penalties nowadays. Yousuf Khan |
#11
|
|||
|
|||
What is the absolute smallest instruction set do you need to make a working computer?
VanguardLH on Sun, 22 Sep 2019 01:26:19 -0500 typed in
alt.windows7.general the following: Yousuf Khan wrote: What's your guess? 100 instructions? 50 instructions? 10? Would you believe just 1 instruction!? And that instruction is implied, you don't even need an opcode for that! And you're not going to believe what that one instruction is either! This video explains how it's possible. https://youtu.be/jRZDnetjGuo https://en.wikipedia.org/wiki/One_in...n_set_computer Concept proposed back in 1956. It is a computational model used for teaching. It would be too slow for physical implementation. That it can be done doesn't mean anyone cares. Martin Gardner had an article about a "theoretical" 'primitive computer using pulleys and ropes in place of transistors (or tubes). In theory it would work, in practice there would be too much imprecision from the slack/stretch in the ropes for it to work. -- pyotr filipivich Next month's Panel: Graft - Boon or blessing? |
#12
|
|||
|
|||
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 |
#13
|
|||
|
|||
What is the absolute smallest instruction set do you need to make a working computer?
In message , Roger Blake
writes: On 2019-09-21, Yousuf Khan wrote: What's your guess? 100 instructions? 50 instructions? 10? Would you believe just 1 instruction!? And that instruction is implied, you don't even need an opcode for that! And you're not going to believe what that one instruction is either! This video explains how it's possible. https://youtu.be/jRZDnetjGuo Interesting. In terms of commercially-successful CPUs the most minimal I've worked with was the DEC PDP-8, which had 8 instructions (3-bit opcode). However, one of those (OPR) permitted the programmer to combine several operations into one instruction cycle by setting the appropriate bits. The first computer I learnt on had 8 instructions (3 bit opcode); it was a "computer" by Mr. Parr's definition of having a conditional jump among its op.s [as opposed to a programmable calculator - common at the time, 1970s, which didn't], where the decision was based on the result of (in this case) previous instructions. (The one-opcode answer given above qualifies, as it is subtract-and-jump-if.) The PDP-8 was a 12-bit word-oriented machine sold from 1965-1979. Early models used discrete transistors, the last models were CMOS microprocessors. There was also a serial model that operated on one bit at a time - slow!! No stack was employed - subroutines worked via the caller writing the return address into the first word of the called routine. Fun times! BRENDA (BaRnardian Electronic Numerical Demonstration Apparatus) was a 7-bit machine (16 memory locations); it _was_ a serial machine, also operating in ones complement, instead of the now-universal twos complement. It looked like everybody's idea of a computer then: a wall of filament bulbs (one for each bit in each memory location, plus the other registers such as accumulator, prog. counter, etcetera). No subroutines. It was the shape and size of the luggage space of a Hillman Imp (British car of the time), as that's where HCP built it. It was modular, using transistors - I believe he actually got the fourth form [tenth grade I think] one year to make the modules. I can still remember the opcodes: Z clear accumulator A address add the contents of address to accumulator S address subtract the contents of address from accumulator T address transfer accumulator to address I address stop for input (which went into address) J address jump to address+1 K address conditional jump (if negative IIRR) to address+1 E stop Note that Z and E - 000 and 111 - had no parameter; a wily programmer used those to store constants. Mr. Parr produced a booklet, including some exercises; they started with simple things like 3a+b (Z, A15, A15, A15, A14, E) and running totals (I15, A15, J15), but leading up to the 50th example which was IIRR calculate the highest common factor of two numbers (which I never managed). http://forum.6502.org/download/file....7446aed16b6825 d2bb7c5999023c http://forum.6502.org/viewtopic.php?f=3&t=2333 -- J. P. Gilliver. UMRA: 1960/1985 MB++G()AL-IS-Ch++(p)Ar@T+H+Sh0!:`)DNAf Q. How much is 2 + 2? A. Thank you so much for asking your question. Are you still having this problem? I'll be delighted to help you. Please restate the problem twice and include your Windows version along with all error logs. - Mayayana in alt.windows7.general, 2018-11-1 |
#14
|
|||
|
|||
What is the absolute smallest instruction set do you need to make a working computer?
In message , pyotr
filipivich writes: [] Martin Gardner had an article about a "theoretical" 'primitive computer using pulleys and ropes in place of transistors (or tubes). In theory it would work, in practice there would be too much imprecision from the slack/stretch in the ropes for it to work. Babbage (arguably only with modern materials) made a mechanical machine work. There are the mechanical equivalents of squaring circuits, thresholds etcetera. Electronic computers could be made to work with three or four voltage levels rather than two - it just reduces the noise margin, which puts limits on speed and distances. Presumably a pulleys/ropes machine could be made, as long as there were thresholds, and the mechanical equivalents of amplifiers (a rope-operated clutch perhaps? I'm not really a mechanical engineer). -- J. P. Gilliver. UMRA: 1960/1985 MB++G()AL-IS-Ch++(p)Ar@T+H+Sh0!:`)DNAf "Flobalob" actually means "Flowerpot" in Oddle-Poddle. |
#15
|
|||
|
|||
What is the absolute smallest instruction set do you need to make a working computer?
"J. P. Gilliver (John)" on Sun, 22 Sep 2019
21:15:45 +0100 typed in alt.windows7.general the following: In message , pyotr filipivich writes: [] Martin Gardner had an article about a "theoretical" 'primitive computer using pulleys and ropes in place of transistors (or tubes). In theory it would work, in practice there would be too much imprecision from the slack/stretch in the ropes for it to work. Babbage (arguably only with modern materials) made a mechanical machine work. There are the mechanical equivalents of squaring circuits, thresholds etcetera. Electronic computers could be made to work with three or four voltage levels rather than two - it just reduces the noise margin, which puts limits on speed and distances. Presumably a pulleys/ropes machine could be made, as long as there were thresholds, and the mechanical equivalents of amplifiers (a rope-operated clutch perhaps? I'm not really a mechanical engineer). It is funny in a way. Garden was reporting a supposed "discovery" of a "computer" discovered on a south pacific island. Yes, one could probably be made to work. Wintergatan - Marble Machine has made what was originally a CGI video into a working machine. https://www.youtube.com/watch?v=IvUU8joBb1Q A fascinating study in its own right. -- pyotr filipivich Next month's Panel: Graft - Boon or blessing? |
|
Thread Tools | |
Display Modes | Rate This Thread |
|
|