home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3193 < prev    next >
Encoding:
Internet Message Format  |  1992-08-16  |  1.4 KB
  1. Xref: sparky comp.ai.neural-nets:3193 comp.ai:3095 comp.compression:3014 comp.theory:1764
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,comp.theory
  3. Path: sparky!uunet!s5!sethb
  4. From: sethb@fid.morgan.com (Seth Breidbart)
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <1992Aug14.170728.14162@fid.morgan.com>
  7. Organization: Morgan Stanley & Co., New York, NY
  8. References: <arms.713549466@spedden> <1992Aug12.173546.3298@access.usask.ca> <1992Aug13.033835.4492@linus.mitre.org>
  9. Date: Fri, 14 Aug 1992 17:07:28 GMT
  10. Lines: 17
  11.  
  12. In article <1992Aug13.033835.4492@linus.mitre.org>
  13. crawford@church.mitre.org (Randy Crawford) writes:
  14.  
  15. >That begs a question.  Are all universal turing machines of indeterminate 
  16. >power?  Or must they be considered turing machines because they _may_ be 
  17. >configured as turing machines, even though they also may not be so configured?
  18. >If they _are_ still turing machines, then once again, why does computibility 
  19. >theory become uninteresting once a turing machine is passed instructions?
  20.  
  21. A Universal Turing Machine is a Turing Machine that, on input <i,j>,
  22. returns the same result as Turing Machine i does on input j.
  23. Therefore, Universal Turing Machines are a subset of Turing Machines.
  24. There can be Universal Machines that start out more powerful than
  25. Turing Machines but this particular one is programmed to act like a
  26. Universal Turing Machine.
  27.  
  28. Seth        sethb@fid.morgan.com
  29.