home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.theory
- Path: sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!hp9000.csc.cuhk.hk!cucs5.cs.cuhk.hk!cyli
- From: cyli@cs.cuhk.hk (LI Chung-Yuen)
- Subject: Re: Are type 0 languages recursive?
- Message-ID: <1992Dec22.133424.5951@cucs5.cs.cuhk.hk>
- Sender: news@cucs5.cs.cuhk.hk
- Organization: Faculty of Engineering, The Chinese U. of Hong Kong
- References: <1992Dec21.095854.7218@ghost.dsi.unimi.it>
- Date: Tue, 22 Dec 1992 13:34:24 GMT
- Lines: 16
-
- lombardo@ghost.dsi.unimi.it (franco lombardo) writes:
- >Are type 0 languages recursive? If the answer is yes, where can I find
- >a prove of it? Otherwise, can you show an example of a type 0
- >language which is not recursive?
- >Are type 0 languages "recursivly numerable"?
-
- Type 0 languages are, by definition, recursively enumerable.
- The universal language (Introduction to Automata Theory, Languages and
- Computation, Hopcroft & Ullman, p.183) is recursively enumerable but not
- recursive.
- The set of recursive languages is a proper subset of the set of
- recursive renumerable languages.
-
- --
- Li Chung Yuen cyli@cs.cuhk.hk (852)609-7734
- Room 121 Lady Shaw Building The Chinese University of Hong Kong HONG KONG
-