|
![](/i/fill.gif) |
On 10/7/2010 8:59 AM, Darren New wrote:
> Look back over the diagonalization argument. There's no mention in there
> of what gets computed for who or what. It (basically) shows there are
> more partial functions than there are complete functions, so no complete
> function will be able to list all the partial functions.
Either I'm misinterpreting something or you didn't quite mean to type it
that way, because as you put it that seems to be wrong. Given two sets
X and Y, I should think that there would only be more partial function
from X to Y than total function when both X and Y are finite. In the
context of computable function both X and Y are generally assumed to be
the set of natural numbers, so this wouldn't be the case. Even if we
restricted X and Y to finite sets, it still doesn't seem right since the
denationalization you're trying to make work would need there to be
using the number of programs which compute functions, rather than the
number of functions itself.
Assuming that you were talking about "more programs which compute
partial functions than programs which compute total functions" it still
seems wrong, since I think it's pretty easy to show that there's
countable infinitely many of each.
Am I missing something here? Sure Rice's theorem can be proven with
denationalization, but I don't think it has anything to do with the
cardinality of sets (unlike, say, Cantor's denationalization).
Post a reply to this message
|
![](/i/fill.gif) |