i read this sentence in one exam that be false. anyone could say why?
if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate.
i read this sentence in one exam that be false. anyone could say why?
if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate.
Copyright © 2021 JogjaFile Inc.
I am guessing at the interpretation to this question.
Suppose the range of $l(x)$ is all programs.
Suppose $r(x)$ is a simulator.
Suppose $H(x)$ is the predicate "$l(x)$ runs forever without stopping."
When $r$ stops the simulation of $l$ , you know that $H$ is false. However, $H$ is the halting problem which is considered to be undecidable. So $l$, $H$, $r$ are a counterexample.