I know all computable partial functions are countable. Wondering if it is the the other way around as well.
1
-
3$\begingroup$ What do you mean by a function being countable? $\endgroup$– David RicherbyCommented Jan 26, 2019 at 21:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
You must be mistaken about a definition. It is not that any single computable partial function is countable. Rather, the set of all computable partial functions is a countable set. (There isn't any such thing as a countable partial function.)
-
$\begingroup$ YOU HAVE ENLIGHTENED ME! My prof is horrible $\endgroup$– NoNameCommented Jan 26, 2019 at 22:36
-
2$\begingroup$ Yeah, he didn't teach you to provide evidence, especially when you're insulting someone on-line rather than double-checking whether you misunderstood what they said. $\endgroup$ Commented Jan 27, 2019 at 8:09
$\begingroup$
$\endgroup$
By a countable partial function, you probably mean a partial function that can be specified by a finite amount of information. But even if you asked your question in that form, people would probably still tell you that "can be specified" is unclear, instead of trying to explain why the answer your question is: "No, there are non-computable functions which can be specified by a finite amount of information!"
The prototypical example of such functions are the partial functions from the arithmetical hierarchy, i.e. the functions computed by a Turing machine with access to an oracle for deciding whether an explicitly written down (by the Turing machine) "sentence in the first order language of arithmetic" is true or false.
Very few people would still protest that it is not clear whether those functions really "can be specified", since we have to assume that every "sentence in the first order language of arithmetic" is either true or false, for those functions to be well-defined. Computation in the limit provides even less objectionable examples of non-computable partial function which can be specified by a finite amount of information. In fact, those questions of "definability" were once investigated in the context of recursion theory.
