On 16 Sep 2009, at 18:12, Bruno Marchal wrote:
>
>
> If it is OK, in the next post we begin to address the computability
> issue. I give you an anticipative exercise or subject reflection.
> This is a deep exercise. Its solution leads to the notion of
> universal function and universal number/machine. More exactly it
> leads to an evaluation of the price we have to pay if we want to
> believe in that notion.
>
> We have seen that the set N^N is non enumerable. This means it is a
> *huge* infinite set, compared to N.
> We could argue that there are too much functions in that set. Most
> usual functions that we encounter in real life, both in math and
> physics, seem to share the property that they are computable. This
> means that we can write some rules or recipe for computing them, or
> that, may be, we can build some mechanical device capable of
> computing them. The natural functions we met were the exponential
> f(n) = 2^n, or the factorial(n), or similars. It seems that we can
> explain to each other how to compute them, and you already known
> that we can build machines computing them indeed. So, we could
> decide, if only to avoid those big infinities, to restrict ourself
> on the computable functions. Let us define N^N-comp to be the set of
> computable functions from N to N.
>
> The question is: is there a bijection from N to N^N-comp ?
This is a tricky question.
I give you an argument that there is a bijection between N and N^N-
comp. Followed by an argument that there is no bijection between N and
N^N-comp.
Which one is wrong?
1) A "proof" that N^N-comp is enumerable.
I said that a function from N to N, is computable (and thus in N^N-
comp), if there is a recipe explaining how to compute it.
But this means that there has to be a language in which we can
describe or encode that explanation. A language is a set of finite
expressions build from some finite alphabet. But we have seen that the
set of finite expressions build on an alphabet (which is always a
finite set) is enumerable. Those expressions, corresponding to the
explanation describing the recipe for a computable function, will
constitute a subset of the set of all expressions, and is thus
enumerable. So N^N-comp is enumerable.
2) A "proof" that N^N-comp is NOT enumerable.
Suppose N^N-comp is enumerable, and let f_n be such an enumeration,
with n in {0, 1, 2, ...}. Consider the diagonal function g defined by
g(n) = f_n(n) + 1. All f_n are computable, and surely "+ 1" is
computable, so g is a computable function. But then g has to belong to
f_n, which enumerates the computable functions. So there is a k such
that g = f_k. But then g(k) = f_k(k) = f_k(k) + 1. But f_k is a
computable function from N to N, so f_k(k) is a number, which I can
subtract on both side, so 00 = 1. So N^N^comp is not enumerable.
Well, there is a problem, isn't it? N^N-comp cannot be both enumerable
and non enumerable. So one of those proofs has to be wrong. Which one?
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Thu Sep 17 2009 - 16:27:23 PDT