Logic & Computability Problem

70 Views Asked by At

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.

1

There are 1 best solutions below

0
On

I am guessing at the interpretation to this question.

if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate

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.