home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3167 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  2.8 KB
  1. Xref: sparky comp.ai.neural-nets:3167 comp.ai:3068 comp.compression:2991 comp.theory:1748
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,comp.theory
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!mips!think.com!linus!linus.mitre.org!church.mitre.org!crawford
  4. From: crawford@church.mitre.org (Randy Crawford)
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <1992Aug13.033835.4492@linus.mitre.org>
  7. Sender: news@linus.mitre.org (News Service)
  8. Nntp-Posting-Host: church.mitre.org
  9. Organization: The MITRE Corporation, McLean, VA
  10. References: <arms.713549466@spedden> <1992Aug12.173546.3298@access.usask.ca>
  11. Date: Thu, 13 Aug 1992 03:38:35 GMT
  12. Lines: 40
  13.  
  14. In article <1992Aug12.173546.3298@access.usask.ca> choy@skorpio.usask.ca (I am a terminator.) writes:
  15. >In article <arms.713549466@spedden>, arms@cs.UAlberta.CA (Bill Armstrong) writes:
  16. >|> The trouble is that all you need to define any function is a
  17. >|> (complete) table of input-output pairs.  If you allow this table as
  18. >|> (part of) the "instruction set", all of computability theory becomes
  19. >|> uninteresting.  So yes, normally algorithms have to be finite.
  20. >
  21. > Why would computability theory become uninteresting?
  22.  
  23. Because any machine may be made arbitrarily powerful (that is, of less or equal
  24. power to the original machine) by passing it more or less complex input (instr-
  25. uctions).  In evaluating the machine as an interpreter of the instructions,
  26. you are measuring the complexity of the input which the modified machine will
  27. recognize, and not the complexity of the machine itself.  The arguments will
  28. direct the interpreting machine to behave like a different machine.  Therefore 
  29. stack machines may become finite-state machines, and turing machines may become
  30. _any_ kind of machine.
  31.  
  32. This is not so different from the undecidability problem.  If you pass arguments
  33. into a machine which direct the machine to act like a different machine, not
  34. only can you not decide whether the original machine terminates for all input, 
  35. but the new machine no longer behaves with the same level of complexity or
  36. power that it did before the instructions were introduced.
  37.  
  38. That begs a question.  Are all universal turing machines of indeterminate 
  39. power?  Or must they be considered turing machines because they _may_ be 
  40. configured as turing machines, even though they also may not be so configured?
  41. If they _are_ still turing machines, then once again, why does computibility 
  42. theory become uninteresting once a turing machine is passed instructions?
  43.  
  44. (Do I detect a bit of circular reasoning here...)
  45.  
  46.  
  47. Randy
  48. crawford@mitre.org
  49. -- 
  50.  
  51. | Randy Crawford        crawford@mitre.org        The MITRE Corporation
  52. |                                                 7925 Colshire Dr., MS Z421
  53. | N=1 -> P=NP           703 883-7940              McLean, VA  22102
  54.