home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / arch / 10677 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  1.4 KB
  1. Path: sparky!uunet!ferkel.ucsb.edu!taco!rock!stanford.edu!agate!doc.ic.ac.uk!uknet!dsbc!jura!pete
  2. From: pete@jura.uucp (Pete Bevin)
  3. Newsgroups: comp.arch
  4. Subject: Re: MINIMUM instruction set
  5. Message-ID: <pete.180021.12Nov92@sst.icl.co.uk>
  6. Date: 12 Nov 92 18:25:27 GMT
  7. References: <1992Nov10.235849.19192@fcom.cc.utah.edu>
  8. Sender: news@dsbc.icl.co.uk
  9. Reply-To: pete@sst.icl.co.uk (Pete Bevin)
  10. Lines: 29
  11. Nntp-Posting-Host: sst.icl.co.uk
  12.  
  13. Val Kartchner writes:
  14. > I've heard that it is possible to implement all programming languages with
  15. > seven instructions.  (Possible does not mean practicle.)  Does anyone know
  16. > what these instructions are?  Is it possible to do all operations in less
  17. > than seven instructions?
  18.  
  19. You can get away with four instructions in the following (rather
  20. inefficient) Turing-Machine-equivalent architecture.  Allow yourself a
  21. number of registers, each of which can hold large enough numbers for
  22. what you want to do.  Then, you only need:
  23.  
  24.     Z(register):        Zero a register
  25.     S(register):        Increment a register (`S' for `successor')
  26.     T(r1, r2):          Transfer value from r1 to r2
  27.     J(r1, r2, address): Jump to address if r1 and r2 hold the same
  28.                 value.
  29.  
  30. In fact, you can get away without the T instruction, because T(r1, r2)
  31. is the same as:
  32.  
  33.         Z(r2)
  34.     loop:    J(r1, r2, finished)
  35.         I(r2)
  36.         J(r1, r1, loop)
  37.  
  38. You wouldn't want to program it, but I guess it's fairly easy to reason
  39. mathematically about it.
  40.  
  41. Pete.
  42.