def. A predicate M(x,y) is partially decidable if the function f given by " f(x,y) = 1(if M(x,y) holds), f(x,y) = undefined(otherwise) " is computable.

Thm. If M(x,y) is partially decidable, then so is the predicate ∃yM(x,y).

proof. Take a decidable predicate R(x,y,z) such that M(x,y) iff ∃zR(x,y,z). Then...

I can not imagine the R(x,y,z)... Please explain the way of thinking.

( Page115, Computability by Nigel Cutland)

  • $\begingroup$ How do you define partially decidable? $\endgroup$ – Yuval Filmus Sep 8 at 13:20
  • $\begingroup$ Please edit your question to include explanation of "partially decidable" (and delete comment afterwards). Please include more accessible reference (I do not know what resource the "Cutland p115" is). $\endgroup$ – Evil Sep 8 at 14:24

The predicate $R(x,y,z)$ states that "$M$ accepts the input $x,y$ within $z$ steps". It is computable since we can simulate a given machine on a given input for a bounded number of steps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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