# Expressing partial decidability using existential quantification

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)

• How do you define partially decidable? – Yuval Filmus Sep 8 '19 at 13:20
• 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). – Evil Sep 8 '19 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.