1
$\begingroup$

How to prove that if the set and its complement are recursively enumerable, then this set and its complement are recursive?
My idea is that we can make the characteristic function of recursively enumerable set to be a total function using characteristic function of the complement (we can compute both $\chi_A$ and $\chi_\overline{A}$ step by step, alternating steps between them, and when either one stops, we can determine if the element belongs to the set $A$ or its complement).
Is it right?

$\endgroup$
0
$\begingroup$

Roughly, yes, that's the right idea.

I think there are a few small issues though.

First, you can not compute the characteristic function $\chi_A$, since this is computable only when the set is recursive. What you can compute is the semi-characteristic function, whose domain is $A$, and is constantly $1$ there.

If we wanted to be more pedantic, "computing a function step by step" is not completely precise. One usually takes a "program" implementing the semi-characteristic (e.g. a Turing machine accepting each element of $A$, and diverging elsewhere) and executes that program step-by-step.

So, given two TMs $M$ and $N$ implementing both semi-characteristics, you can craft a new TM $O$ which runs them "in parallel, step by step" on the same input $w$. Eventually, one (and only one) of them will halt, and $O$ can accept or reject "w" consequently.

A completely computational-model-agnostic way to state "computing step by step" could be to exploit the Kleene's normal form theorem, where a number $x$ plays an equivalent role to the number of steps. While this is arguably the "true mathematical" way to do it, in computer science we often prefer to work with "programs" (TMs,...) since we find those more familiar.

$\endgroup$
0
$\begingroup$

From the Turing machine point of view, $A$ and $\overline{A}$ being R.E. means that there are is a TM $M_A$ that always halts and accepts when its input is in $A$ and, similarly, a machine $M_{\overline{A}}$ that always halts and accepts when its input is in&nbsp$\overline{A}$. A set $B$ being recursive means there's a TM $N_B$ which halts for all inputs, accepting if the input is in $B$ and rejecting if it isn't.

So, to decide $A$, you just need to simulate both of these machines in parallel until one of them accepts, and then accept if it was $M_A$ that accepted and reject if it was $M_{\overline{A}}$. One of these two things is guaranteed to happen, so the we're done. $\overline{A}$ is similarly decidable.

Alternatively, a set $A$ is R.E. if, and only if, there is a TM $E_A$ that, when started with no input, writes out a list of $A$'s elements on its tape, with the guarantee that every element of $A$ appears in the enumeration if you wait long enough. (So, for example, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ... is an enumeration of the natural numbers, but listing all the odd numbers and "then" all the even ones wouldn't be valid, since the evens would never actually appear.)

In this scenario, we can decide whether $x\in A$ by simulating the enumerators $E_A$ and $E_{\overline{A}}$ in parallel until one of them says "$x$", which is guaranteed to happen. Then accept or reject as appropriate.

$\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.