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