1
$\begingroup$

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)

Improve this question
$\endgroup$
2
  • $\begingroup$ How do you define partially decidable? $\endgroup$
    – Yuval Filmus
    Commented Sep 8, 2019 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
    Commented Sep 8, 2019 at 14:24

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1

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.