How to prove that class of “recursive” and “recursively enumerable” languages are not equal?

224 Views Asked by At

I would like to formulate a formal proof for showing that the classes of recursive and recursively enumerable languages are not equal.

I know that recursive languages are accepted by Turing machines with stop property and recursively enumerable languages are accepted by Turing machines.

1

There are 1 best solutions below

2
On BEST ANSWER

It is enough to find a recursively enumerable language that is not recursive. This can be done either by exhibiting a concrete example or by means of a proof by diagonalization.