1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – chi Oct 30 '17 at 9:38
  • $\begingroup$ @chi if the decider halts, it means the sequence of strings generated by the enumerator is accepted? $\endgroup$ – Maxxx Oct 30 '17 at 9:48
  • $\begingroup$ 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. $\endgroup$ – chi Oct 30 '17 at 10:13
1
$\begingroup$

M1 and M2 together will eventually enumerate every possible string. So the trick is to alternate between them. Then you get an enumerator that enumerates all strings. Every time you compare the output string of the enumerator to your input string. At some point they will be equal. Then you just have to look whether you have used M1 or M2 in the last step.

You compute for input string w:

M1(0)=w?, M2(0)=w?, M1(1)=w?, M2(1)=w?, M1(2)=w?, M2(2)=w?,... 
$\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.