# What does “effective enumeration” in Turing machines mean?

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 ?

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

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.
• 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$. – user80502 Jan 8 '18 at 8:04
• @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. – fade2black Jan 8 '18 at 8:17