home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / physics / 14419 < prev    next >
Encoding:
Text File  |  1992-09-10  |  1.6 KB  |  34 lines
  1. Newsgroups: sci.physics
  2. Path: sparky!uunet!cis.ohio-state.edu!news.sei.cmu.edu!firth
  3. From: firth@sei.cmu.edu (Robert Firth)
  4. Subject: Re: Computability of the universe
  5. Message-ID: <1992Sep10.183603.2357@sei.cmu.edu>
  6. Organization: Software Engineering Institute
  7. References: <1992Sep10.021939.10087@murdoch.acc.Virginia.EDU> <1992Sep10.131437.15148@sei.cmu.edu> <rwallace.716144999@unix1.tcd.ie>
  8. Date: Thu, 10 Sep 1992 18:36:03 GMT
  9. Lines: 23
  10.  
  11. In article <rwallace.716144999@unix1.tcd.ie> rwallace@unix1.tcd.ie (russell wallace) writes:
  12.  
  13. >Not so. A Turing machine can perform any feasible computation (the
  14. >Church-Turing thesis).
  15.  
  16. Yes, I know the thesis.  The argument is circular, because it defines
  17. "feasible" to mean "capable of being computed by a <machine equivalent
  18. to> a Turing machine".  Unfortunately, a true random number is not
  19. one of the things so computable, though it can of course be computed
  20. using one of several flavours of the universal quantum computer.
  21.  
  22. The analogy with Greek geometry is exact.  They defined "constuctible"
  23. to mean "constructible with only straight edge and compasses", whence
  24. it follows trivially that straight edge and compasses can construct
  25. all "constructible" figures.  Unfortunately, the trisector of an angle
  26. is not one of those "constructible" figures, though it can of course
  27. be constructed using the method of Archimedes.
  28.  
  29. The argument that a Turing machine can produce an arbitrarily close
  30. approximation to a true random sequence is just as bogus as the
  31. argument that successive bisections can produce an arbitrarily close
  32. approximation to a trisection.  Yes, they can, but the issue is the
  33. formal solvability of the problem, isn't it?
  34.