Prove that this language is not recursive by reducing the problem halts to it: {

Question

Prove that this language is not recursive by reducing the problem halts to it:

{ p | p is a method that takes an integer as a parameter and returns an integer, returning a negative number when its input is 0. }

sample example:

Le = fp j p is a recognition method that never returns trueg
that is, all p such that L(p) = fg. Assume recursive, and empty is
decision method that implements.
To show that it is non-recursive, implement halts using empty:
boolean halts(String p, String x) {
String x2 =
"boolean f(String z) { " +
" run(""+p+"",""+x+""); " +
" return true; " +
"} ";
boolean b = empty(x2);
return !b;
}

Explanation / Answer

Answer:

We know that the recursive languages are a subset of the recursively enumerable languages, We will now show that they are a proper subset.
We know how to enumerate strings over a given alphabet, w1, w2, w3, .... We know that we can enumerate Turing machines, T1, T2, T3, .... (Recall that each Turing machine defines a recursively enumerable language.)
Consider the language
L = {wi: wi Î L(Ti)}
and its complement:
-L = {wi: wi Ï L(Ti)}
It can be shown that L is recursively enumerable.
If -L is recursively enumerable, then there must exist a Turing machine that recognizes it. This Turing machine must be in the enumeration somewhere - call it Tk.
Consider a string wk. Does it belong to L?
If wk belongs to L then (by the way we have defined L) Tk accepts this string. But Tk accepts only strings that do not belong to L, so we have a contradiction.
If wk does not belong to L, then it belongs to -L and is accepted by Tk. But since Tk accepts wk, wk must belong to L. Again, a contradiction.
We have now defined a recursively enumerable language L and shown by contradiction that -L is not recursively enumerable. We know that if a language is recursive, its complement must also be recursive. If language L above were recursive, then -L would also be recursive, hence recursively enumerable. But -L is not recursively enumerable; therefore L must not be recursive.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.