Prove that the language A M accepts x is ceSolutionAnswer

Prove that the language A = { | M accepts x} is c.e.

Solution

Answer:

Here C.E. stands for Computationally Enumerable. A language is said to be Computationally Enumerable (CE), if there exists some Turing Machine, M, that accepts every string in L and either rejects or loops over every string not in L. Another term used for such languages is Semi-decidable.

A langauge can be termed computationally enumerable if and only if there exists some enumerator that enumerates the langauge. An enumerator is a Turing Machine that outputs, possibly repetitively, the string x from language,

For the given language, lets assume there exists an enumerator E for the language A.

On an input x, we can run E till it outputs x. If x is output, the it will be accepted. In case, x in not output, then E will run forever without accepting x. Hence, it can be said that given language A is computationally enumerable or semi-decidable.