Solution:
From last problem (sipser 3.18) : If we have an enumerator which enumerates a language in lexicographic order, then we can make a decider using it.
Now. given a Turing recognizable language L, R be Turing machine which recognizes it. Clearly we can make an enumerator E using R, which enumerates L. Not necessarily, it enumerates in lexicographic order. But we can always pick lexicographic subset from the enumerated set.
My new enumerator E<prime> will work as follow :
From last problem (sipser 3.18) : If we have an enumerator which enumerates a language in lexicographic order, then we can make a decider using it.
Now. given a Turing recognizable language L, R be Turing machine which recognizes it. Clearly we can make an enumerator E using R, which enumerates L. Not necessarily, it enumerates in lexicographic order. But we can always pick lexicographic subset from the enumerated set.
My new enumerator E<prime> will work as follow :
Run E, print newly generated string if it is max(lexicographically) in all generated strings till this point.
Otherwise reject it, And wait for next string to be generated by E.
And definitely this subset is Turing-decidable.
No comments:
Post a Comment