home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2752 < prev    next >
Encoding:
Text File  |  1992-12-23  |  1.2 KB  |  28 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!hp9000.csc.cuhk.hk!cucs5.cs.cuhk.hk!cyli
  3. From: cyli@cs.cuhk.hk (LI Chung-Yuen)
  4. Subject: Re: Are type 0 languages recursive?
  5. Message-ID: <1992Dec22.133424.5951@cucs5.cs.cuhk.hk>
  6. Sender: news@cucs5.cs.cuhk.hk
  7. Organization: Faculty of Engineering, The Chinese U. of Hong Kong
  8. References: <1992Dec21.095854.7218@ghost.dsi.unimi.it>
  9. Date: Tue, 22 Dec 1992 13:34:24 GMT
  10. Lines: 16
  11.  
  12. lombardo@ghost.dsi.unimi.it (franco lombardo) writes:
  13. >Are type 0 languages recursive? If the answer is yes, where can I find
  14. >a prove of it? Otherwise, can you show an example of  a type 0 
  15. >language which is not recursive?
  16. >Are type 0 languages "recursivly numerable"?
  17.  
  18. Type 0 languages are, by definition, recursively enumerable.
  19. The universal language (Introduction to Automata Theory, Languages and
  20. Computation, Hopcroft & Ullman, p.183) is recursively enumerable but not
  21. recursive.
  22. The set of recursive languages is a proper subset of the set of
  23. recursive renumerable languages.
  24.  
  25. --
  26. Li Chung Yuen    cyli@cs.cuhk.hk    (852)609-7734
  27. Room 121 Lady Shaw Building The Chinese University of Hong Kong HONG KONG
  28.