recursive function, computablity vs formulae

[persres]

Hello all, 

      I know the definition of recursive functions. I am unclear about the concept of computability. Wouldn't any function we can write down be recursive? I would have thought any function that can be written as an expression (analytic expression) would be recursive/computable. Could someone give me a function that is not recursive (not computable). 

Please clarify

Pers

[Paul Chapman]

Pers,

 

There are many proven non-computable functions, and to prove a function has any property, you have to be able to define it analytically. For example, the Busy Beaver Function is non-computable, but it can be defined in ZFC, and therefore in Metamath.

 

Cheers, Paul

[Giovanni Mascellani]

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 <g.masc...@gmail.com>
Postdoc researcher - Université Libre de Bruxelles

[fl]

One could say that most of these noncomputable functions are probably
not interesting.

On the other side, the universe is finite. Everything interesting to measure is never smaller than a few picometres. 

Everything related to computer science, the number of computers, the number of bytes on earth and so on

is finite. And there is even an interesting text from Leibniz called "Apokatastasis Panton", where he proves that the number

of possible histories of the humanity is finite.

 

Everything interesting is finite.

-- 

FL