0
$\begingroup$

what is meant by EFFECTIVE ENUMERATION i have comes across this word when I was reading about enumerators for Turing machines is it same as LEXICOGRAPHIC ORDER? so effective enumeration is possible for recursive sets but no recursively enumerable sets? i came across this in this question of a competitive exam

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as ω1,ω2,ω3,…. Define another language L2 over Σ∪{#}

{wi#wj ∣ wi,wj∈L1, i < j}.

Here # is a new symbol.

Consider the following assertions.

S1:L1 is recursive implies L2 is recursive

S2:L2 is recursive implies L1 is recursive

which of the following is true ?

Improve this question
$\endgroup$
4
  • $\begingroup$ Where did you come across this word? Could you include the fragment of the text where the EFFECTIVE ENUMERATION is defined or mentioned? $\endgroup$ – fade2black Jan 8 '18 at 7:07
  • $\begingroup$ Yeah, context would be useful. At the cost of being tautological, an "effective enumeration" is an enumeration that is effective (i.e. computable). $\endgroup$ – quicksort Jan 8 '18 at 7:09
  • $\begingroup$ This article may clarify the concept. $\endgroup$ – fade2black Jan 8 '18 at 7:19
  • $\begingroup$ @quicksort fade2black have a look at the edited question $\endgroup$ – venkat Jan 8 '18 at 7:56
1
$\begingroup$

One way to approach EFFECTIVE ENUMERATION is as following. Let $L=\{a_1, a_2, \dots\}$ be a set/language. Then we (effectively) enumerate $A$ if we can construct a TM $M$ which prints out (enumerates) all elements of $L$ on the tape, say in the following way: $a_1$#$a_2$#$a_3$#$\dots$. The order of the elements is not important. What is important is that any element of $L$ will eventually be printed on the tape, meaning it must not be a LEXICOGRAPHIC order.

Improve this answer
$\endgroup$
7
  • $\begingroup$ so if we know that L1 is recursive then will L2 be recursive? how will we reject the strings wi#wj i > j? $\endgroup$ – venkat Jan 8 '18 at 7:59
  • $\begingroup$ In addition, an element can be printed several times. There's another equivalent approach that states that a set $L$ is recursively enumerable if and only if there's a recursive function with definition domain $L$. $\endgroup$ – user80502 Jan 8 '18 at 8:04
  • $\begingroup$ @venkat if $L_1$ is recursive then so is $L_2$. It is not hard to prove it. Given $w$#$u$ you first effectively check if both $w$ and $u$ are in $L_1$, and if so then you compute indices of $w$ and $u$ for a fixed enumeration of $L_1$. Say, $w = w_i$ and $u=w_j$ for some $i$ and $j$. If $i<j$ then accept otherwise reject. $\endgroup$ – fade2black Jan 8 '18 at 8:17
  • $\begingroup$ so here in the question when it says " effective enumeration " it doesn't signify the order of w1 w2 w3 and so on but when we say L1 recursive then we have an enumerator that generates those strings in the order of their indices(lexicographic) hence proving L2 is recursive is easy am i right? $\endgroup$ – venkat Jan 8 '18 at 8:23
  • $\begingroup$ how can we prove if L2 is recursive then L1 is recursive? $\endgroup$ – venkat Jan 8 '18 at 8:26
0
$\begingroup$

"Effective" usually means "computable". Therefore, an effective enumeration is a computable enumeration.

In the problem you note, this is redundant. An algorithm that enumerates a set is, by definition, a witness for the set being effectively enumerable.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.