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?

Improve this question
$\endgroup$
3
  • $\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, 2017 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, 2017 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, 2017 at 10:13

1 Answer 1

Reset to default
2
$\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?,...
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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