Le 11-juin-06, à 02:00, Tom Caylor a écrit :
> If I may, I'd like to revisit why (the motivation) we are considering
> functions from N to N. I guess it is because all computations are
> equivalent to taking a number from N (i.e. each uniquely meaningful
> input of a computation can be put into a one-to-one correspondence with
> a number from N, because there are countably many inputs) and produce a
> number from N (same reasoning for output as for input).
Yes, although the way you put it can be misleading. All computations
comes from an application of some program on some input (always a
positive integer or zero, I mean a natural number; or anything codable
by a natural number). If the program P codes a total (everywhere
defined) one-variable-function, then for each n each computation P(n)
will stop. Note that to compute a function of one variable on *all*
inputs we need to run it on all numbers, or at least to write a program
generating its graph (set of all its couple of input-outputs, see below
for examples).
> I guess that
> you are interested in computations because this is what your comp is
> based on. Your "sufficient level of substitution" is a description of
> a person with countably many symbols. Right?
Even with a finite number of symbols. Think of the motto: believing in
comp is the belief that you can save your soul on a disk, or even in a
(voluminous) book. Two symbols are enough. Well, actually one symbol is
enough, because you can write a number n just with n strokes.
>
>> Note that a (one) computable function is an infinite object, but
>> giving
>> that that infinite set is computable and generable from a code, the
>> set
>> of computable functions is in bijection with the set of their codes,
>> which itself is in bijection with N, and so the infinite set of
>> infinite objects which are the computable function is in bijection
>> with
>> N.
>>
>
> When you say "infinite object" here, you mean that the function
> computes an infinite number of values, i.e. all the numbers in N.
> Right?
Yes. Examples,
The constant function 1 =
{(0, 1) (1,1) (2,1) (3,1) (4,1) (5,1) (6,1), (7,1) ... }
Factorial = {(0,1) (1,1) (2,2) (3,6) (4,24) (5,120) (6,720) (7,5040)
...}
Successor = {(0,1) (1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8) ...}
Identity = {(0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (6,6) (7,7) ...}
...
All functions from N to N are infinite object.
Now, a computable function got a finite name/description/code/programs,
etc. But we have just learned (by the diagonalization trick) that many
programs (in any programming language or in any universal machine
specification) does not compute total functions, but compute so-called
partial functions, = those not necessarily defined everywhere.
> Even though the function is programmed with a finite number of
> symbols, equivalent to a finite number from N. A function programmed
> with a finite number of symbols, say digits, I can think of as a finite
> number, or if I put a decimal point in front, a rational number.
Yes. I will just use the number appearing in the enumeration of the
partial functions
F1, F2, F3, F4, F5, F6, F7, ...
So I will say for example that 4 is a Godel number of the function F4.
I guess all computer user knows that all programmable function (total
or partial) will have an infinity of such godel number, because they
have (necesarily) an infinity of programs (just think about dummy
instructions). Later I will give a tool for proving this in all
generality.
> This
> is equivalent to saying that the rational numbers can be put in a
> one-to-one correspondence (bijection) with N, which is true.
Right, but I'm not sure to understand your motivation for using
rational numbers as code. Any set for which there is a computable
bijection with N will do, so let us keep the simplest one: N. OK?
> We can
> see that this does not remain true if we allow for infinite programs,
> i.e. a program defined by an infinite number of symbols/digits.
In general, an infinite programs can still be written with a finite
number of symbols, like a real number can be written with a finite
number of symbols chosen among {0,1,2,3,4,5,6,7,8,9}. Of course in
general it will need an infinite number of occurences of those symbols.
It is the length of the program which is infinite.
But there is no infinite programs (in arithmetical Platonia). Of course
like Russell, you can conceive and study them but it in general the
whole motivation of the notion of programs/names/description is really
to capture something infinite by something finite.
Actually you can even consider programs based on infinite alphabets,
even of any cardinality. But I don't see any motivations unless you
want to study strongly non-comp philosophy. You will need advanced
stuff in set theory, and also you have to masterize the "finite" theory
before (so let us not try to put the car before the horse ...).
> The
> number of such programs is equivalent to the cardinality of the reals
> or the continuum.
Yes, but it is not standard to call them programs.
> So we have to keep in mind that "infinite object"
> refers to the domain of the function, not the description of the
> function. Right?
The domain, or the range or the graph. The domain of f = the set of n
such f(n) is defined, the range of f = the set of n such that there
exist m such that f(m) = n, and the graph is the set of couples like I
have illustrated above.
>> 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.
>>
>
> This seems to be a result of the fact that we have given *meaning* to
> the symbols, by specifying that the symbols have to make sense in some
> language. This seems to imply that "attributing meaning to symbols" is
> not algorithmically codable.
You are right,we will have opportunities to come back on this.
> If you could code it, then it would be
> programmable (and even computable if it halts).
> But then it would just
> be a bunch of numbers being crunched without meaning.
This is a little fuzzy for me. We will come back on this.
>
> I've been wondering about this in the background for a while, so now I
> can ask this question. OK, I think I understand everything so far.
> But... if there are functions (in the list of *all* programmable
> functions) which will run forever, and you cannot (computably?) know
> which ones they are (otherwise you could solve the Halting problem?...
We have not yet seen the halting problem. Our proof shows directly that
we cannot, computably indeed, find those codes corresponding to total
functions, *otherwize* we can enumerate them and prove 0 = 1 by
diagonalization.
> or... at least by the digaonalization reasoning you've given),
Ah! Yes, exactly. Everyone should be sure to understand this.
> then
> isn't the Universal Dovetailer going to run into one of these programs
> and run forever? Alternatively, if the UD executes the first
> instruction of each program, there are a (countably) infinite number of
> programs, so you would never get to the second instruction.
> Alternatively again, are we really allowed to sort the infinite number
> of programs so that we execute the one-instruction programs first,
> followed by the two-instruction programs, etc.? Isn't this
> non-constructive?
OK, you and Quentin have already solve this, I will not comment. Just a
little summary in two points:
1) The deep reason why we can hope (pray, bet on, ...) in the universal
dovetailer is just Church thesis which is possible thanks to the fact
the set of programmable partial(*) functions is enumerable and close
for the diagonalization procedure (unlike the case of the total
programmable function which gives a non recursively (mechanically)
enumerable subset of the partial functions.
2) But so, to execute all programs, we have to *dovetail* so that we
will not been stuck in some infinite computations.
(*) I include the total functions in the partial functions. A total
function is a particular case of a function which is defined only on a
subset of N, but here the subset is N itself. I will say a function is
*strictly* partial when it is not total.
I will try to make a summary of the main definitions and theorems.
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 - 09:53:26 PDT