# Constructing a decider for a language

I'm confused about the idea of constructing a decider for a language and i need some help with it.

For example, if i have an enumerator M1 for a language L and another enumerator M2 for the complement of L, how do i construct a decider for L that uses both enumerator M1 and M2?

I understand that i would first introduce a Turing Machine with an input string and simulate it but I'm lost in the next stage of constructing a decider. By the way, enumerators are Turing Machines that outputs a sequence of strings.

Could anyone please explain on how do i construct a decider for the language L that uses both enumerators M1 and M2?

• Given $x$, for each value of $n\geq 0$, run $M1(x)$ for $n$ steps and run $M2(x)$ for $n$ steps. What will happen, eventually?
– chi
Oct 30 '17 at 9:38
• @chi if the decider halts, it means the sequence of strings generated by the enumerator is accepted? Oct 30 '17 at 9:48
• Actually, my comment assumed that $M1,M2$ are semi-deciders: TMs that halt exactly on L and its complement, respectively. With enumerators, you have instead to run them until they output $n$ strings, and check if $x$ if among them instead. Anyway, the idea is to run $M1,M2$ in "parallel", much similarly to how an operating system runs many processes on the same CPU, continuously switching between the processes so that all of them keep on running.
– chi
Oct 30 '17 at 10:13

M1(0)=w?, M2(0)=w?, M1(1)=w?, M2(1)=w?, M1(2)=w?, M2(2)=w?,...