We know, that all (partial) recursive functions are countable (since one can for example interpret them as some simple programs; and the set of those programs are themselves countable), so one can try to apply a "diagonal" argument to them: Let $g(n)=f_n(n)+1$, if $f_i$ is the $i$-th (partial) recursive function. Now, $g$ can't be (partially) recursive, because otherwise it would be one of the $f_i$'s, so we would get a contradiction. But my instructor mentioned in class, that we don't get a contradiction, if we restrict ourselves just to partial recursive functions. I am not sure if I understood him correctly, but could maybe someone here enlighten me, whether it makes sense what he said ? Because it seems to me that this assertion is wrong... Or, if I misunderstood, in which context it would make sense what he said ?
Why can't we diagonalize out, if we deal with partial functions?
3
$\begingroup$
computer-science
computability