Cheap and Secure Web Hosting Provider : See Now

[Solved]: Language is recursive, hence recursively enumerable

, , No Comments
Problem Detail: 

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?

Asked By : revisingcomplexity

Answered By : babou

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.

QED

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41211

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback