0
$\begingroup$

K = {<J, a, b, c> : J is a Java program, a, b, and c are integer variables declared in J, and throughout the execution of J, a never has the same value as b and a never has the same value as c}.

I'm aware the problem is not actually decidable as I performed a reduction from ATM (or halting problem), which proves it is not decidable, but my question is it Turing-recognizable or not Turing-recognizable? if not is it co-Turing recognizable and what would be the complement? I would assume it would be:

K' = {<J, a, b, c>: J is a Java program, a, b, and c are integer variables declared in J, and throughout the execution of J, a always has the same value as b and a never has the same value as c}.

$\endgroup$
1
  • $\begingroup$ Please proof-read your question and edit it to correct all typos and errors. The name is "Turing", not "turing" or "turning". Please ask only one question per post. $\endgroup$
    – D.W.
    Commented May 20, 2023 at 20:52

1 Answer 1

1
$\begingroup$

The complement of your language $K$ is easily seen to be recognizable: If $J$ isn't a valid Java programme, or it is lacking the specified integer variables, we can easily tell. Otherwise, we run the Java programme and monitor the values of $a$, $b$ and $c$. If we see $a$ to have the same value as $b$, or if we see $a$ to have the same value as $c$, we are also in the complement of $K$. This process will identify all inputs not belonging to $K$, so we have what we want.

$\endgroup$
1
  • $\begingroup$ Would K be not TR? $\endgroup$ Commented May 21, 2023 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.