[eilonsh]

I have just learned the prove that the language ALLcfg is undecidable by computation histories and reduction from Atm.
I don't understand why we can't do the same thing to prove that Ecfg undecidable? (but we know that Ecfg decidable so
this is wrong but why?)

[modi123_1]

Care to elaborate, provide context, or retry the translation there for folk not sitting around your living room, bub?

[Skydiver]

I think the OP is talking about ALL_CFG, A_TM, and E_CFG in the context of Alan Turing's work.

Frankly most of this stuff has gone in one ear and out of the other ear for me: http://www.iith.ac.i...4510/allcfg.pdf

[macosxnerd101]

E_CFG is the set of CFGs whose languages are empty. This is easy to check. We use a pebbling algorithm (similar to the Huffman tree algorithm) to build a derivation tree from the bottom up. The language L is empty iff we cannot reach S, the start symbol. So we have an algorithm to decide E_CFG

ALL_CFG is a bit trickier. Basically, we take an instance of the Halting language <M, w> and construct a string based on the sequence of states (separated by the # symbol) visited when M runs on w. The language then is Q(#(Q + \Gamma))^{*}, where Q is the set of states in the Turing Machine and Gamma is the tape alphabet. Since this language is regular, it is also context-free.

So what we prove is that the language of non-accepting computation histories is undecidable. Observe that computations that don't halt will fall into this category.

So the strings of computations from <M, w> pairs where M halts are recursively enumerable. Since the complement is undecidable, the language of accepting computation histories is undecidable. The result follows.

The reason a reduction works here is because there is choice in the matter, or condition, on which a string may be finite. The condition is the Turing Machine halting. So we can't check the computation history string if the TM never halts. In the E_CFG language, we have an algorithm to decide this and there is no real choice in the matter. Either we can get to S or we can't. In other words, do we have some string in the language?