Article View: comp.theory
Article #1681Re: Are type 0 languages recursive?
From: LI Chung-Yuen
Date: Tue, 22 Dec 1992 13:34
Date: Tue, 22 Dec 1992 13:34
16 lines
1209 bytes
1209 bytes
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
Technical Details
Message-ID:
<1992Dec22.133424.5951@cucs5.cs.cuhk.hk>Path:
arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!hp9000.csc.cuhk.hk!cucs5.cs.cuhk.hk!cyliReferences:
<1992Dec21.095854.7218@ghost.dsi.unimi.it>Show Full Headers
Complete Article Headers
Newsgroups: comp.theory Path: arc1-ca.pugleaf.net!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