Printable View
so, im trying to figure this out and i hoped you guys could help. i know they are both true, im just not sure i see why:
1) every infinite recursive set contains a non-r.e. subset
2) every r.e. set contains an infinite recursive subset
any ideas?
thanks
Eh?? a recursive set of what? define what you mean by a "recursive infinite" set, an non-recursive subset and recursive set an infinite recursive subset.
Sorry but im not sure how i can be more explicit, i guess im not sure what youre asking. I meant in terms of languages of turing machines, so an infinite recursive set of strings.
By infinite recursive set i mean a set for which a turing machine exists that halts on all words (whether they are in the language or not), and the set is infinite. like the set of all even-length binary strings would be infinite and recursive.
A non-re set is a set that is not turing-recognizable, like the diagonal language, for example.
maybe these help: http://en.wikipedia.org/wiki/Recursive_set
http://en.wikipedia.org/wiki/Recursively_enumerable_set
(i really dont mean to be patronizing, im just not sure how to explain)
i actually think i got the second one, using an enumerator, etc. but im still totally lost on the first one...can anyone help please!
1) you can construct one: infinite recursive set is equivalent to set of all words (since you can enumerate all words of inf. rec. set and make correspondence with all words). Pick any non-r.e. language, make translation to that original recursive set - that's non-r.e. subset.Quote:
Originally Posted by nikonratm
2) pick any procedure to enumerate original set. Machine to solve recursive subset looks through enumeration until it finds any word of length no less then legth of given word (if it hasn't found given word in the list yet, it says NO). Since set is infinite, for every length n there is a first occurance of word with length l>n, so number of such first occurances is infinite, every first occurance will be found, so constructed subset is infinite.