Le 11-juin-06, à 08:49, Tom Caylor a écrit :
>
> Bruno Marchal wrote:
>> ...
>> It looks like g is computable isn't it. All fn are computable and can
>> be computed on each n, and certainly adding one ("the + 1") is
>> computable too. Right?
>>
>> Well, if you say "all right" here, we are in trouble. Because if g is
>> really computable, then g is in the sequence of all computable
>> functions fi. But then *there is* a k such that g = fk, and then g(k)
>> is equal to both fk(k) and fk(k)+1, and that gives 0 = 1, by
>> substracting the well-defined number fk(k).
>>
>> So g just cannot be a computable!
>>
>> How could g looks like being computable? It is true that all fn are
>> computable, and it is obviously true that "+ 1" is computable.
>> So, the only thing which is not computable is .... the bijection
>> itself, between N and the fi.
>>
>> It is the correspondence:
>>
>> 1 --- f1
>> 2 --- f2
>> 3 --- f3
>> 4 --- f4
>> ....
>>
>> which is NOT computable! There is just no algorithm which can generate
>> the sequence of codes of the computable functions from N to N. So,
>> although each fn is a computable function (from N to N), you cannot
>> diagonalize it for getting g, because to compute g on n, g(n) you need
>> to generate the n first programs corresponding to f1, f2, f3, ... fn,
>> and then apply it to n (and then add one), but you just will never
>> been
>> able to give me a finite set of instructions for doing that. If {f1,
>> f2, f3, ...} are all computable function from N to N, and if the
>> sequence is complete (con,tains all such function) then g, although
>> mathematically well defined, is just not programmable.
>>
>
> Here, I would think that to compute g(n), you would only have to
> generate fn and apply it to n and add one. In saying that you have to
> "generate the n first programs", perhaps you are looking ahead to the
> Universal Dovetailer starting at f1 which is the smallest program, etc.
> But if we are just considering the math/definitions here, I'd reason
> differently to show that the bijection is not computable. It seems
> that the way to prove that g is not computable, we could show that one
> (or both) of the following is false:
>
> 1) g can be specified in a finite number of symbols.
> 2) g can be executed in a finite number of steps, given any single
> input.
>
> I think that #2 above is actually true. To compute g(n), you just
> compute fn(n) and add one (like you said). Since fn can be executed in
> a finite number of steps, then #2 follows. Even if you had to compute
> all of the fi from 1 to n in a dovetailer fashion, it would still
> compute g(n) in a finite time, since all of the fi's are computable. I
> guess even if this was the Universal Dovetailer computing the fi's
> interspersed with non-computable Fi's, it would still compute the fi's
> in a finite amount of time, along with a finite amount of the
> non-computable Fi's computation (even though it will not finish the
> Fi's computation).
>
> On the other hand, I think that #1 above is false. This is because, in
> order to specify g as a bijection from N to N, you need an infinite
> number of symbols: you need *all* of the programs {f1, f2, f3, ...},
> which is a countably infinite number of finite programs, which added
> together makes a countably infinite number of symbols. Am I off track?
I think you are a little bit off the track here (and less in your other
post).
Let us be specific (also for the others).
Let us continue to write f1 f2 f3 f4 f5 f6 f7 ... for the sequence of
total computable functions.
Let us continue to write F1 F2 F3 F4 F5 F6 F7 ... for the sequence of
partial computable functions (this includes the fi but in a hidden
way).
Let us write, as usual, g for the diagonalization of the fi, and G for
the diagonalization of the Fi.
So: g(n) = fn(n)+1; and G(n) = Fn(n)+1
Now g cannot be computable, it would be total and it would belongs to
the sequence fi, and thus there would be a number code k such that g =
fk, and then fk(k) = fk(k)+1, and then 0 = 1 by substracting the well
defined number fk(k). Obviously each fn(n) is computable, and adding
one is computable, so only the bijection between the fi and N can be
the source of uncomputability. Conclusion the bijection between i and
fi, although well defined mathematically, is not computable.
Now, if we accept Church thesis, then by definition all the total
function are in the sequence F1 F2 F3 F4 ... But the sequence Fi is
mechanically generable (just do it on your favorite programming
language), and thus G is programmable, (G(n) = Fn(n)+1; note the
capital!) but then G is programmable and thus belongs to the Fi, and
thus you can find k, the number code of G, and then G(k) = Fk(k) =
Fk(k)+1, but this can be ok only if Fk(k) is undefined.
>
>>
>> BUT THEN .....
>>
>> Saying this, it could look like the Universal Dovetailer is still in
>> peril. But I have given you the shape of the solution when I show you
>> the proof of the existence of a irrational number which exponentiated
>> to an irrational number gives a rational number. That precise problem
>> is irrelevant, but the non constructive reasoning I did to prove it is
>> very relevant here. I was telling that there exist some mathematical
>> object, but I was unable to give it. I was only able to give you a bow
>> with the shape
>>
>> { a b }
>>
>> telling you the "solution" was in that box (but not saying if it was a
>> or if it was b).
>>
>> The same here, but with an infinite box. I cannot generate
>> mechanically
>> the set {f1, f2, f3, ...} of computable functions, but there is still
>> hope (Church Thesis CT will just express that hope) that I can
>> generate
>> some BIGGER set, containing all computable functions AND MANY OTHER
>> THINGS TOO. The hope is that the OTHER THINGS will help us escaping
>> the
>> diagonal contradiction.
>>
>> Well, actually CT says more: it says not only that there is a
>> universal
>> language/machine, but that fortran is such a one! And fortran programs
>> are fortran generable, so I can generate a sequence of all fortran
>> one-variable program F1 F2 F3 F4 F5 F6 F7 F8 .... ("all" means that
>> soon or later this sequence goes trough any fortran programs: it is of
>> course an infinite set)
>>
>
> Here, the Fi's are all still computable but not necessarily from N to N
> (i.e. total). Right?
Yes. They are called partial computable functions, although it would
have been better to call them computable partial functions. But I
prefer to always stick to the most used nomenclature.
The Fi are written \phi_i (in latex), but I will write Fi for it in
the mail (and Wi will denotes their domain).
>
> Why is it that we are interested only in total computable functions?
> The first paragraph in my previous post, on "motivation", addressed the
> motivation for computable, but why total? Do total functions have some
> attribute that is required in your comp?
The total fi are an important subset of the partial Fi. It is really
the Fi which are important, although the sequence of fi will be play a
rather important "second" role: the role of what George Levy called
sometimes the *first person plenitude* and which will play the role of
the arithmetical interpretation of the third Plotinus' hypostases (the
Soul!). I don't want anticipate too much (the soul comes after the
"terrestrial" and "divine" intellect captured by G and G*.
Nevertheless, intuitively, you can imagine that if you are working with
a powerfull NON-UNIVERSAL subprogramming language you will keep control
on your "software processing", and you can still extend it into the
tranfinite as we have done with the successive sequences of (total)
growing functions.
The first person is not only incorrigible, she want have complete or
total control of her (growing) universe!
And this is by the way what conventional computer (as opposed to
artificial intelligence) use consist in: we don't want our execution
going in an unpredictable loop of infinite computation, even when
dealing with streams (although I don't want to tackle them at this
stage). Conventional computing is "first person" at the start. In
artificial intelligence programming, we are no more trying to conceive
a controllable self-extension of ourself, but we hope that the program
will self-extend itself by itself and thus become autonomous (it is
almost a contradictory goal: we want the machine going to surprise us
in some way and so we are open (up to some economic point!) to let
ourself loosing control. Life, and everything creative or interesting
lives on the border between the controllable and the uncontrollable.
Another thing of interest about the total computable functions is that
they are are equivalent with the constructive, or computable, recursive
(all those terms are synounimous with CT) *real*. Indeed a computable
real number can be defined (with CT) as a real such that its decimals,
or its continuous fraction coefficient (for those who knows what it is)
are computable, and I guess you can see how to code it by a total
computable function: for example 10*PI = 31,41592...can be coded by the
computable function:
{(0, 31) (1, 4) (2, 1) (3, 5) (4,9) (5, 2) ...}
Inversely, total computable function can represent computable real
numbers, and the set R of total computable functions is quite often
referred as the computable reals. It represents the maximal
controllable thing. It is thus ironic, but highly informative that you
cannot generate it all, unless you accept to generate hidden among them
the *other beast" the partial computable functions. Those partial
computable functions do not capture the computable reals which all have
their decimals computable.
>
>> So, given that the sequence F1, F2, F3, F4, F5, ... is generable, the
>> corresponding diagonal function G defined by
>>
>> G(n) = Fn(n) + 1
>>
>> *is* programmable in fortran. So there *is* a k such that G = Fk
>>
>> And what will happen if I apply G on its own number-code k?
>>
>> Just this: your machine will crash! The fortran interpreter will go in
>> loop or in an infinite computations.
>>
>> Well, in some formal sense I will get G(k) = G(k) + 1. But I can no
>> more substract G(k) on both sides like we have always do at that
>> stage,
>> because G(k) is just not a well-defined number.
>> It looks like the OTHER THINGS are the function from a subset of N to
>> N. Functions, now, if we want to associate them to the fortran
>> programs, can be only partially defined functions.
>>
>> So I can still hope the sequence Fi of Fortran programs goes trough,
>> among OTHER THINGS, all computable functions everywhere defined, but
>> the price will be that I will got the undefined programmable functions
>> by the same token.
>>
>
> I can see why a *non-computable* function would run forever, because if
> it is generatable it must admit a finite description, so the only other
> attribute of computability it can fail to have is finite execution.
>
> But why would a computable partial function run forever?
At least we know for the partial computable G. If G(k) = Fk(k) does not
run for ever, it will stop on a number Fk(k) equal to Fk(k)+1.
G(k) run forever because 0 is different of 1.
Or if you prefer: G(k) run forever unless 0 is different of 1, and then
experiments (*) provides confirmation that 0 is different from 1 (but
honestly I'm joking here).
(*) try it, well if you have some time and know some not to complex
programming language, perhaps we could do it on the list here either
with Python or the combinators?. I think aloud.
Now if G(k) run forever, you think that you can stop it by some
"Ctrl-Q" key, or escape key, and somehow you think G crashed, not your
computer! Well, the point of the diagonalization is that you will never
succeed in finding a complete set of keys or a 100% safe operating
system such that any non terminating procedure can end so easily,
unless you accept keys like cut the power, or send an asteroid on the
planet! But actually even such instruction can be defeated by
diagonalization, once you take the "whole system" into account in the
(universal) simulation.
The diagonalization can show why in Computerland there is no universal
vaccine against the many kind of virus and organisms.
> Why would it
> even crash?
Because if you run "G(k)" on your universal machine (including the
operating system) in which you have defined G, you will have to reboot
the system.
> Wouldn't the Universal Dovetailer just generate the
> program for that function and run it on all numbers that it is defined
> on?
Yes, for each programs, the one corresponding to the sequence of the
partial computable functions Fi. Let us write them Pi. The UD runs
one step of P1 on 1, then one step of P2 on 1, then the seond step of
P1, on 1, then the second step of P2, etc. using a good bijection
between N and N^3, it can dovetails on the n of Pn, the number of
steps, and the inputs, so as not being trapped into some *particular*
infinite computations. Somehow it trapped itself in all finite and
infinite computations.
When I say a computer (alias a turing universal machine, or simply,
given that we assume CT, a universal machine) crash, I am not saying it
is the end!
The universal dovetailer is born crashed, if I can say. It compute
nothing. More precisely, and extensionally, it computes the empty
partial computable function, the one with the graph having no couples!:
{ }
The DU has no input and no outputs and computes for ever. Intensionally
(as opposed to extensionally) The DU goes through all possible
computations.
>
> When we are jumping from functions to programs crashing, I am getting
> confused.
Here a partial computable function Fi is undefined at n if her program
i "crashes" on n.
And I propose to define equality of partial computable function by
Fi = Fj if they have the same domain and the same value on that domain.
> It would seem that a program running forever and a program
> crashing (stopping without the right answer) would have different
> effects on a Universal Dovetailer.
Why? There is no effect of the DU by the DU. It runs all programs, and
of course all the ways programs can crash, including asteroids!
The DU itself cannot crash in some sense, and btw this shows the DU is
not a universal machine but we knew it: "{}" would be a quite
degenerate computable universal function.
Oops I realize I am calling the UD DU. Sorry. DU is the french for UD.
Dovetelleur Universel (Brussels' "thesis"), or Déployeur Universel
(Lille's thesis). (Universal Deployment). Les deux se disent (you can
say both) :)
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
-~----------~----~----~----~------~----~------~--~---
Received on Mon Jun 12 2006 - 11:51:53 PDT