Hi, Il 14/02/20 17:50, persres ha scritto: > I know the definition of recursion functions. I am unclear about > the concept of computability. Wouldn't any function we can write down be > recursive? Could someone give me a function that is not recursive (not > computable). I would have thought any function that can be written as an > expression (analytic expression) would be recursive/computable.
There are people who can answer you much better than me on this list, but let me have a try anyway. It all depends on what you mean by "write down". Most of the notations we are used to "explicitly" give a function are actually some form of recursive definition, so trivially they can only describe either total or partial recursive functions (depending on which specific notation we are considering). However, they cannot describe all functions. For example, let us only consider function N -> N for simplicity. It is well known that the cardinality of such functions is equal to the cardinality of continuum, but we can describe only a countable number of partial recursive functions. Therefore there must be a lot of functions N -> N that are not partial recursive. Actually, the majority of them is not. One could say that most of these noncomputable functions are probably not interesting. Unfortunately (or fortunately, depending on how you see the consequences) there are quite a few very interesting functions that turn out to be noncomputable. A nice list is given by this MO post[1]. [1] https://mathoverflow.net/q/29197/22134 Hope this helps, Giovanni. -- Giovanni Mascellani <[email protected]> Postdoc researcher - Université Libre de Bruxelles -- You received this message because you are subscribed to the Google Groups "Metamath" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/metamath/4bced8b0-669b-eaff-c4b0-ee4ba8bbd314%40gmail.com.
signature.asc
Description: OpenPGP digital signature
