I was going through a book of proof and I read:

If L is recursive, L is r.e.

And the proof goes:

  • Let L be recursive, hence there is a TM that decides it
  • Convert an halt state to a normal state
  • Add to program that when it enters this state it goes to infinite loop

How can this be a proof for it?

  • 2
    $\begingroup$ It's (part of) a constructive proof; starting from the decider, we construct a semi-decider as per the definitions in place. $\endgroup$ – Raphael Apr 10 '15 at 11:47
  • $\begingroup$ what is the full proof? $\endgroup$ – revisingcomplexity Apr 10 '15 at 11:52
  • $\begingroup$ What do you mean by "a full proof"? Actually, you did not give us a full question, since you did not state what is your book definition of recursive and of RE. $\endgroup$ – babou Apr 11 '15 at 12:33

One possible definition of recursively enumerable (most likely the one used by your instructor) is that it is the domain of a partial function. In Turing Machine terms, that means the following definition:

A language $L$ is recursively enumerable iff there is a turing machine that halts on input $x$ exactly whenever $x\in L$.

Note that there is no longer any notion of accepting an rejecting state.

Now, assuming that you have a recursive language $L$, you know there is a TM $M$ that always halt on any input $x$ (on the alphabet of $L$), being in an accepting state iff $x\in L$.

To prove that L is RE, you can build a machine $M'$, that will halt exactly on the words $x\in L$. This implies the following step, if you want to be fully formal:

  • define the TM $M'$;

  • prove that $M'$ halts on all words $x\in L$;

  • prove that $M'$ halts only on words $x$ that are in $L$, i.e. does not halt on words $x\notin L$.

Actually, in most proofs of this type, the difficulty is to define (construct) the machine $M'$, while the two other steps are often long and tedious, but not difficult. So it is common to consider that giving the definition is enough of a proof (as long as the definition is correct).

However, that may be unwise, because sometimes the other two steps will uncover errors in the definition provided in the first step. So you are quite correct in asking for a full proof. The definition of $M'$ is not enough for a formal proof, even though it is pretty trivial in the example of your question.

Actually, the construction you give, possibly badly recorded, does contain two error:

  • accepting states are not made to loop infinitely;

  • accepting states must remain halting states.

Given the TM $M$ that can decide whether a string $x$ belongs to $L$, you define the TM $M'$ as follows:

  • convert all non-accepting halting states into states that loop for ever;

  • convert all accepting halting states into simple halting states (not really important, but acceptance will be irrelevant, only halting will matter);

Everything remains otherwise the same: same states, same transitions, and you have only added transitions to make the non-accepting halting states go into a loop.

Then, you can prove by induction on the length of a computation (number of transitions), that if $M$ reaches an instantaneous description $d$ on input $x$ in $n$ steps, then $M'$ reaches the same $d$ in input $x$ also in $n$ steps. Whenever $x\in L$, there is a computation of $M$ such that $M$ reaches an instantaneous description with some halting accepting state $q$. Hence, the same computation for $M'$ must reach the same instantaneous description with state $q$, which by construction of $M'$ is still a halting state. Therefore $M'$ is in a halting state.

When $x\notin L$, there is a computation of $M$ such that $M$ reaches an instantaneous description with some halting non-accepting state $q$. Hence, the same computation for $M'$ must reach the same instantaneous description with state $q$, which by construction of $M'$ is a looping state, so that $M'$ will not terminate.

So the TM $M'$ is a machine that does recognize $L$ as an RE set, according to the definition above.


| cite | improve this answer | |

Depending on what definitions you use, the proof can be trivial. We can all agree that a set $S$ is recursive if there is a Turing machine that halts on every input, accepts the members of $S$ and rejects the non-members of $S$. Such a Turing machine is called a decider of the set.

One definition of the recursively enumerable sets is that $S$ is RE if there is a Turing machine that accepts every member of $S$ and does not accept any non-member. That is, if $x\notin S$, the machine either rejects it or loops forever. By this definition, it is trivial that every recursive language is RE: the machine that decides the language has the property that it accepts everything in the set and nothing outside it.

The other definition is that a set $S$ is RE if there is a Turing machine that accepts every member of the set and loops forever for every non-member. This appears to be the definition your book is using. Now, suppose you have a machine that decides a set $S$. Modify it so that, instead of rejecting non-members of the set, it loops forever. This gives a machine that accepts every member of $S$ and loops forever for every non-member. This is exactly what you need to conclude that $S$ is RE.

The same idea proves that the two definitions of RE are the same. Any machine that obeys the second definition also obeys the first one (the first says it can either loop or reject for non-members: it happens to loop for all of them but that's a valid choice). Any machine that obeys the first definition can be converted to obey the second by the same trick: replace rejection with looping.

| cite | improve this answer | |

The class R is a proper subset of the class RE and this is just a trivial consequence of the definition of these classes. Basically a Language L is in R iff both L and (not)L are in RE. So if something is in R it must be in RE.In the proof you have presented this idea is illustrated by sort of handicapping the TM by enabling it to satisfy only one of the 'anded' conditions.

| cite | improve this answer | |
  • 2
    $\begingroup$ I've never seen that as the definition of recursive sets. Rather, it's a theorem, which needs to be proven and the question is asking about exactly that. $\endgroup$ – David Richerby Apr 10 '15 at 12:53
  • 1
    $\begingroup$ turing-decidable=recursive.turing-recognizable=recursively enumerable.A language is decidable iff it is turing-recognizable and co-turing-recognizable. $\endgroup$ – xyz123 Apr 10 '15 at 12:57
  • 2
    $\begingroup$ Yes. But that is a theorem, not a definition. Since it's a theorem, it needs proof. The question is asking about that proof. $\endgroup$ – David Richerby Apr 10 '15 at 13:34
  • $\begingroup$ @DavidRicherby Well, you can define Recursive as recognized by a TM that always halt, accepting of not, while RE is by a TM that may still accept of reject, but may not halt when a word is not in the language. In that case the proof is trivial to the vanishing point. See third definition on Wikipedia. It is possible that user RRC learned that Recursive is by definition RE+coRE, to state it briefly. In which case the proof vanishes. The OP did not give any definition in the question. We only guessed. $\endgroup$ – babou Apr 10 '15 at 14:27

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.