nikonratm
December 8th, 2005, 07:28 PM
Ack, someone please help me!
(a) Consider a set S of strings S = {0^i1, 0^i2, ...} representing the natural numbers i1, i2, ... This set may be finite or infinite. Is every such set recursively enumerable?
(b) Consider a given set S as above, and assume that it is infinite and known to be RE (either because you proved it for all sets S above or this one has been shown to be). Consider the infinite union of languages Lunion = UiESL(Mi) [that reads the union from i element of S of L(Mi)] where Mi denotes the ith turing machine in lexicographic order using a predetermined canonical method of representing TMs. Is this language Lunion necessarily RE?
(c) Is the union of any infinite number of RE languages always RE?
thanks
(a) Consider a set S of strings S = {0^i1, 0^i2, ...} representing the natural numbers i1, i2, ... This set may be finite or infinite. Is every such set recursively enumerable?
(b) Consider a given set S as above, and assume that it is infinite and known to be RE (either because you proved it for all sets S above or this one has been shown to be). Consider the infinite union of languages Lunion = UiESL(Mi) [that reads the union from i element of S of L(Mi)] where Mi denotes the ith turing machine in lexicographic order using a predetermined canonical method of representing TMs. Is this language Lunion necessarily RE?
(c) Is the union of any infinite number of RE languages always RE?
thanks