home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1853 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  1.1 KB
  1. Path: sparky!uunet!sun-barr!ames!elroy.jpl.nasa.gov!swrinde!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!FWI.UVA.NL!peter
  2. From: peter@FWI.UVA.NL (Peter van Emde Boas)
  3. Newsgroups: comp.theory
  4. Subject: Re: Are there reductions from Hilbert's 10th problem?
  5. Message-ID: <199209010915.AA06626@vera.fwi.uva.nl>
  6. Date: 1 Sep 92 23:03:13 GMT
  7. Sender: daemon@ucbvax.BERKELEY.EDU
  8. Reply-To: Peter van Emde Boas <peter@fwi.uva.nl>
  9. Lines: 16
  10.  
  11. Dear Imre. I know of a prime example of a reduction from Hilbert 10
  12. which in the mean time seems to have been replaced by a far easier
  13. reduction by direct means.
  14.  
  15. The reference is to be found in the ph.d. thesis of Jan van Leeuwen, Rule
  16. labeled programs, written under prof. D. van Dalen  on which he graduated
  17. jun 07 1972.
  18.  
  19. As told the same problem, dealing with the generative power of some
  20. specific class of controled context free grammars, nowadays can be
  21. solved directly in a few pages instead of the ca. 50 pages in this
  22. thesis. Still it is an example of the sort of reductions you seem to
  23. be looking for.
  24.  
  25. Sincerely yours
  26. Peter van Emde Boas
  27.