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