Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
On Thu, Jun 22, 2006 at 11:24:22AM +0200, Bruno Marchal wrote:
>
> > Whereas I don't think it does. It can be applied in an absolute way
> > (such as you refer) or in a relative subjective way (which is how I do
> > it). In fact I make the point that absolute measures aren't meaningful
> > - there just isn't an absolutely given UTM.
>
>
> From a recursive or computationalist standpoint there is. In particular
> "absolute measure" *can* be defined up to a constant.
>
The constant, unfortunately, is infinity! What is true is that the
complexity of two strings x and y will differ by no more than a
constant independent of the strings x and y when measured by two
different machines.
But the reverse case is where the strings x and y are fixed, and the
machines variables. For any two strings x, y, it is possible to find
machines U & V that give different answers to the question K(x) > K(y).
Consequently, the universal prior is not absolute, but dependent on a
chosen U.
>
>
>
> > The dovetailing provides the simpler ensemble from which the specific
> > computation is selected. This is right there in the first
> > [Schmidhuber] paper.
>
> I don't see it.
>
Its right there on the second line of page 2 of his 1997 paper:
"Computing all universes. One way of sequentially computing all
computable universes is dove-tailing. A_1 ..."
So he does use the term dovetailer. He doesn't qualify it with
"universal", mind you I'm not entirely sure it isn't universal. Its
hard to read everything into one single line of prose. However, you
certainly have published on the UD prior to this.
>
>
> > In the second paper, the dovetailing is assumed to run on an actual
> > resource limited computer - hence the speed prior.
>
>
> But that dovetailing is not related to the universal one. Which is all
> normal given that Schmidhuber does not base his reasoning on the 1-3
> distinction. His ensemble or his "great programmer" is thus enough for
> his purpose.
>
> Bruno
>
He talks about the dovetailer on page 28 on that paper, and it is
running every possible program. He also notes that Li and Vitanyi
introduce such an algorithm (which they call SIMPLE) in Lemma 7.5.1 on
page 503.
How are these algorithms not "universal"?
--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 20-juin-06, à 06:00, Tom Caylor a écrit (replying to Norman Samish) : > > > Norman Samish wrote: >> Gentlemen: >> >> I've endured this thread long enough! Let's get back to something I >> can understand! >> >> "Why?" you'll ask. >> >> I'll reply, "Because your audience is shrinking! I've plotted the >> Audience vs. Topic, and find that, in 12.63 months, there is a 91% >> probability that, if the topic doesn't become understandable to one >> with an IQ of 120, your audience will be zero, and the only expositor >> will be Bruno. Not that there's anything wrong with that, but we >> must acknowledge that Bruno speaks a language that very few of us can >> understand. Bruno, and probably Russell and a few others, are >> clearly Homo Superior, while the rest of us are mere Homo Sapiens." >> >> You will then say, "Our discourse is meant for Homo Superior. If you >> can't stand the heat, get out of the kitchen." >> >> I'll reply, "Damn! I was hoping to learn something!" >> >> Norman Samish >> > > Norman: > > Even though the other current topic "Calculus of personal identity" has > the word "calculus" in it, I think it's an understandable and > interesting thread. And you can also start a new thread. For me, I'm > hoping to learn something, too, as long as Bruno lasts, and feels like > he's benefiting. This current topic I think is just starting to really > get good, in my view. Or it may evolve to the next level and be less > mathematical and more philosophical. Or maybe someone smarter than I > am will pipe up and make it even more interesting. Who knows what will > happen, but it's up to whoever wants to participate to make it happen. > My thoughts. I appreciate. I will solve the four diagonalization questions later (I recall them below(*). I intend also to make clearer the motivation. I was just trying to help george with Smullyan's FU "heart of the matter" but Norman is right at least on this: I should find a way to explain the general idea without being technical, and then, for those interested, I can explain the technics. It would be better for everyone, though, to ask questions once there is a unclear point. With all my respect for Norman, he reminded me those students who wait for the exams for asking questions! I do think such clarifications could help to clarify nuances between theoretical computer science notions (number, program, function, computation, ...) which are important in many other thread. For example I said recently that Kolmogorov complexity is a well defined notion, that it is a non constructive (nor computable) notion, and that it does not depend on the chosen universal machine except for a constant term. But all that presupposes importantly Church thesis. So it is not a luwe to dig on it a little more. Aarghh... Sorry for that teacher's tone it is June. Exam Month here ... :-( Bruno (*) So the question was: what does diagonalization prove on those following list of functions: 0) r1 r2 r3 r4 r5 r6 r7 r8 ... This is an arbitrary list of functions from N to N (not necessarily computable one); 1) h0 h1 h2 h3 h4 h5 h6 ... This is a list of total computable functions from N to N that we can generate mechanically (I mean we can generate their codes). It means that we can generate the codes of each hi, written in some language, and that, for some reason, we are sure that each hi is total computable. Examples: Caylor last funny enumeration; all the (transfinite collection of) sequences of growing functions we have defined in this thread (since "Smullyan Smullyan ..."); 2) f0 f1 f2 f3 f4 f5 f6 f7 ... This is a list of *all* total computable functions; 3) F0 F1 F2 F3 F4 F5 F6 F7 F8 ... This is the list of all programmable things in some "universal language" like fortran. CT asserts fortran is universal so that the total computable function fi will be dispersed *among* those Fi things, so that a universal machine can really compute all the fi, among other things. Now the same diagonalization argument proves 4 different propositions according to which list we are talking about. Which one? Before answering, I let people muse a little about what are those 4 different consequences, given that the only way to really grasp those propositions consists in rediscovering them by oneself, ... or at least in searching enough so as to be curious listening to the solutions. 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 20-juin-06, à 01:18, Russell Standish a écrit : > So we a need a name. Bitstrings is too specific, since we could also > be referring to strings from other alphabets. The word description > seems to fit the concept, and wasn't otherwise used in literature. Why not saying just "strings" then? It works on all alphabet. The term "Description" conveys the idea of finiteness, except in explicit infinite formal languages. > Whereas I don't think it does. It can be applied in an absolute way > (such as you refer) or in a relative subjective way (which is how I do > it). In fact I make the point that absolute measures aren't meaningful > - there just isn't an absolutely given UTM. From a recursive or computationalist standpoint there is. In particular "absolute measure" *can* be defined up to a constant. > The dovetailing provides the simpler ensemble from which the specific > computation is selected. This is right there in the first > [Schmidhuber] paper. I don't see it. > In the second paper, the dovetailing is assumed to run on an actual > resource limited computer - hence the speed prior. But that dovetailing is not related to the universal one. Which is all normal given that Schmidhuber does not base his reasoning on the 1-3 distinction. His ensemble or his "great programmer" is thus enough for his purpose. 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
On Tue, Jun 20, 2006 at 11:43:08AM +0200, Bruno Marchal wrote:
>
>
> Le 19-juin-06, à 15:31, Russell Standish a écrit :
>
> > I'm not so sure. At heart, I suspect he is a computationalist, however
> > what he assumes in his papers is that the universe (that we see) is a
> > single
> > specific computation selected from the dovetailer algorithm. With COMP
> > (and
> > with functionalism too) we assume that consciousness supervenes on all
> > consistent computations, which leads to your famous first person
> > indeterminism result. Schmidhuber's assumption directly implies
> > determinism (we are living inside one particular computation only).
> >
> > I do not see Schmidhuber's argument as inconsistent, but it does seem
> > to contradict COMP, so Schmidhuber may have inconsistent faiths if he
> > insists both on this argument and COMP.
>
>
> I agree here. I still don't understand why you call "description" what
> is really just a real number (or a real number from the unit interval).
Sets of descriptions are more or less isomorphic to set of real numbers, but
not actually the same. In fact there is even a difference - the strings
011... and 10 are different descriptions, but correspond
to the same real number (0.5), but this difference is only on a set of
measure 0 (rational numbers with denominator that is a power of two).
So we a need a name. Bitstrings is too specific, since we could also
be referring to strings from other alphabets. The word description
seems to fit the concept, and wasn't otherwise used in literature.
> I will try to read my Levin Solomonov literature, if only to see if we
> are just quibbling on terminology or on something more fundamental. To
> see program as prefix of infinite string is interesting if you are
> interested in Kolmogorov-Chaitin-Solovay-Martin-Löf sort of (quasi
> absolute) probability measure, like in the search of a Bayesian sort of
> ASSA Udist (which, I have often argue miss the relative self-sampling
> assumption forced by the 1-3 distinction).
Whereas I don't think it does. It can be applied in an absolute way
(such as you refer) or in a relative subjective way (which is how I do
it). In fact I make the point that absolute measures aren't meaningful
- there just isn't an absolutely given UTM.
>
> I disagree (but this I already told you) with your mention of universal
> dovetailing in Schmidhuber, given that if you select a specific
> computation there is no more need to dovetail.
The dovetailing provides the simpler ensemble from which the specific
computation is selected. This is right there in the first paper. In
the second paper, the dovetailing is assumed to run on an actual
resource limited computer - hence the speed prior.
> This is, at the least,
> pedagogically confusing. Sure, Church Thesis and Universal Machine
> should play an important role in Schmidhuber, but there is no reason to
> dovetail universally. This appears when you realize comp makes it
> impossible to attach consciousness to any specific computation
> (material or not) that is when you get the comp first person
> indeterminacy.
>
> A last note: speed prior, like in Schmidhuber second paper, seems to
> contradict the basic idea of its first paper. With notion of prior we
> can just go back to (theoretical) physics. QM is easily derivable from
> few assumptions on probability and symmetry and math, but this I take
> as cheating when asking fundamental questions. More technically the
> speed prior seems to be in contradiction with the fact that "universal
> machine" can be sped up infinitely (Blum speed up theorem). Speed prior
> would favorize *big* programs. We can come back later on this more
> technical issue.
>
Perhaps, although it is not a burning interest of mine :(
> Bruno
>
>
> http://iridia.ulb.ac.be/~marchal/
>
>
>
--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 20-juin-06, à 04:04, Norman Samish a écrit : I've endured this thread long enough! Let's get back to something I can understand! "Why?" you'll ask. I'll reply, "Because your audience is shrinking! I've plotted the Audience vs. Topic, and find that, in 12.63 months, there is a 91% probability that, if the topic doesn't become understandable to one with an IQ of 120, your audience will be zero, and the only expositor will be Bruno. I thought only politicians were interested in audience (during electoral period!). Not that there's anything wrong with that, but we must acknowledge that Bruno speaks a language that very few of us can understand. Please ask when you don't understand, unless you are not interested. I insist enough that there is no stupid questions. Perhaps, like so many (especially in france and Belgium) you get some traumatic experience with math and you did persuade yourself you cannot understand math. My experience is that people who believes they does not understand math, well in 99,% are just imagining difficulties which does not exist at all. They are too much clever! Like henry Poincare I believe mathematics is the easiest of all the fields. Human psychology is the most complex one. Bruno, and probably Russell and a few others, are clearly Homo Superior, while the rest of us are mere Homo Sapiens." I am talking to the the Machina Universalis. Todays, with the exception of those who got a highly injured brain, current universal machines are still *very* far from being as clever as the stupidest human. I bet you have just miss some definition, in which case it is all normal you miss the track. You will then say, "Our discourse is meant for Homo Superior. If you can't stand the heat, get out of the kitchen." I am addressing the most "inferior" of all the creatures, the simple mind common to all of us (but yes sometimes traumatized by teaching driven by pure competition or moral sadism. Note that, I have nothing against competition *per se*, but everything against competition for competition and form of social elitism based on it, which has lead us to some form of in-numeracy. I'll reply, "Damn! I was hoping to learn something!" Just tell us what you don't understand. Do you grasp the notion of function from N to N? Do you know what N refers to? Just ask. You have the opportunity of being in front of a math teacher who is willing to explain you the basic starting from zero. Not just because I would be so compassionned, but because later it will be capital to understand that what I say can be understandable, in some sense, by very simple machine. What are your relation with computers? Theoretical computer science is a field which you can get startling results quickly when starting from zero. This is rather uncommon. Also, we are discussing since years. It is all normal that we arrive at delicate points needing to be more specific, especially in counterintuitive-land. Come back in the kitchen Norman. You can understand the thread, and if you ask all the needed question, perhaps the audience will grow up again! Because then many other will benefit from your questions. I don't believe in non-mathematicans! Those who say "I have never understand math" are just either snobbish, or have been mentally destroyed by some mad teacher (frequent in some country). 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 19-juin-06, à 15:31, Russell Standish a écrit : > I'm not so sure. At heart, I suspect he is a computationalist, however > what he assumes in his papers is that the universe (that we see) is a > single > specific computation selected from the dovetailer algorithm. With COMP > (and > with functionalism too) we assume that consciousness supervenes on all > consistent computations, which leads to your famous first person > indeterminism result. Schmidhuber's assumption directly implies > determinism (we are living inside one particular computation only). > > I do not see Schmidhuber's argument as inconsistent, but it does seem > to contradict COMP, so Schmidhuber may have inconsistent faiths if he > insists both on this argument and COMP. I agree here. I still don't understand why you call "description" what is really just a real number (or a real number from the unit interval). I will try to read my Levin Solomonov literature, if only to see if we are just quibbling on terminology or on something more fundamental. To see program as prefix of infinite string is interesting if you are interested in Kolmogorov-Chaitin-Solovay-Martin-Löf sort of (quasi absolute) probability measure, like in the search of a Bayesian sort of ASSA Udist (which, I have often argue miss the relative self-sampling assumption forced by the 1-3 distinction). I disagree (but this I already told you) with your mention of universal dovetailing in Schmidhuber, given that if you select a specific computation there is no more need to dovetail. This is, at the least, pedagogically confusing. Sure, Church Thesis and Universal Machine should play an important role in Schmidhuber, but there is no reason to dovetail universally. This appears when you realize comp makes it impossible to attach consciousness to any specific computation (material or not) that is when you get the comp first person indeterminacy. A last note: speed prior, like in Schmidhuber second paper, seems to contradict the basic idea of its first paper. With notion of prior we can just go back to (theoretical) physics. QM is easily derivable from few assumptions on probability and symmetry and math, but this I take as cheating when asking fundamental questions. More technically the speed prior seems to be in contradiction with the fact that "universal machine" can be sped up infinitely (Blum speed up theorem). Speed prior would favorize *big* programs. We can come back later on this more technical issue. 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Norman Samish wrote: > Gentlemen: > > I've endured this thread long enough! Let's get back to something I can > understand! > > "Why?" you'll ask. > > I'll reply, "Because your audience is shrinking! I've plotted the Audience > vs. Topic, and find that, in 12.63 months, there is a 91% probability that, > if the topic doesn't become understandable to one with an IQ of 120, your > audience will be zero, and the only expositor will be Bruno. Not that > there's anything wrong with that, but we must acknowledge that Bruno speaks a > language that very few of us can understand. Bruno, and probably Russell and > a few others, are clearly Homo Superior, while the rest of us are mere Homo > Sapiens." > > You will then say, "Our discourse is meant for Homo Superior. If you can't > stand the heat, get out of the kitchen." > > I'll reply, "Damn! I was hoping to learn something!" > > Norman Samish > Norman: Even though the other current topic "Calculus of personal identity" has the word "calculus" in it, I think it's an understandable and interesting thread. And you can also start a new thread. For me, I'm hoping to learn something, too, as long as Bruno lasts, and feels like he's benefiting. This current topic I think is just starting to really get good, in my view. Or it may evolve to the next level and be less mathematical and more philosophical. Or maybe someone smarter than I am will pipe up and make it even more interesting. Who knows what will happen, but it's up to whoever wants to participate to make it happen. My thoughts. Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Gentlemen: I've endured this thread long enough! Let's get back to something I can understand! "Why?" you'll ask. I'll reply, "Because your audience is shrinking! I've plotted the Audience vs. Topic, and find that, in 12.63 months, there is a 91% probability that, if the topic doesn't become understandable to one with an IQ of 120, your audience will be zero, and the only expositor will be Bruno. Not that there's anything wrong with that, but we must acknowledge that Bruno speaks a language that very few of us can understand. Bruno, and probably Russell and a few others, are clearly Homo Superior, while the rest of us are mere Homo Sapiens." You will then say, "Our discourse is meant for Homo Superior. If you can't stand the heat, get out of the kitchen." I'll reply, "Damn! I was hoping to learn something!" Norman Samish --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
On Mon, Jun 19, 2006 at 11:12:52AM +0200, Bruno Marchal wrote:
>
> ?
I'm not sure which bit you were having trouble with. A description is
an infinite length bitstring. It is therefore equivalent to a point in
the unit interval [0,1] (modulo a little bit of funny stuff on a set of
measure zero). The uniform measure on the unit interval is equivalent
to the Levin-Solomonoff distribution, or universal prior, were sets of
descriptions are partitioned by a UTM. Information (or complexity) is
simply the negative logarithm of the set's measure:
I = -log mu(S)
Clearly, the set of all descriptions is equivalent to the unit
interval, and has I=0. This is the zero information object. Subsets of
the unit interval have smaller measure than 1, so the equivalent sets
of descriptions have larger information content.
A finite string can be thought of as a set of descriptions that share the
same finite prefix, and so have I <= length of string.
>
>
> > I think he
> > is wrong too, and agree with you, however I'm not so sure his
> > arguments are this easy to dismiss.
>
>
>
> Which argument in particular?
>
The speed prior argument (advanced in his "Algorithmic Theories of
Everything") paper.
>
>
>
>
> > It is related again to the ancient
> > debate on ASSA vs RSSA - Schmidhuber's argument works if you assume
> > just one computation is selected as your universe, which is rather
> > contrary to functionalism (and COMP).
>
> Remember Schmidhuber assumes comp.
>
I'm not so sure. At heart, I suspect he is a computationalist, however
what he assumes in his papers is that the universe (that we see) is a single
specific computation selected from the dovetailer algorithm. With COMP (and
with functionalism too) we assume that consciousness supervenes on all
consistent computations, which leads to your famous first person
indeterminism result. Schmidhuber's assumption directly implies
determinism (we are living inside one particular computation only).
I do not see Schmidhuber's argument as inconsistent, but it does seem
to contradict COMP, so Schmidhuber may have inconsistent faiths if he
insists both on this argument and COMP.
I'm thinking out loud here, so I welcome comments and corrections, of course.
>
> Bruno
>
> http://iridia.ulb.ac.be/~marchal/
>
>
>
--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 18-juin-06, à 06:35, Tom Caylor a écrit : > I don't know much about Church Thesis, but I want to learn more. Even > though it seems easy to recite, as in the existence of a Universal > Language, it seems very deep and mysterious. I think so. > Almost like stating a > Unified Field Thesis. I agree. > You just state it, and then see where it leads, Yes. > at least as far as you are able to follow it. ? I mean we follow it. Comma. Of course in case we get a contradiction we will abandon it. If we get just weirdness, well, personnaly I follow Deutsch dicto: let us take our theory seriously, it is the only chance to make them wrong ... > > But on the surface, the very prospect of someone trying to disprove > Church Thesis is funny to me. I think so too. To be honest, one paper on continuous (quantum) teleportation made me doubt on Church thesis during several hours ... but no more. > Perhaps I am missing something. To > think of a counterexample seems like a contradiction. Didn't Turing > describe his Turing machine as equivalent to what a mathematician can > do with a pencil and paper? But the counterexample would have to be > something that someone (probably a mathematician ;) could think up! So > a counterexample would be a function F that > > 1) a mathematician could think up > 2) without using a pencil and paper! Oooo. Not really, because Church thesis asks for the "pencil and paper". So a counterexample of Church thesis would be a FINITE description of how to compute a function, description which can be send by radio wave or by pedestrian mailing and understandable by human but not by computer. The main problem is that we cannot define really what we mean by "FINITE". It is as hard to define the term "finite" (without using its meaning implicitly) than the term "consciousness". (and in my opinion the term "matter" is still more complex, and that almost follows from comp in fact, cf UDA). > > Actually, I am aware that people like Penrose actually say that > something is going on in the brain (quantum-mechanically) that could > never happen on a piece of paper. After having read his cute "road to reality" book I think he has changed his mind. > But putting it in the above way > makes it sound funny. And I think actually Penrose might claim that > the function G is just such a function. Penrose knows perfectly well that no known human can compute g. (G can be compute partially and is in general undefined in a predictible way (for example on its own code)). So Penrose has concentrated his non-comp argument on the formal version of that argument, that is on Godel second incompleteness theorem. He needs to say that humans know their are consistent and thus escape the godelian fate, but Judson Web already refutes such attempts. I propose we come back to this when we will go the fact 1 and to to the facts I and II (cf Smullyan). We need the notion of theory for doing that. > He doesn't say much in his > Shadows of the Mind about Church Thesis. Interesting. I will try to reread what he says about Church thesis. > But, Bruno, your posts on > this seem to be assuming Church Thesis and then seeing what the > conclusion is about G, which is perhaps the opposite of Penrose. Sure. remember I put explicitly Church thesis in the definition of computationalism. Penrose postulates non-comp at the start (of its two best-sellers book). penrose uses Godel as an argument for non-comp. I take it as the most lucky possible event for the mechanist, because it saves mechanism from reductionism. With a good understanding of Church thesis you can realize that comp is the most anti-reductionist philosophical standpoint possible. Church thesis and comp are the rationalist road to the mystical notion of unconceivable freedom. Unfortunately, although we have practice rational mysticism for a millenium (from Pythagoras to Proclus), we have (irrationally, after mixing religion and state) separate them since about 1500 years. > > Do you think that there is a possibility that Church Thesis has the > same status as the Continuum Hypothesis in this sense: the Continuum > Hypothesis has been shown to be independent of the axioms of > arithmetic, i.e. both the truth and the falsity of the Continuum > Hypothesis is consistent with the axioms of arithmetic. You mean with the axioms of Zermelo Fraenkel set theory, I guess. (The continuum hypothesis is not even expressible in first order axiomatized arithmetic, like Peano). > Could the > Church Thesis be independent of... what?... The problem is: what body > of knowledge is there that is in the pursuit of truth, and is also > intimately affected by the Church Thesis? The mind-body problem, I > guess. Could the Church Thesis be independent of the mind-body > problem? Quite interesting question. In 1922, Emil Post, the real first discoverer of "Church thesis" (except perhaps for Babbage
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 18-juin-06, à 01:55, Russell Standish a écrit : > A description is an infinite length (bit)string (bits in brackets, > because any other alphabet will do also). This use does sometimes fly > in face of what people expect, Certainly. > but I define this explicitly - it is a > useful term. > > I'm just using the term "object" informally. The zero information > object is in > fact a set of descriptions. ? > >> I can understand "an infinite length object", like some putative >> infinite physical universe for example. I can understand "a zero >> information description"; for example the empty program or some empty >> theory (I will address "theories" later though). It is harder for me >> to >> understand what can be the use of infinite description or a >> zero-information object. >> > > Only sets of descriptions (remember infinite length bitstrings) can > have finite information. ? > > This looks like a terminological issue... ? >> I think the only trouble with Schmidhuber, and then with many people >> to >> be sure, is that they find hard to take seriously enough the >> distinction between first and third person point of views. >> The UD is a (finite) program, and when it runs, like any program >> running on some universal machine, it uses only at each time a finite >> piece of its (potentially infinite) tape, etc. >> Now, indeed, once you grasp that the probabilities of relative >> histories relies on the first person point of view, the case can been >> made that the infinite computations have a higher measure that the >> finite one, so that somehow physicalities emerges from the infinite >> set >> of those infinite (crashing-like) computations. >> > > You're talking here of his speed prior argument of course. ? (I was just saying that Schmidhuber miss the 1/3 distinction). > I think he > is wrong too, and agree with you, however I'm not so sure his > arguments are this easy to dismiss. Which argument in particular? > It is related again to the ancient > debate on ASSA vs RSSA - Schmidhuber's argument works if you assume > just one computation is selected as your universe, which is rather > contrary to functionalism (and COMP). Remember Schmidhuber assumes comp. 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
James,
Le 17-juin-06, à 20:10, James N Rose a écrit :
>
> Bruno,
>
>
> Sometimes gedankenexperiments - or even theoretical
> contemplations - include unvoiced/unconsidered
> presumptions and biases that a system may not
> be self-aware of. Benj Whorf brought this aspect
> of systemic nature into consideration, in the 1930's,
> when he applied Einstein/Reichenbach notions of
> 'relativity' to the "subjective" field of language
> and linguistics. {Reichenbach called his analysis
> of it (1927) vis a vis gravity, Theorem Theta.}
>
>
> Several years ago, I proposed that attention
> should not be paid to the Halting Problem, but
> instead be paid to what comes after. Meaning,
> not to the effective information production
> of the computation run, nor to any activity
> resulting from the computation run .. but rather
> to this: future re-activation of 'the' or any
> computation process.
>
> We exist in a universe that is always 'in process'.
> Even if some operations 'halt', the essential nature
> of co-present simultaneous systems is that dynamics
> are so 'on-going' that the main priority is on
> re-enacted/re-established/re-initiated actions.
>
> No systems are 'pure isolates' .. there are always
> and importantly: relationships of context, continuity,
> and recursion.
>
> Placing the Turing or Church or any other devised
> 'closed conditioned system' on the table of evaluation,
> is to miss THE critical group of parameters, that no
> 'idealized' parameters group includes.
I argue that the contrary is true. I have no evidence that you did
follow the argument. You are not enough clear that I can counter-argue
here.
>
> Current closed-set evaluations are fundamentally:
> utilitarian, task-oriented, single assignments/missions.
?
>
> But the statespace of the universe is open, relative,
> re-accessible, and re-instantiable .. WITH .. all
> systems being vulnerable to correlary/additional
> instructions.
Which universe?
>
> It makes no nevermind if a system or computation
> 'halts' or not.
>
> The crucial things is whether 1) if a computation
> halts .. what are the conditions for re-instantiation?,
> and 2) if it never self-halts .. then what parameters
> are present to induce halting? (a) sufficient utility of
> incomplete data, (b) eradication due to untimely utility,
> (c) exhaustion of operational resources, (d)
We have proved that such question cannot be answer in any systematic
way.
>
>
>
> You see Bruno, mathematics carries a self-blinding
> presumption: Perfect universal information distribution/access.
>
> "Sequential operations" functions are an attempt to
> evaluate non-instantaneous information processing.
>
> And physical reality includes both AND contraints
> unique to both - but interactive with the other
> domain.
What do you mean exactly by "physical reality"?. In this list such an
expression is ambiguous. Are you talking about the observables which
are emerging from the relation between numbers (if comp is true
together with the reasoning I am trying to convey) or about some (non
comp) materialist theory?
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno Marchal wrote: > Le 15-juin-06, à 13:53, Tom Caylor a écrit : > > > OK. I think I understand what you are saying, on a surface level. Of > > course a surface level will never be able to expose any contradictions. > > I'm just riding this wave as long as I can before deciding to get off. > > > > It seems that there are very deep concepts here. We are standing on > > the shoulders of computability giants. I think it would take a Godel > > or a Church or Turing to find any problem with your whole argument, if > > there is any. My feeling is that any "problem" is actually just lack > > of deep enough insight, either on the part of the attempting-refuter of > > the argument, or on your part, or both. > > > > By the way, I am also cognizant that what you are covering here > > actually is pretty standard stuff and actually has been pored over by > > the giants of computability. So like I said, I'm riding the wave. > > > > On a certain level, it bothers me that Church's Thesis is said to not > > have any proof. But maybe it is sort of like Newton's gravity. It is > > just a descriptive statement about what can be observed. And yet... we > > still don't really understand gravity. Here we are at the level where > > all there is is falsifiability. > > OK. Note that Church thesis has a unique status in math. I will come > back on this. > > > > And, by the same diagonalization > > argument, you'd have to be God to falsify this "stuff". > > Ah... but here you are wrong. Church thesis, although not entirely > mathematical, still less physical, is completely refutable in the sense > of Popper (and thus "scientific" in the "modern" acceptation of the > word). To refute Church thesis it is enough to find a function F such > that you can show: > > 1) F is computable, and > 2) F is not Turing emulable. > Some people, like Kalmar, has thought they got such a function, but > this has been rebuked. > I don't know much about Church Thesis, but I want to learn more. Even though it seems easy to recite, as in the existence of a Universal Language, it seems very deep and mysterious. Almost like stating a Unified Field Thesis. You just state it, and then see where it leads, at least as far as you are able to follow it. But on the surface, the very prospect of someone trying to disprove Church Thesis is funny to me. Perhaps I am missing something. To think of a counterexample seems like a contradiction. Didn't Turing describe his Turing machine as equivalent to what a mathematician can do with a pencil and paper? But the counterexample would have to be something that someone (probably a mathematician ;) could think up! So a counterexample would be a function F that 1) a mathematician could think up 2) without using a pencil and paper! Oooo. Actually, I am aware that people like Penrose actually say that something is going on in the brain (quantum-mechanically) that could never happen on a piece of paper. But putting it in the above way makes it sound funny. And I think actually Penrose might claim that the function G is just such a function. He doesn't say much in his Shadows of the Mind about Church Thesis. But, Bruno, your posts on this seem to be assuming Church Thesis and then seeing what the conclusion is about G, which is perhaps the opposite of Penrose. Do you think that there is a possibility that Church Thesis has the same status as the Continuum Hypothesis in this sense: the Continuum Hypothesis has been shown to be independent of the axioms of arithmetic, i.e. both the truth and the falsity of the Continuum Hypothesis is consistent with the axioms of arithmetic. Could the Church Thesis be independent of... what?... The problem is: what body of knowledge is there that is in the pursuit of truth, and is also intimately affected by the Church Thesis? The mind-body problem, I guess. Could the Church Thesis be independent of the mind-body problem? Tom > Eliot Mendelson has argued that CT is provable, and sometimes I share a > little bit that feeling. I did believe that CT is provable in "second > order arithmetic" for a time because it did seem to me that CT relies > above all on the intuition of the finite/infinite distinction. But then > it could still be subtler than that, and I am not sure at all CT could > really be proved. > > Note that I talk only on the classical Church thesis, not about its > intuitonistic variants, which I do believe are false for the first > person associated to the machine (and this has been partially confirmed > by a result due to Artemov which shows that some "computabiliy version" > of constructive mathematics (like the so called Markov principle) is > false in S4Grz (with quantifiers). But intuitionist CTs really asserts > a different thing. The only roles intuitionistic CTs have in my work > are for the explanation of why (first person) machine find so hard to > say yes to the doctor and also to clarify the non-constuctivity feature > of the "OR" in "Wa
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno Marchal wrote: > Le 15-juin-06, à 18:40, Tom Caylor a écrit : > > > > > > > Bruno Marchal wrote: > >> > >> 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. > >> > > > > OK. You've shown by contradiction that g is not computable. I was > > just trying to go back to the definition of computable to see which > > part of the definition is violated. I think I overlooked the fact that > > you alluded to the answer to this question when you said "...you just > > will never been able to give me a finite set of instructions for doing > > that". I.e. g violates the finite description part of computability. > > I think Brent Meeker was trying to get at this idea, too, in answer to > > your diagonalization explanation in 2001. > > > > http://www.mail-archive.com/everything-list@eskimo.com/msg01002.html > > > > But both then and now, you said that this is not the right reason, and > > then you went on to repeat the proof by contradiction, which we already > > understand. > > You have perhaps miss the difference between two resembling proof. I > think A summary will be necessary. It should be easy because the proofs > are short. > > > > > If finiteness does not correspond with the reason for > > non-computability, this implies that there are g's formed by this > > diagonalization method, which have a finite description, but that take > > an infinite time to execute (thus fulfilling the definition of > > non-computable). > > Are you talking about the diagonal function g build on from the set of > all fi, and which is not computable, or about the G get from the Fi, > which is partial computable, or about some given effective enumeration > of total function (where we have used also the letter fi)? > Or just wait for a summary where the proposition will be numerated for > the sake of future use of them. Well here apparently you were talking > about the Fi. > > > > > So apparently we are still missing something. You need to tell us > > *why* this is not the right reason. The set of instructions for g is > > precisely a big "case" statement (if you will) on n, like this: > > > > switch n: > > begin > > case 1: > > set of instructions for f1: > > case 2: > > set of instructions for f2: > > case 3: > > set of instructions for f3: > > ... > > end (after an infinite number of cases) > > > > This is an infinitely long program. You need the whole program to > > define g, not just the portion you need for a given input. Is there a > > finite version of g? I don't see how. > > But here you talk distinctly about the fi. > if your fi denotes all the total computable functions, then, what we > have proved, is that not only your "program" for g would be infinite, > but, above all, could not be generated by any computational process: > you cannot generate the sequence of all, and only all, total computable > function f1, f2, f3, ... > CT is the statement that the fi are among the Fi, so that you can > generate computably a superset of the fi. > > Bruno > > http://iridia.ulb.ac.be/~marchal/ Yes. I am talking about the fi in all of the above. I think we are actually in agreement about this. I understand the argument, given the acceptance of the Church Thesis. Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
On Thu, Jun 15, 2006 at 04:29:18PM +0200, Bruno Marchal wrote:
>
>
> Le 14-juin-06, à 07:31, Russell Standish a écrit :
>
> >
> > On Mon, Jun 12, 2006 at 03:52:15PM +0200, Bruno Marchal wrote:
> >>
> >> 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.
> >
> > This is an interesting comment, that I hadn't appreciated before. The
> > Plenitude I study has infinite length "description", precisely because
> > this plenitude is the zero information object.
>
>
> Could you explain what is your conception of the relation between a
> description and an object?
A description is an infinite length (bit)string (bits in brackets,
because any other alphabet will do also). This use does sometimes fly
in face of what people expect, but I define this explicitly - it is a
useful term.
I'm just using the term "object" informally. The zero information object is in
fact a set of descriptions.
> I can understand "an infinite length object", like some putative
> infinite physical universe for example. I can understand "a zero
> information description"; for example the empty program or some empty
> theory (I will address "theories" later though). It is harder for me to
> understand what can be the use of infinite description or a
> zero-information object.
>
Only sets of descriptions (remember infinite length bitstrings) can
have finite information.
This looks like a terminological issue...
>
>
>
>
> >
> > However, computable things are indeed finite in size, which implies
> > that the arithmetical Platonia is smaller, and consequently a richer
> > set of things.
> >
> > The universal dovetailer, however, executes everything in the infinite
> > bitstring Plenitude does it not, or is this a misunderstanding of
> > Schmidhuberian proportions?
>
>
>
> I think the only trouble with Schmidhuber, and then with many people to
> be sure, is that they find hard to take seriously enough the
> distinction between first and third person point of views.
> The UD is a (finite) program, and when it runs, like any program
> running on some universal machine, it uses only at each time a finite
> piece of its (potentially infinite) tape, etc.
> Now, indeed, once you grasp that the probabilities of relative
> histories relies on the first person point of view, the case can been
> made that the infinite computations have a higher measure that the
> finite one, so that somehow physicalities emerges from the infinite set
> of those infinite (crashing-like) computations.
>
You're talking here of his speed prior argument of course. I think he
is wrong too, and agree with you, however I'm not so sure his
arguments are this easy to dismiss. It is related again to the ancient
debate on ASSA vs RSSA - Schmidhuber's argument works if you assume
just one computation is selected as your universe, which is rather
contrary to functionalism (and COMP).
Cheers
--
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno,
Sometimes gedankenexperiments - or even theoretical
contemplations - include unvoiced/unconsidered
presumptions and biases that a system may not
be self-aware of. Benj Whorf brought this aspect
of systemic nature into consideration, in the 1930's,
when he applied Einstein/Reichenbach notions of
'relativity' to the "subjective" field of language
and linguistics. {Reichenbach called his analysis
of it (1927) vis a vis gravity, Theorem Theta.}
Several years ago, I proposed that attention
should not be paid to the Halting Problem, but
instead be paid to what comes after. Meaning,
not to the effective information production
of the computation run, nor to any activity
resulting from the computation run .. but rather
to this: future re-activation of 'the' or any
computation process.
We exist in a universe that is always 'in process'.
Even if some operations 'halt', the essential nature
of co-present simultaneous systems is that dynamics
are so 'on-going' that the main priority is on
re-enacted/re-established/re-initiated actions.
No systems are 'pure isolates' .. there are always
and importantly: relationships of context, continuity,
and recursion.
Placing the Turing or Church or any other devised
'closed conditioned system' on the table of evaluation,
is to miss THE critical group of parameters, that no
'idealized' parameters group includes.
Current closed-set evaluations are fundamentally:
utilitarian, task-oriented, single assignments/missions.
But the statespace of the universe is open, relative,
re-accessible, and re-instantiable .. WITH .. all
systems being vulnerable to correlary/additional
instructions.
It makes no nevermind if a system or computation
'halts' or not.
The crucial things is whether 1) if a computation
halts .. what are the conditions for re-instantiation?,
and 2) if it never self-halts .. then what parameters
are present to induce halting? (a) sufficient utility of
incomplete data, (b) eradication due to untimely utility,
(c) exhaustion of operational resources, (d)
You see Bruno, mathematics carries a self-blinding
presumption: Perfect universal information distribution/access.
"Sequential operations" functions are an attempt to
evaluate non-instantaneous information processing.
And physical reality includes both AND contraints
unique to both - but interactive with the other
domain.
James
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 17-juin-06, à 07:56, Stathis Papaioannou a écrit : Bruno, I'll rephrase the problem - let me know if I get it wrong. It is proposed that all the functions f with certain attributes "A" be enumerated in a list: f1, f2, f3 etc. It looks like "A" in the example under consideration means "all the computable functions", but in fact there is a further implicit restriction: the list can only contain all the computable functions which will fit into the labelling scheme chosen for the list. If I remember correctly I did make this explicit (but then it is easy to miss a post or a paragraph in a post or just a line:). I have defined a *computable* function (from N to N) as a function f such that there is a language (labeling sheme as you say) L in which it can be explained finitely and without ambiguity how for each n to compute f(n). Now, I have defined the notion of Universal Language UL as a language in which *all* computable function can be defined. (I also define a Universal Machine as a machine capable to "understand" the Universal Language, and thus capable of computing *all* computable function from N to N. And then Church Thesis is the statement that there is a Universal Language, in particular, that programming languages like FORTRAN, LISP, Java, c++, etc. are universal languages. Now, when we say that g(k) is the kth function in the list +1, we are defining an apparently computable function that does not have a place on the list, since if g were the ith function on the list we would have fi(i)=fi(i)+1. At this stage: you really should say what the fi are meant for. To be sure I will treat one+three cases under the form of 1+3 lists: 0) r1 r2 r3 r4 r5 r6 r7 r8 ... This is an arbitrary list of functions from N to N (not necessarily computable one); 1) h0 h1 h2 h3 h4 h5 h6 ... This is a list of total computable functions from N to N that we can generate mechanically (I mean we can generate their codes). It means that we can generate the codes of each hi, written in some language, and that, for some reason, we are sure that each hi is total computable. Examples: Caylor last funny enumeration; all the (transfinite collection of) sequences of growing functions we have defined in this thread (since "Smullyan Smullyan ..."); 2) f0 f1 f2 f3 f4 f5 f6 f7 ... This is a list of *all* total computable functions; 3) F0 F1 F2 F3 F4 F5 F6 F7 F8 ... This is the list of all programmable things in some "universal language" like fortran. CT asserts fortran is universal so that the total computable function fi will be dispersed *among* those Fi things, so that a universal machine can really compute all the fi, among other things. Now the same diagonalization argument proves 4 different propositions according to which list we are talking about. Which one? Before answering, I let people muse a little about what are those 4 different consequences, given that the only way to really grasp those propositions consists in rediscovering them by oneself. However, this is only a contradiction if we say that the list contains all the computable functions; it is not a contradiction if we say that the list contains all the computable functions which fit into the labelling scheme chosen for the list, as I think we must. (perhaps to read or reread after the musing suggested above). It depends what sorts of "labeling scheme" you are interested in. The key is that: 1) either you want only total functions (so that you can be sure your machine will not crash): in that case the diagonal g is total computable but cannot belong to your list. You would need another labeling scheme for a language extending your previous labeling containing that g. Like with the sequence of growing computable functions, this label-extension can be iterated into the transfinite. But at each of those transfinite stage your machine is NOT universal, but it grows toward it keeping control. (it is a sort of pre-image of the first person exploring the first person *plenitude* (Levy's expression)). 2) or you want to capture *all* total functions at once through one *universal* labeling scheme. Church Thesis is the statement that this wish can be fulfilled despite diagonalization (crazily enough!). Indeed CT asserts FORTRAN is such a universal language. And the programs can be effectively (fortran-mechanically, Turing-mechanically, recursively, ... with CT all those terms are equivalent) enumerated, so that you get the Fi. The price to pay for escaping the contradiction through the use of the diagonalization: some Fi are undefined and even unpredictably so. That is, the Fi enumerates a set much vaster than the fi, and the fi forms a NON recursively enumerable subset of a recursively enumerable set (the Fi), a little like the "Joconde" is a very complex subset of a simple rectangle! I know that George Levy does not like this too much: but the first person plenitude, [although so big and so unnameable that you cannot generate it in
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 15-juin-06, à 21:03, Jesse Mazer a écrit : > > Tom Caylor wrote: > >> >> So apparently we are still missing something. You need to tell us >> *why* this is not the right reason. The set of instructions for g is >> precisely a big "case" statement (if you will) on n, like this: >> >> switch n: >> begin >> case 1: >> set of instructions for f1: >> case 2: >> set of instructions for f2: >> case 3: >> set of instructions for f3: >> ... >> end (after an infinite number of cases) >> >> This is an infinitely long program. You need the whole program to >> define g, not just the portion you need for a given input. Is there a >> finite version of g? I don't see how. >> >> Tom > > I haven't been following the all details of this discussion, so > apologies if > I get things confused...but aren't those f1, f2, f3 etc. supposed to > correspond *only* to turing machine programs which actually halt and > give > you a finite number as an output? If so, then although we can write > down the > list of all possible turing machine programs, there is no way to > figure out > which programs on this list correspond to one of your functions and > which > don't without solving the halting problem. Note that even if you could solve the halting problem (perhaps with some oracle) you would still not been able to solve the problem of distinguishing the code/program of a total comp function from the code of a strictly partial comp function. I have proved that insolubility of code-of-total/code-of-partial distinction again and again without using the insolubility of the halting problem. Of course I proceed in that way to make things as simple as possible. Showing the insolubility of an harder problem (tot/partial) is of course simpler than showing the insolubility of a simpler problem (the halting problem). Another reason is that the set R of the total fi (the constructive reals) and the set P of the Fi will provide neat description of the first person plenitude and the third person plenitude, and relate all this to "Smullyan's heart of the matter". 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 15-juin-06, à 18:40, Tom Caylor a écrit : > > > Bruno Marchal wrote: >> >> 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. >> > > OK. You've shown by contradiction that g is not computable. I was > just trying to go back to the definition of computable to see which > part of the definition is violated. I think I overlooked the fact that > you alluded to the answer to this question when you said "...you just > will never been able to give me a finite set of instructions for doing > that". I.e. g violates the finite description part of computability. > I think Brent Meeker was trying to get at this idea, too, in answer to > your diagonalization explanation in 2001. > > http://www.mail-archive.com/everything-list@eskimo.com/msg01002.html > > But both then and now, you said that this is not the right reason, and > then you went on to repeat the proof by contradiction, which we already > understand. You have perhaps miss the difference between two resembling proof. I think A summary will be necessary. It should be easy because the proofs are short. > If finiteness does not correspond with the reason for > non-computability, this implies that there are g's formed by this > diagonalization method, which have a finite description, but that take > an infinite time to execute (thus fulfilling the definition of > non-computable). Are you talking about the diagonal function g build on from the set of all fi, and which is not computable, or about the G get from the Fi, which is partial computable, or about some given effective enumeration of total function (where we have used also the letter fi)? Or just wait for a summary where the proposition will be numerated for the sake of future use of them. Well here apparently you were talking about the Fi. > > So apparently we are still missing something. You need to tell us > *why* this is not the right reason. The set of instructions for g is > precisely a big "case" statement (if you will) on n, like this: > > switch n: > begin > case 1: > set of instructions for f1: > case 2: > set of instructions for f2: > case 3: > set of instructions for f3: > ... > end (after an infinite number of cases) > > This is an infinitely long program. You need the whole program to > define g, not just the portion you need for a given input. Is there a > finite version of g? I don't see how. But here you talk distinctly about the fi. if your fi denotes all the total computable functions, then, what we have proved, is that not only your "program" for g would be infinite, but, above all, could not be generated by any computational process: you cannot generate the sequence of all, and only all, total computable function f1, f2, f3, ... CT is the statement that the fi are among the Fi, so that you can generate computably a superset of the fi. 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 15-juin-06, à 17:57, Tom Caylor a écrit : > > An even simpler case is the following: > >inputs >1 2 3 4 5 6 7 8 9 > f1:1 2 3 4 5 6 7 8 9 ... (identity) > f2:2 1 3 4 5 6 7 8 9 ... (switch 1 and 2) > f3:3 2 1 4 5 6 7 8 9 ... (switch 1 and 3) > f4:4 2 3 1 5 6 7 8 9 ... (switch 1 and 4) > f5:5 2 3 4 1 6 7 8 9 ... (switch 1 and 5) > ... > fn:fn(n) 2 3 4 5 6 7 8 9 ... fn(n-2) fn(n-1) 1 fn(n+1) fn(n+2) ... > (switch 1 and fn(n)) > ... > So let's do the diagonalization move. Let g(n) = fn(n)+1. > But from inspection of the table, we see that fn(n) = 1. So g(n) = 1+1 > = 2. Putting this in a table: >inputs >1 2 3 4 5 6 7 8 9 ... > g: 2 2 2 2 2 2 2 2 2 ... > > But from inspection, we see that g does not fit anywhere in the table > of f1,f2,f3,... because it does not follow the rule of "switch 1 and > something else" [and also it doesn't follow fn(i)=i for all i not equal > > to 1 or fn(n+1) ]. > > So therefore g is not part of the list. I.e. g is not a total > computable function. > > However, as is plainer to see with this example, how can g(n)=2 (for > all n) not be computable and total? It is not one-to-one, but does > that make it not computable or not total? Of course g(n)=2 is computable! A program could be like BEGIN READ X OUTPUT 2 END You have just proved that g(n) = 2 is not in your list. But why did you ever think that your list should enumerate all computable functions? You generate just the identity functions up to a permutation in their range: you will miss all the constant functions (not just your g(n) = 2), you will miss the factorials, and any growing functions we have defined, etc. Still, you illustrate the point: for any presentation of an effective list of computable functions from N to N, we can build a computable function from N to N which is not in the list. An effective (computable) list of functions fi is given by a computable bijection i ---> Pi with Pi a program computing fi. It is obvious that the set of the computable function fi is enumerable. The diagonalization has proved so far that , although enumerable, that set is not computably enumerable. We have to understand this to grasp that Church Thesis (CT) is a very strong statement. CT says that all the computable fi belongs to the collection of the Fi, the partial computable functions or programmable functions, which *is* effectively enumerable. Will say more. 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno, I'll rephrase the problem - let me know if I get it wrong. It is proposed that all the functions f with certain attributes "A" be enumerated in a list: f1, f2, f3 etc. It looks like "A" in the example under consideration means "all the computable functions", but in fact there is a further implicit restriction: the list can only contain all the computable functions which will fit into the labelling scheme chosen for the list. Now, when we say that g(k) is the kth function in the list +1, we are defining an apparently computable function that does not have a place on the list, since if g were the ith function on the list we would have fi(i)=fi(i)+1. However, this is only a contradiction if we say that the list contains all the computable functions; it is not a contradiction if we say that the list contains all the computable functions which fit into the labelling scheme chosen for the list, as I think we must. This is perhaps just the point you are making: it is not that g is not computable, rather that the attempt to enumerate the computable functions is problematic. But is it as surprising to discover this (or what I think of as related results, like Russell's Paradox and Godel's Theorem) as it would be to discover, say, a discrepancy or contradiction in the addition and subtraction of integers? I'll reply to the second part of your post later. Stathis Papaioannou> > I've always wondered (from a position of relative mathematical > > naivete, please understand)> > about the process in arguments like this whereby reasoning about > > arithmetic comes to> > include the labels applied to arithmetical statements, on the grounds > > that these labels happen> > themselves to be numbers. The function g as defined below is based on > > a look-up table, and > > the contradiction consists in that this table has the same label > > applied to more than one> > distinct value, i.e. fk(k) and fk(k)+1. Doesn't this just mean that > > the chosen labelling> > scheme is ill-chosen? Is there any way to separate f and g formally, > > perhaps to call g a> > meta-function (or something) rather than a function of f, and thus > > avoid the contradiction?> > Or is this whole train of thinking basically flawed, there being no > > method in general to> > banish g from the cosy world of functions like f(x)=x^2 or sin(x) or > > |x|?> > > Just two questions before I leave, the first concerns this current > thread, the second refers to an older post of you.> > Why do you think g is defined from a look-up table? G applied on n > generates the Fi when needed. g would like generate the fi but can't. I > am using the convention that the Fi are the programmable function (thus > the partial computable one), and the fi are the total computable > functions.>Express yourself instantly with MSN Messenger! MSN Messenger --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Tom Caylor wrote: > >So apparently we are still missing something. You need to tell us >*why* this is not the right reason. The set of instructions for g is >precisely a big "case" statement (if you will) on n, like this: > >switch n: >begin >case 1: >set of instructions for f1: >case 2: >set of instructions for f2: >case 3: >set of instructions for f3: >... >end (after an infinite number of cases) > >This is an infinitely long program. You need the whole program to >define g, not just the portion you need for a given input. Is there a >finite version of g? I don't see how. > >Tom I haven't been following the all details of this discussion, so apologies if I get things confused...but aren't those f1, f2, f3 etc. supposed to correspond *only* to turing machine programs which actually halt and give you a finite number as an output? If so, then although we can write down the list of all possible turing machine programs, there is no way to figure out which programs on this list correspond to one of your functions and which don't without solving the halting problem. Jesse --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno Marchal wrote:
> Le 11-juin-06, à 08:49, Tom Caylor a écrit :
>
> >
> > Bruno Marchal wrote:
> >> 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.
>
OK. You've shown by contradiction that g is not computable. I was
just trying to go back to the definition of computable to see which
part of the definition is violated. I think I overlooked the fact that
you alluded to the answer to this question when you said "...you just
will never been able to give me a finite set of instructions for doing
that". I.e. g violates the finite description part of computability.
I think Brent Meeker was trying to get at this idea, too, in answer to
your diagonalization explanation in 2001.
http://www.mail-archive.com/everything-list@eskimo.com/msg01002.html
But both then and now, you said that this is not the right reason, and
then you went on to repeat the proof by contradiction, which we already
understand. If finiteness does not correspond with the reason for
non-computability, this implies that there are g's formed by this
diagonalization method, which have a finite description, but that take
an infinite time to execute (thus fulfilling the definition of
non-computable).
So apparently we are still missing something. You need to tell us
*why* this is not the right reason. The set of instructions for g is
precisely a big "case" statement (if you will) on n, like this:
switch n:
begin
case 1:
set of instructions for f1:
case 2:
set of instructions for f2:
case 3:
set of instructions for f3:
...
end (after an infinite number of cas
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Tom Caylor wrote: > An even simpler case is the following: > >inputs >1 2 3 4 5 6 7 8 9 > f1:1 2 3 4 5 6 7 8 9 ... (identity) > f2:2 1 3 4 5 6 7 8 9 ... (switch 1 and 2) > f3:3 2 1 4 5 6 7 8 9 ... (switch 1 and 3) > f4:4 2 3 1 5 6 7 8 9 ... (switch 1 and 4) > f5:5 2 3 4 1 6 7 8 9 ... (switch 1 and 5) > ... > fn:fn(n) 2 3 4 5 6 7 8 9 ... fn(n-2) fn(n-1) 1 fn(n+1) fn(n+2) ... > (switch 1 and fn(n)) > ... > So let's do the diagonalization move. Let g(n) = fn(n)+1. > But from inspection of the table, we see that fn(n) = 1. So g(n) = 1+1 > = 2. Putting this in a table: >inputs >1 2 3 4 5 6 7 8 9 ... > g: 2 2 2 2 2 2 2 2 2 ... > > But from inspection, we see that g does not fit anywhere in the table > of f1,f2,f3,... because it does not follow the rule of "switch 1 and > something else" [and also it doesn't follow fn(i)=i for all i not equal > > to 1 or fn(n+1) ]. > > So therefore g is not part of the list. I.e. g is not a total > computable function. > > However, as is plainer to see with this example, how can g(n)=2 (for > all n) not be computable and total? It is not one-to-one, but does > that make it not computable or not total? > > Tom In fact, my first example, where g(n) = n+1, is in fact one-to-one. Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
An even simpler case is the following: inputs 1 2 3 4 5 6 7 8 9 f1:1 2 3 4 5 6 7 8 9 ... (identity) f2:2 1 3 4 5 6 7 8 9 ... (switch 1 and 2) f3:3 2 1 4 5 6 7 8 9 ... (switch 1 and 3) f4:4 2 3 1 5 6 7 8 9 ... (switch 1 and 4) f5:5 2 3 4 1 6 7 8 9 ... (switch 1 and 5) ... fn:fn(n) 2 3 4 5 6 7 8 9 ... fn(n-2) fn(n-1) 1 fn(n+1) fn(n+2) ... (switch 1 and fn(n)) ... So let's do the diagonalization move. Let g(n) = fn(n)+1. But from inspection of the table, we see that fn(n) = 1. So g(n) = 1+1 = 2. Putting this in a table: inputs 1 2 3 4 5 6 7 8 9 ... g: 2 2 2 2 2 2 2 2 2 ... But from inspection, we see that g does not fit anywhere in the table of f1,f2,f3,... because it does not follow the rule of "switch 1 and something else" [and also it doesn't follow fn(i)=i for all i not equal to 1 or fn(n+1) ]. So therefore g is not part of the list. I.e. g is not a total computable function. However, as is plainer to see with this example, how can g(n)=2 (for all n) not be computable and total? It is not one-to-one, but does that make it not computable or not total? Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 15-juin-06, à 14:40, Stathis Papaioannou a écrit : I've always wondered (from a position of relative mathematical naivete, please understand) about the process in arguments like this whereby reasoning about arithmetic comes to include the labels applied to arithmetical statements, on the grounds that these labels happen themselves to be numbers. The function g as defined below is based on a look-up table, and the contradiction consists in that this table has the same label applied to more than one distinct value, i.e. fk(k) and fk(k)+1. Doesn't this just mean that the chosen labelling scheme is ill-chosen? Is there any way to separate f and g formally, perhaps to call g a meta-function (or something) rather than a function of f, and thus avoid the contradiction? Or is this whole train of thinking basically flawed, there being no method in general to banish g from the cosy world of functions like f(x)=x^2 or sin(x) or |x|? Just two questions before I leave, the first concerns this current thread, the second refers to an older post of you. Why do you think g is defined from a look-up table? G applied on n generates the Fi when needed. g would like generate the fi but can't. I am using the convention that the Fi are the programmable function (thus the partial computable one), and the fi are the total computable functions. The second question is related to your assessment (in older posts) that in a self-duplication W M, with annihilation of the "original" in Brussels, the probability are equal to 1/2. I don't disagree with this. But are you aware of the difficulty of composing such probabilities? What if in Moscow I am read and annihilated again, and duplicate into Sidney and Beijing? I mean what are in Brussels the (first person) probabilities to reach and stay in Washington, Sidney and Beijing respectively? The most common answers are "P(W) = 1/2 P(S) = P(B) = 1/4" and "P(W) = P(S) = P(B) = 1/3". The problem here is that you can have a continuum of thought experiments, where you introduce ranges of amnesia in Moscow going from a case where "clearly" it should be 1/2 1/4 1/4 and (in the case of a complete amnesia of anything happened in Moscow) 1/3 1/3 1/3. What would you say? I mention this problem because it has motivated me for going more technical. I think it shows that amnesia makes possible the relative fusion of comp histories ... like the one of the quantum (empirical) world. (I think George also assessed a relation between fusing and amnesia if I remember correctly (?)). 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 15-juin-06, à 13:53, Tom Caylor a écrit : > OK. I think I understand what you are saying, on a surface level. Of > course a surface level will never be able to expose any contradictions. > I'm just riding this wave as long as I can before deciding to get off. > > It seems that there are very deep concepts here. We are standing on > the shoulders of computability giants. I think it would take a Godel > or a Church or Turing to find any problem with your whole argument, if > there is any. My feeling is that any "problem" is actually just lack > of deep enough insight, either on the part of the attempting-refuter of > the argument, or on your part, or both. > > By the way, I am also cognizant that what you are covering here > actually is pretty standard stuff and actually has been pored over by > the giants of computability. So like I said, I'm riding the wave. > > On a certain level, it bothers me that Church's Thesis is said to not > have any proof. But maybe it is sort of like Newton's gravity. It is > just a descriptive statement about what can be observed. And yet... we > still don't really understand gravity. Here we are at the level where > all there is is falsifiability. OK. Note that Church thesis has a unique status in math. I will come back on this. > And, by the same diagonalization > argument, you'd have to be God to falsify this "stuff". Ah... but here you are wrong. Church thesis, although not entirely mathematical, still less physical, is completely refutable in the sense of Popper (and thus "scientific" in the "modern" acceptation of the word). To refute Church thesis it is enough to find a function F such that you can show: 1) F is computable, and 2) F is not Turing emulable. Some people, like Kalmar, has thought they got such a function, but this has been rebuked. Eliot Mendelson has argued that CT is provable, and sometimes I share a little bit that feeling. I did believe that CT is provable in "second order arithmetic" for a time because it did seem to me that CT relies above all on the intuition of the finite/infinite distinction. But then it could still be subtler than that, and I am not sure at all CT could really be proved. Note that I talk only on the classical Church thesis, not about its intuitonistic variants, which I do believe are false for the first person associated to the machine (and this has been partially confirmed by a result due to Artemov which shows that some "computabiliy version" of constructive mathematics (like the so called Markov principle) is false in S4Grz (with quantifiers). But intuitionist CTs really asserts a different thing. The only roles intuitionistic CTs have in my work are for the explanation of why (first person) machine find so hard to say yes to the doctor and also to clarify the non-constuctivity feature of the "OR" in "Washington OR Moscow" self-duplication experiments. Godel did miss Church thesis, and he takes some years for him to eventually assess it and then to describe it as a "sort of epistemological miracle". At the same time I would say Godel never got it completely because he will search for an equivalent miracle for the provability notion, but this can be shown being highly not plausible ... from Church thesis. I have evidence that Charles Babbage (and perhaps its friend Ada Lovelace) got Church thesis, once century before the others. The evidence comes from a book by Jacques Lafitte(*) who said in 1911 that Babbage discovered that his notation system for describing its analytical machine was somehow cleverer than his machine. Now, the first who really discovered explictly "Church thesis" and its relation with both computability and provability, is Emil Post in 1922, according to my knowledge. Must go now. I intend to comment Tom and Stathis' post later, perhaps Saturday because I have exams all the day tomorrow. Bruno (*) LAFITTE J., 1911, 1932, Réflexions sur la science des machines, Vrin 1972 (New Ed.), Paris. 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 14-juin-06, à 07:31, Russell Standish a écrit :
>
> On Mon, Jun 12, 2006 at 03:52:15PM +0200, Bruno Marchal wrote:
>>
>> 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.
>
> This is an interesting comment, that I hadn't appreciated before. The
> Plenitude I study has infinite length "description", precisely because
> this plenitude is the zero information object.
Could you explain what is your conception of the relation between a
description and an object?
I can understand "an infinite length object", like some putative
infinite physical universe for example. I can understand "a zero
information description"; for example the empty program or some empty
theory (I will address "theories" later though). It is harder for me to
understand what can be the use of infinite description or a
zero-information object.
>
> However, computable things are indeed finite in size, which implies
> that the arithmetical Platonia is smaller, and consequently a richer
> set of things.
>
> The universal dovetailer, however, executes everything in the infinite
> bitstring Plenitude does it not, or is this a misunderstanding of
> Schmidhuberian proportions?
I think the only trouble with Schmidhuber, and then with many people to
be sure, is that they find hard to take seriously enough the
distinction between first and third person point of views.
The UD is a (finite) program, and when it runs, like any program
running on some universal machine, it uses only at each time a finite
piece of its (potentially infinite) tape, etc.
Now, indeed, once you grasp that the probabilities of relative
histories relies on the first person point of view, the case can been
made that the infinite computations have a higher measure that the
finite one, so that somehow physicalities emerges from the infinite set
of those infinite (crashing-like) computations.
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
RE: *THE* PUZZLE (was: ascension, Smullyan, ...)
I've always wondered (from a position of relative mathematical naivete, please understand) about the process in arguments like this whereby reasoning about arithmetic comes to include the labels applied to arithmetical statements, on the grounds that these labels happen themselves to be numbers. The function g as defined below is based on a look-up table, and the contradiction consists in that this table has the same label applied to more than one distinct value, i.e. fk(k) and fk(k)+1. Doesn't this just mean that the chosen labelling scheme is ill-chosen? Is there any way to separate f and g formally, perhaps to call g a meta-function (or something) rather than a function of f, and thus avoid the contradiction? Or is this whole train of thinking basically flawed, there being no method in general to banish g from the cosy world of functions like f(x)=x^2 or sin(x) or |x|? Stathis Papaioannou > Let me just recall what is a computable function from N to N. It is > function from N to N which is such that it is exist a finite way to > explain how to compute it in a finite number of steps on any natural > numbers. More precisely: f is computable if there is a language L such > that f admits a finite code/program/description/number explaining how > to compute f(n), in a finite time on any number natural n.> I will say that that a language L is universal, if all computable > functions from N to N admit a code in L.> > A weak form of Church thesis can be put in this way: there exists a > universal language.> > I will say a digital (or finitely describable) machine M is universal > if M can "understand" a universal language L, in the sense of being > able to compute any computable functions described in L (and thus all > given that L is universal) . In term of digital machine, Church thesis > becomes: there exists a universal digital machine.> > Now what is wrong with the following argument: if there is an universal > language or machine, the computable functions can be described by > finite description in that language, or program for that machine.> Such a set is obviously enumerable. There is a bijection between N and > the set of those descriptions:> > 1 f1> 2 f2> 3 f3> 4 f4> etc.> > So the following function g is well-defined by:> > g(n) = fn(n) + 1> > Then, to compute it on the number n (439 say), just generate the > description/program of f1 f2 f3 ... until fn, that is f439, apply it > on n to get fn(n), f439(439), and add 1 to get g(n) = fn(n)+1, that is > here: f439(439)+1.> But then g cannot be described in the language L! Why? Suppose g is > described by a code in the language L: then g belongs somewhere in the > list f1, f2, f3, f4, f5, Thus there would exist a number k such > that g = fk, and thus g(k) = fk(k); but g(k) = fk(k)+1. And thus> > fK(k) = fk(k)+1(*)> > And fk(k) is a well defined number given that the fi are all computable > functions from N to N. So I can substract fk(k) on both sides of (*) > just above, and I get 0 = 1 (contradiction). So there is no universal > language, we cannot generate all computable functions, still less, > then, to dovetail on them.>Express yourself instantly with MSN Messenger! MSN Messenger --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno Marchal wrote: > ... > 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. > Let me try to see what is wrong with the following attempt to enumerate the total computable functions: inputs 1 2 3 4 5 6 7 8 9 ... f1:2 1 3 4 5 6 7 8 9 ... (switch 1 and 2) f2:3 2 1 4 5 6 7 8 9 ... (switch 1 and 3) f3:4 2 3 1 5 6 7 8 9 ... (switch 1 and 4) f4:5 2 3 4 1 6 7 8 9 ... (switch 1 and 5) f5:6 2 3 4 5 1 7 8 9 ... (switch 1 and 6) ... fn:fn(n+1) 2 3 4 5 6 7 8 9 ... fn(n-2) fn(n-1) fn(n) 1 fn(n+2) ... (switch 1 and fn(n+1)) ... So let's do the diagonalization move. Let g(n) = fn(n)+1. But from inspection of the table, we see that fn(i) = i, for all i not equal to 1 or fn(n+1). So g(n) = n+1. Putting this in a table: inputs 1 2 3 4 5 6 7 8 9 ... g: 2 3 4 5 6 7 8 9 10 ... But from inspection, we see that g does not fit anywhere in the table of f1,f2,f3,... because it does not follow the rule of "switch 1 and something else" [and also it doesn't follow fn(i)=i for all i not equal to 1 or fn(n+1) ]. So therefore g is not part of the list. I.e. g is not a total computable function. I have more to say/ask, but I have to meet someone to go jogging right now. I don't know when I'll have more time. Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno Marchal wrote: > ... > 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/ OK. I think I understand what you are saying, on a surface level. Of course a surface level will never be able to expose any contradictions. I'm just riding this wave as long as I can before deciding to get off. It seems that there are very deep concepts here. We are standing on the shoulders of computability giants. I think it would take a Godel or a Church or Turing to find any problem with your whole argument, if there is any. My feeling is that any "problem" is actually just lack of deep enough insight, either on the part of the attempting-refuter of the argument, or on your part, or both. By the way, I am also cognizant that what you are covering here actually is pretty standard stuff and actually has been pored over by the giants of computability. So like I said, I'm riding the wave. On a certain level, it bothers me that Church's Thesis is said to not have any proof. But maybe it is sort of like Newton's gravity. It is just a descriptive statement about what can be observed. And yet... we still don't really understand gravity. Here we are at the level where all there is is falsifiability. And, by the same diagonalization argument, you'd have to be God to falsify this "stuff". Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
On Mon, Jun 12, 2006 at 03:52:15PM +0200, Bruno Marchal wrote:
>
> 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.
This is an interesting comment, that I hadn't appreciated before. The
Plenitude I study has infinite length "description", precisely because
this plenitude is the zero information object.
However, computable things are indeed finite in size, which implies
that the arithmetical Platonia is smaller, and consequently a richer
set of things.
The universal dovetailer, however, executes everything in the infinite
bitstring Plenitude does it not, or is this a misunderstanding of
Schmidhuberian proportions?
Cheers
--
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 13-juin-06, à 03:04, George Levy a écrit : > > Bruno Marchal wrote: > >> Proceeding that way you will run into trouble. But it is very easy to >> find the k. >> Let us be specific and let us imagine you have already written in >> Fortran a generator of all programs of the one-variable partial >> computable functions: F1 F2 F3 F4 F5 F6 F7 ... >> The list of programs is P1 P2 P3 P4 P5 P6 ... Each Pi(n) computes >> Fi(n) >> >> Now program G in "Fortran". It is something like that: >> >> Begin G >> Read X >> Call the generator of program up to X, giving PX >> Apply PX on X, and put the result in register 439 >> Add 1 to the content of register 439 >> Output the content of register 439 >> End >> >> Now, look at your list of programs Pi until you find it, and look at >> his number code (where n is the number code of Pn by definition). >> Finding your program in your list of programs should be easy given >> that >> the list P1 P2 P3 ... is ordered lexicographicaly (by length, and by >> alphabetical order for those of same length). So you can find it >> easily. Is number code is the number k. If you run G on k, your >> fortran >> interpreter will run for ever (and your fortran compiler will generate >> a code which run for ever). Speaking just a little bit loosely. >> >> >> > Let's be more specific. > Begin G > Read X > Call generator of program which produces P1, P2, P3..in sequence. > Select > Program PX. > Compute the value PX(X). > Save the value into register 439 > Add 1 to content of register 439. Call this value Y OK. I guess you agree this program is equivalent to mine. Now this a fortran program (I mean when correctly written in Fortran of course). Thus it is equal (syntactically) with some program Pk (given that the Pi lists all fortran programs). But then we have *already* k. It is the indice k of Pk = "BEGIN G READ X ..." written above. We don't even need to ever run G, because to find its code (and thus its number code) we need only to *write* the program. To find k we need only to find the piece of code Pk in our list P1 P2 ... So I don't see the point of your scanning device. Having said this > > Now look at the list of all programs P1(1), P2(2) I guess you mean the 0-variable programs obtained by fixing the argument (like in Jesse second key remark of last week). > The scanning > program could be: > > i = 1(initiate counter i to 1) > Start Loop > If Pi(i) = Y then k=i; Exit > Else i=i+1 > End if > End Loop > > My point is that the loop will never end and you will never find k. I think you are right. But this shows only that this way of finding k will not work. See above for a method which works. Tell me if you see it works. It works because the program above is in the list Pi, so it has a number code k. We don't need a second scanning program to find it. The code of G is enough, we just need to be patient to find it in the list of the programs Pi, and given that the Pi are lexicographically ordered, we can do it for sure. Of course we can write a program for doing that, that program is just the reciprocal of the computable bijection between the N and the set of codes of the partial computable functions. I recall that set of the computable partial functions includes the set of the strictly partial and the set of total computable functions. I will make a summary of definitions and of the propositions we have already proved. > If > you did find k then Pk(k) = P(k)+1 which is impossible. Not at all. The Pk are the programs of the partial computable functions Fk (not the total one fk). I can find k by localizing the program above (or any equivalent) in the list Pi. > However, I don't see any problem in using P(x) for computing G(x) for > any x Well, even your own argument shows that G(k) is undefined. Here your remark would be true with the "listing" of the total computable fonction. In that case G is not computable because we have shown by diagonalization that the "listing" of fi is not programmable. I know you leave us for 10 days, and your last line makes me not so sure you completely grasped the difference between the fi and the Fi. (apology for those june-exam like remark: but some minimal amount of technical matter needs to get the real thing). All this is needed to proceed, so I hope we will arrive at a common understanding. G G*, and thus all "plotinian hypostases" (including the physical appearances) will appear when you will be easy not only with the current diagonalizations, but when you will see that a machine canhandle them too and reason about. them also, so that she is able to study its own limitations. In Smullyan's FU, this is reflect in the two stages: fact 1 + fact 2 versus fact I + fact II, where "true" has been replaced by "established". UDA shows that the physical appearances emerges from those limitations, and to extract physics (and then the whole larger theology
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno Marchal wrote: >Proceeding that way you will run into trouble. But it is very easy to >find the k. >Let us be specific and let us imagine you have already written in >Fortran a generator of all programs of the one-variable partial >computable functions: F1 F2 F3 F4 F5 F6 F7 ... >The list of programs is P1 P2 P3 P4 P5 P6 ... Each Pi(n) computes Fi(n) > >Now program G in "Fortran". It is something like that: > >Begin G >Read X >Call the generator of program up to X, giving PX >Apply PX on X, and put the result in register 439 >Add 1 to the content of register 439 >Output the content of register 439 >End > >Now, look at your list of programs Pi until you find it, and look at >his number code (where n is the number code of Pn by definition). >Finding your program in your list of programs should be easy given that >the list P1 P2 P3 ... is ordered lexicographicaly (by length, and by >alphabetical order for those of same length). So you can find it >easily. Is number code is the number k. If you run G on k, your fortran >interpreter will run for ever (and your fortran compiler will generate >a code which run for ever). Speaking just a little bit loosely. > > > Let's be more specific. Begin G Read X Call generator of program which produces P1, P2, P3..in sequence. Select Program PX. Compute the value PX(X). Save the value into register 439 Add 1 to content of register 439. Call this value Y Now look at the list of all programs P1(1), P2(2) The scanning program could be: i = 1(initiate counter i to 1) Start Loop If Pi(i) = Y then k=i; Exit Else i=i+1 End if End Loop My point is that the loop will never end and you will never find k. If you did find k then Pk(k) = P(k)+1 which is impossible. However, I don't see any problem in using P(x) for computing G(x) for any x --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 12-juin-06, à 00:23, George Levy a écrit : > Ok. G(n) = Fn(n)+1 is computable. I guess you mean programmable, or at least "partial computable". OK. > The hard part is finding the k such > that G(k)=Fk(k). I could try scanning all instances of Fk(k) from k=0 > to > a very large number. The scan will never find a match.because there is > no k that satisfies both G(k) = Fk(k)+1 and G(k)=Fk(k). Proceeding that way you will run into trouble. But it is very easy to find the k. Let us be specific and let us imagine you have already written in Fortran a generator of all programs of the one-variable partial computable functions: F1 F2 F3 F4 F5 F6 F7 ... The list of programs is P1 P2 P3 P4 P5 P6 ... Each Pi(n) computes Fi(n) Now program G in "Fortran". It is something like that: Begin G Read X Call the generator of program up to X, giving PX Apply PX on X, and put the result in register 439 Add 1 to the content of register 439 Output the content of register 439 End Now, look at your list of programs Pi until you find it, and look at his number code (where n is the number code of Pn by definition). Finding your program in your list of programs should be easy given that the list P1 P2 P3 ... is ordered lexicographicaly (by length, and by alphabetical order for those of same length). So you can find it easily. Is number code is the number k. If you run G on k, your fortran interpreter will run for ever (and your fortran compiler will generate a code which run for ever). Speaking just a little bit loosely. > >> The key point if, I may insist, is that >> >> 1) the superset (of programmable functions, not everywhere defined) is >> MECHANICALLY enumerable. You can write a fortran program generating >> their codes. >> 2) the subset of (computable function from N to N) is enumerable, but >> is NOT MECHANICALLY enumerable. The bijection with N exists, but is >> not >> programmable, in *any* programming language! >> >> >> George ? Are you ok. >> >> > Hanging on Remember, I would like to know how all this relates to > *me.* I think it relates to *you* :) in many ways. The simplest, is that the UDA shows that if comp is true, eventually the laws of physics will emerges from a structure related to the UD through computer science, Church thesis, arithmetical self-reference, etc. And those laws of physics calibrate *your* possibilities, what you can hope for locally. Of course current physics and mundane knowledge helps more here. And for the life after death question just let us say that the equation are too much complex (is it possible to annihilate oneself? open problem). But the three main hypostases (truth, provability and knowability) gives a more global picture. ... don't really one to anticipate too much... At some point perhaps you will recognize some Lobian machine living through you, at least sufficiently enough for being interested in the possible fates of lobian machines in general? It concerns us as any plausible attempts to figure out what reality are we "really" living concerns us. I just show that if we are machine; then there is a first person indeterminacy, and eventually the physical emerges from the mind/number so that Plato is right and Aristotle wrong, and materialism is put in difficulty, and as far as theology (the truth about *you*) concern us I'm afraid we need to backtrack a little bit. But it is theory, science, conjecture's based, third person communication. No certainty here. And comp justifies the roots of our uncertainty there, either by thought experiments or by diagonalization, or other forms of sharable introspection. Before comp: only two certainties: death and taxes. After comp: only once certainties: taxes. It may concern *us*. And note that comp just rises one doubt more. Or destroy one certainty, at least for some it seems. But this, people in this list already know the possibility, given that QM without collapse do the same, with respect, of course, to the belief that nature (exists and) follows QM. With comp we need much less belief than QM to begin to doubt on most fundamental questions and guess the many possibilities. Some doubts are creative and leads to ... new taxes! Eventually the answer to your question depends exclusively by what *you* mean by *you*. Mathematical self-reference can perhaps provides sort of hints, even without comp ... I stop here before I run into an infinite computation . 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
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
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
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 o
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Quentin Anciaux wrote: > > it generate the second > > program, execute the first instruction of the second program, then the > > *SECOND* instruction of the first program, then it generates the third one, > > executing its first instruction, the second instruction of the second > > program, the *THIRD* of the first and so on ad infinitum. > > I hope everyone has corrected this ,) I apologize for these mistakes/errors ? > > And also if a program has no next instruction, then it simply stop and the UD > won't execute any instruction of it (after it ended). > > Quentin Yes. After I wrote that post, I recognized how a UD works. Thanks. My other points/questions still stand. Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
> it generate the second > program, execute the first instruction of the second program, then the > *SECOND* instruction of the first program, then it generates the third one, > executing its first instruction, the second instruction of the second > program, the *THIRD* of the first and so on ad infinitum. I hope everyone has corrected this ,) I apologize for these mistakes/errors ? And also if a program has no next instruction, then it simply stop and the UD won't execute any instruction of it (after it ended). Quentin --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Hi Tom, Le Dimanche 11 Juin 2006 02:00, Tom Caylor a écrit : > > 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?... > or... at least by the digaonalization reasoning you've given), 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. The UD doesn't work this way. The dovetailer dovetail ;) it means, first it generates the "first" program (programs are enumerated following the set N) and execute the first instruction of it, then it generate the second program, execute the first instruction of the second program, then the first instruction of the first program, then it generates the third one, executing its first instruction, the second instruction of the second program, the first of the first and so on ad infinitum. This way the UD can't be stuck in a loop of one program it generates (even if the program itself will never halt). Quentin --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
I went on a 10 day trip during which I had no access to email... a lot
has happened on this list since then.
Bruno Marchal wrote:
>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)
>
>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.
>
>
>
Ok. G(n) = Fn(n)+1 is computable. The hard part is finding the k such
that G(k)=Fk(k). I could try scanning all instances of Fk(k) from k=0 to
a very large number. The scan will never find a match.because there is
no k that satisfies both G(k) = Fk(k)+1 and G(k)=Fk(k).
>The key point if, I may insist, is that
>
>1) the superset (of programmable functions, not everywhere defined) is
>MECHANICALLY enumerable. You can write a fortran program generating
>their codes.
>2) the subset of (computable function from N to N) is enumerable, but
>is NOT MECHANICALLY enumerable. The bijection with N exists, but is not
>programmable, in *any* programming language!
>
>
>George ? Are you ok.
>
>
Hanging on Remember, I would like to know how all this relates to *me.*
George
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Hi Tom, Le Dimanche 11 Juin 2006 02:00, Tom Caylor a écrit : > > 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?... > or... at least by the digaonalization reasoning you've given), 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. The UD doesn't work this way. The dovetailer dovetail ;) it means, first it generates the "first" program (programs are enumerated following the set N) and execute the first instruction of it, then it generate the second program, execute the first instruction of the second program, then the first instruction of the first program, then it generates the third one, executing its first instruction, the second instruction of the second program, the first of the first and so on ad infinitum. This way the UD can't be stuck in a loop of one program it generates (even if the program itself will never halt). Quentin --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Tom Caylor wrote: > ... > 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). Here I should have said (I think), "interspersed with Fi's that are partial computable functions, it would still compute the fi's in a finite amount of time, along with a finite amount of the Fi's computation." Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
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?
>
> 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?
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?
> So,
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno Marchal wrote:
> Hi,
>
> Ok Tom, put your security belt because we will leave the constructive
> area, because it is the price we need to pay, in front of machine, for
> NOT leaving the finite area.
>
> Let me recall the problem.
>
> 1) Obviously the set of all computable function from the set of natural
> number N to the set of natural numbers N is countable (synonym:
> enumerable, in bijection with N). The reason is that a computable
> function, by definition, has a code (synonym: a description, a program,
> a finite machine), that is any finite things which can be used by some
> entity/machine for computing the functions, and (infinite) sets of
> finite things are always (infinite and) countable.
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). 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?
> 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? 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. This
is equivalent to saying that the rational numbers can be put in a
one-to-one correspondence (bijection) with N, which is true. 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. The
number of such programs is equivalent to the cardinality of the reals
or the continuum. So we have to keep in mind that "infinite object"
refers to the domain of the function, not the description of the
function. Right?
> 2) Now it looks like we have already a contradiction. let us write f1
> for the computable function having the least code, f2 the second one,
> etc. So we get the sequence f1, f2, f3, f4, f5, ... fn, And let
> us define the function g by
>
> g(n) = fn(n) + 1
>
> 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.
>
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. 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.
>
> 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
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Hi,
Ok Tom, put your security belt because we will leave the constructive
area, because it is the price we need to pay, in front of machine, for
NOT leaving the finite area.
Let me recall the problem.
1) Obviously the set of all computable function from the set of natural
number N to the set of natural numbers N is countable (synonym:
enumerable, in bijection with N). The reason is that a computable
function, by definition, has a code (synonym: a description, a program,
a finite machine), that is any finite things which can be used by some
entity/machine for computing the functions, and (infinite) sets of
finite things are always (infinite and) countable.
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.
2) Now it looks like we have already a contradiction. let us write f1
for the computable function having the least code, f2 the second one,
etc. So we get the sequence f1, f2, f3, f4, f5, ... fn, And let
us define the function g by
g(n) = fn(n) + 1
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.
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)
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 trou
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 08-juin-06, à 02:56, Russell Standish a écrit : > > On Wed, Jun 07, 2006 at 03:56:32PM +0200, Quentin Anciaux wrote: >> >> Hi Bruno, >> >> what I undestand about the UD is that it generates all programs, a >> program >> being simply a number from the set N.(1) > > No - halting programs are a subset of N, but there are uncountably > infinite non-halting ones. > > (Assuming we identify all programs without taking the non-read bits > into account). Of course Humpty-Dumpty said, about definitions, that it all depends on who is the master :), but it is against all usage to qualify as digital machine or program something which is not finite or finitely describable. All the teleportation thought experiment where based on the fact that we assume, when assuming comp, that our current local description can be put on some finite disk or something. Especially in our context it would be misleading to generalize the notion of program to infinite one (it can be done but it is another chapter and it can be done mathematically only if we grasp the theory of finite programs and machines before. Actually, many computer scientists call some universal machine "infinite" (although they are finite!!!), but this is just for opposing them to *bounded* automata (which are "more" finite if you want, a universal machine can always ask for some more memory supply. A bounded automate cannot). In Marvin Minsky's cute book "finite and infinite machines", the infinite machines are finite in the usual sense of the word. After people understands clearly what is going on with the diagonalization, it will be easy to define what is a universal machine, and why it is something finite, despite the perhaps misleading idea of Turing's "infinite" (but mostly empty at all time) rubber. So halting and non halting programs are countable. Infinite machine like Nielsen's and Calude's one belongs to a quite different chapter (they will still obey to G and G*, but then, for proving this, much more sophisticated recursion-theory tools are needed, and they presuppose a complete understanding of the finite machine case. Your "definition" can be used in the comp-weaker philosophy, which is, by ordinary standard, a non-comp philosophy, except that they can be lobian or self-referentially correc, and in that case they are still obeying to G and G*. 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Hi Quentin,
Le 07-juin-06, à 15:56, Quentin Anciaux a écrit :
>
> Hi Bruno,
>
> what I undestand about the UD is that it generates all programs, a
> program
> being simply a number from the set N.(1)
This is right. Programs or digital machine are supposed to be
(grammatically) well-defined, and this means that we can check in
finite time if some string is a well defined program for some universal
machine. Program like digital machines, or like ourself with comp, are
also supposed to be finite or finitely describable. From that, having
fixed a particular universal machine, we get a computable bijection
between N and the set of all programs. A choice of a Universal Machine
is akin to a choice of a base in a vector space. In each case the
choice makes it possible to ascribe numbers to the mathematical
entities under considerations (natural number for program/machine),
real or complex number for vectors.
In geometry, interesting theorems does not depend of the choice of the
base. In computer science, it is the same. Interesting theorem should
not depend on the choice of the particular universal machine. Of
course I will have to say more on this.
>
> There exists an infinity of program which generates a set of growing
> function
> (different set), all the computable growing function are generated by
> all
> these programs(taken as a whole). Is this correct ?
Taken as a whole: yes.
Alas that whole set cannot be generated mechanically (algorithmically,
by a computer/universal machine). If it was, then the diagonalization
would prove 0=1 again!
That is why, when given a name for a *big* finite number, like
[omega[omega]omega] applied to (9 [9] 9) I have only use a "tiny" part
of the nameable (constructive) ordinal.
Now, if you accept some set theory, obviously you can consider the set
of all constructive ordinals. That gives the first non constructive
ordinal. His name is omega1^CK. CK is for Church and Kleene who found
it. It cannot be constructive, and cannot be generated by a program,
but you can generated bigger and biiger part of it. Note that omega1^CK
is still enumerable (countable, in bijection with N).
Mysterious? Not at all: you will see (I prefer to keep the solution in
one post; so: see later).
With the growing functions from N to N, either you have a set of
names/codes/descriptions/programs which you can generate, but then it
is incomplete, it miss some growing functions; or your set of growing
functions is complete, but then you cannot generate it. We will see
many other examples of sets having similar property.
> Is this metaset also
> diagonalisable ?
It depends of what you mean by a set being diagonalizable? If it is
really the whole set, then, you can get only by building a special
progression on the whole of omega1^CK, and this cannot be done
mechanically. So the whole set will be vaccinated against programmable
diagonlization.
At some point we will have to distinguish carefully among effective
(programmable) diagonalization and some non-constructive (non
programmable) one.
> I said no, because if it was then there is a contradiction
> with the premises that said that we generate *all* the programs that
> compute
> growing functions, thus either we cannot generate those programs (but
> that
> would be strange, that would means N is not enumerable ?) or the
> "metaset" is
> not diagonalisable...
>
> Where do I fail in my understanding ?
I will try to be clear on this asap (still today). Of course N is
enumerable!
>
> Thanks,
> Quentin
>
> (1) I still have another problem with that because a program to be run
> need
> also the coding scheme (the instruction set of the turing machine that
> run
> it), which instruction set the UD use ? or how it construct it ?
A particular UD will just use the(finite number of) instructions of
some particular Universal machine.
Do you recall the SK-combinator programming language? It has an
incredibly simple syntax given that "S" is a program, "K" is a program,
and then all the other programs have been defined "recursively" or "by
induction" from that: if x et a program and y is a program, then (x y)
is a program.
So K, S, (K K), (K S) (S K) (S S) ((K K) K) ((K S) K) ... are all
programs.
In that case, a UD will be programmed by a finite string of S and K +
parentheses.
A UD written in Fortran (resp. lisp) will be a a fortran program. Of
course you can write in Fortran a UD which dovetails on the LISP
programs, and reciprocally ... More will be said, but if, after that,
there are still unclear points don't hesitate to ask ('course).
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, vi
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Russell Standish wrote: > > >Indeed obtaining the tape with Omega on it would be equivalent to solving >the Halting problem, but obtaining an arbitrary random noncomputable >sequence >tape is as simple as hooking up a random source to your TM. > >In what way is the random source not a program? True, although it's only noncomputable if the program actually goes through an infinite number of steps and an infinite number of random digits are generated. Also, if the many-worlds interpretation is correct, then at the level of the multiverse as a whole there'd be no true randomness, this would just be a variant of the dovetailer-like branching solution I suggested in my last post. Jesse --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Indeed obtaining the tape with Omega on it would be equivalent to solving
the Halting problem, but obtaining an arbitrary random noncomputable sequence
tape is as simple as hooking up a random source to your TM.
In what way is the random source not a program?
On another point, 10,000 bits of Omega would be enough to decide the
truth or otherwise of pretty much any mathematical statement of
interest to humans. See Li and Vitanyi's comment on page 218. 10,000
bits eh - just over a KB, which is not a terribly large program.
On Thu, Jun 08, 2006 at 03:36:19AM -0400, Jesse Mazer wrote:
>
> Russell Standish wrote:
>
> >
> >
> >On Thu, Jun 08, 2006 at 04:24:51AM +0200, Quentin Anciaux wrote:
> > >
> > > Le Jeudi 8 Juin 2006 02:56, Russell Standish a écrit :
> > > > On Wed, Jun 07, 2006 at 03:56:32PM +0200, Quentin Anciaux wrote:
> > > > > Hi Bruno,
> > > > >
> > > > > what I undestand about the UD is that it generates all programs, a
> > > > > program being simply a number from the set N.(1)
> > > >
> > > > No - halting programs are a subset of N, but there are uncountably
> > > > infinite non-halting ones.
> > >
> > > Do you mean there exists programs which are not encodable in a finite
> >string ?
> > > Is this really a "program" then ? And I see plenty of non-halting
> >program
> > > which are perfectly writeable in a few instruction.
> > >
> >
> >Of course there are finite length non-halting programs. The question
> >is whether infinite length input tapes are considered programs - isn't
> >this as much a matter of definition than anything else?
>
> But if the infinite string is not itself computable (if it can't be
> generated by a universal turing machine operating on some finite string,
> say), then we'd have no way to run such a program in the real world--imagine
> if the infinite string is Omega (a noncomputable number which encodes the
> answer to whether any turing machine operating on a computable input will
> halt or not), for example. Of course we can use a dovetailer-like solution
> where every time the universal turing machine reaches a digit of its input
> string it hasn't visited yet, we create two new "branches" where we simulate
> what would happen if it encountered a 1 *and* what would happen if it
> encountered a 0 on that step. If we run this branching simulation forever,
> then there must be some path that is identical to what would happen if that
> universal turing machine was fed Omega (or any other possible infinite
> string) as an input...but we can never know which path this is, at least not
> unless the laws of physics allow us to build machines which can solve the
> halting problem in a finite time.
>
> Jesse
>
>
>
>
--
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Russell Standish wrote: > > >On Thu, Jun 08, 2006 at 04:24:51AM +0200, Quentin Anciaux wrote: > > > > Le Jeudi 8 Juin 2006 02:56, Russell Standish a écrit : > > > On Wed, Jun 07, 2006 at 03:56:32PM +0200, Quentin Anciaux wrote: > > > > Hi Bruno, > > > > > > > > what I undestand about the UD is that it generates all programs, a > > > > program being simply a number from the set N.(1) > > > > > > No - halting programs are a subset of N, but there are uncountably > > > infinite non-halting ones. > > > > Do you mean there exists programs which are not encodable in a finite >string ? > > Is this really a "program" then ? And I see plenty of non-halting >program > > which are perfectly writeable in a few instruction. > > > >Of course there are finite length non-halting programs. The question >is whether infinite length input tapes are considered programs - isn't >this as much a matter of definition than anything else? But if the infinite string is not itself computable (if it can't be generated by a universal turing machine operating on some finite string, say), then we'd have no way to run such a program in the real world--imagine if the infinite string is Omega (a noncomputable number which encodes the answer to whether any turing machine operating on a computable input will halt or not), for example. Of course we can use a dovetailer-like solution where every time the universal turing machine reaches a digit of its input string it hasn't visited yet, we create two new "branches" where we simulate what would happen if it encountered a 1 *and* what would happen if it encountered a 0 on that step. If we run this branching simulation forever, then there must be some path that is identical to what would happen if that universal turing machine was fed Omega (or any other possible infinite string) as an input...but we can never know which path this is, at least not unless the laws of physics allow us to build machines which can solve the halting problem in a finite time. Jesse --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
On Thu, Jun 08, 2006 at 04:24:51AM +0200, Quentin Anciaux wrote:
>
> Le Jeudi 8 Juin 2006 02:56, Russell Standish a écrit :
> > On Wed, Jun 07, 2006 at 03:56:32PM +0200, Quentin Anciaux wrote:
> > > Hi Bruno,
> > >
> > > what I undestand about the UD is that it generates all programs, a
> > > program being simply a number from the set N.(1)
> >
> > No - halting programs are a subset of N, but there are uncountably
> > infinite non-halting ones.
>
> Do you mean there exists programs which are not encodable in a finite string
> ?
> Is this really a "program" then ? And I see plenty of non-halting program
> which are perfectly writeable in a few instruction.
>
Of course there are finite length non-halting programs. The question
is whether infinite length input tapes are considered programs - isn't
this as much a matter of definition than anything else?
We can distinguish between those tapes that cause a finite number of
symbols to be read from the tape (including all halting programs) from those
tapes that do not (when fed an infinite tape).
> > (Assuming we identify all programs without taking the non-read bits
> > into account).
>
>
--
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le Jeudi 8 Juin 2006 02:56, Russell Standish a écrit : > On Wed, Jun 07, 2006 at 03:56:32PM +0200, Quentin Anciaux wrote: > > Hi Bruno, > > > > what I undestand about the UD is that it generates all programs, a > > program being simply a number from the set N.(1) > > No - halting programs are a subset of N, but there are uncountably > infinite non-halting ones. Do you mean there exists programs which are not encodable in a finite string ? Is this really a "program" then ? And I see plenty of non-halting program which are perfectly writeable in a few instruction. > (Assuming we identify all programs without taking the non-read bits > into account). --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
On Tue, Jun 06, 2006 at 03:05:26PM +0200, Bruno Marchal wrote:
>
> Alas this is only partially true. Well, perhaps it is due to my use of
> both english and french all the time, but I have a tendency to mess up
> the "s" in french too. The "s" rule are 90% opposed in french and
> english.
Really? True in French, the final s is rarely pronounced, but how
often do the plural forms differ for similar words in each language?
The few words that come to mind for me are exceptional:
eg animal -> animaux in French; animal -> animals in English
Cheers
--
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
On Wed, Jun 07, 2006 at 03:56:32PM +0200, Quentin Anciaux wrote:
>
> Hi Bruno,
>
> what I undestand about the UD is that it generates all programs, a program
> being simply a number from the set N.(1)
No - halting programs are a subset of N, but there are uncountably
infinite non-halting ones.
(Assuming we identify all programs without taking the non-read bits
into account).
--
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics0425 253119 (")
UNSW SYDNEY 2052 [EMAIL PROTECTED]
Australiahttp://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
--~--~-~--~~~---~--~~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list
-~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Hi Bruno, what I undestand about the UD is that it generates all programs, a program being simply a number from the set N.(1) There exists an infinity of program which generates a set of growing function (different set), all the computable growing function are generated by all these programs(taken as a whole). Is this correct ? Is this metaset also diagonalisable ? I said no, because if it was then there is a contradiction with the premises that said that we generate *all* the programs that compute growing functions, thus either we cannot generate those programs (but that would be strange, that would means N is not enumerable ?) or the "metaset" is not diagonalisable... Where do I fail in my understanding ? Thanks, Quentin (1) I still have another problem with that because a program to be run need also the coding scheme (the instruction set of the turing machine that run it), which instruction set the UD use ? or how it construct it ? Le Mercredi 7 Juin 2006 15:11, Bruno Marchal a écrit : > Le 06-juin-06, à 20:50, [EMAIL PROTECTED] a écrit : > > Given a > > (countably infinite) sequence of functions f1, f2, ..., you say that > > fn(n)+1 must either be in the sequence OR not in the sequence. > > I am just showing constructively that if f1, f2,f3, ... is a well > defined sequence of computable functions from N to N, then the > "diagonal" function g (i.e. the one defined by g(n) = fn(n)+1) for each > n) cannot belong to the sequence f1, f2, f3, ... > The proof is constructive in the sense that if you give me some fk > equal to g, I can generate a contradiction from that. The contradiction > being that g(k) will be equal to g(k)+1. > > > But I will take some of my rare spare time (which I always have by > > diagonalization) > > I hope you will explain to me how you do that :) > > > to think some more about this absoluteness of > > computability and Church Thesis, etc. and try to understand this and > > solve the puzzle of where your straw-man argument is wrong. > > OK, I let you think a little more then. > > > Speaking of straw-men, it seems you are saying that machines simply > > running programs, without axioms and inference rules, are like zombies. > > Where am I saying that? > > > Zombies are how I would traditionally think of machines, but you seem > > to be saying that the axioms and inference rules somehow breathe life > > into the machine. > > Not really. Axioms and inference rule just makes it possible for the > machine to develop (third person describable) beliefs. The relation > between computation and proof are subtle. Let us be sure everyone > understand Church thesis (and its non constructive price) before moving > on the subject of theories and chatting machines. I could say things > but it will adds confusions at this stage. > Also zombie is a concept in the philosophy of mind, but we are not yet > really talking about that. > > OK, i give the solution tomorrow. All right? (answer only if you prefer > I give you more time, or else to make any other comments of course, but > by default I give the answer tomorrow). > > 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 06-juin-06, à 20:50, [EMAIL PROTECTED] a écrit : > Given a > (countably infinite) sequence of functions f1, f2, ..., you say that > fn(n)+1 must either be in the sequence OR not in the sequence. I am just showing constructively that if f1, f2,f3, ... is a well defined sequence of computable functions from N to N, then the "diagonal" function g (i.e. the one defined by g(n) = fn(n)+1) for each n) cannot belong to the sequence f1, f2, f3, ... The proof is constructive in the sense that if you give me some fk equal to g, I can generate a contradiction from that. The contradiction being that g(k) will be equal to g(k)+1. > But I will take some of my rare spare time (which I always have by > diagonalization) I hope you will explain to me how you do that :) > to think some more about this absoluteness of > computability and Church Thesis, etc. and try to understand this and > solve the puzzle of where your straw-man argument is wrong. OK, I let you think a little more then. > > Speaking of straw-men, it seems you are saying that machines simply > running programs, without axioms and inference rules, are like zombies. Where am I saying that? > Zombies are how I would traditionally think of machines, but you seem > to be saying that the axioms and inference rules somehow breathe life > into the machine. Not really. Axioms and inference rule just makes it possible for the machine to develop (third person describable) beliefs. The relation between computation and proof are subtle. Let us be sure everyone understand Church thesis (and its non constructive price) before moving on the subject of theories and chatting machines. I could say things but it will adds confusions at this stage. Also zombie is a concept in the philosophy of mind, but we are not yet really talking about that. OK, i give the solution tomorrow. All right? (answer only if you prefer I give you more time, or else to make any other comments of course, but by default I give the answer tomorrow). 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno,
Taking your assumption that I am a machine or number and so I can be
plugged into an equation (You = Tom or George...), I will say speaking
for myself that I would like a couple of days to think about this. If
we all are one person, then I will not be surprised that George feels
the same way. However, the "or" in the equation "You = Tom or
George..." is already non-constructive. :)
On the topic of non-constructiveness, the controversial use of the
excluded middle is in the context of infinity, not in the finite. I
previously agreed that you did not leave the finite. But now I have a
doubt. It seems that the diagonalization step you have already taken
actually uses the excluded middle for a countable infinity. Given a
(countably infinite) sequence of functions f1, f2, ..., you say that
fn(n)+1 must either be in the sequence OR not in the sequence.
But I will take some of my rare spare time (which I always have by
diagonalization) to think some more about this absoluteness of
computability and Church Thesis, etc. and try to understand this and
solve the puzzle of where your straw-man argument is wrong.
Speaking of straw-men, it seems you are saying that machines simply
running programs, without axioms and inference rules, are like zombies.
Zombies are how I would traditionally think of machines, but you seem
to be saying that the axioms and inference rules somehow breathe life
into the machine.
Tom
-Original Message-
From: Bruno Marchal <[EMAIL PROTECTED]>
To: everything-list@googlegroups.com
Sent: Tue, 6 Jun 2006 16:38:28 +0200
Subject: Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Hi,
Here is a little test, just for singling out a typical non
intuitionistic (non constructive) argument.
Such kind of argument makes me recall the tale: "The Little Prince"
written by the French pilot and novelist St-Exupery, where the Little
Prince asked the narrator (a pilot) to draw a sheep. But he can't draw
at all and fails badly in all his attempt to draw a sheep, so that
after a while, and because the Little Prince insisted so much,
eventually he decided to draw just a box, and told the little Prince
that the sheep was in the box.
Well, classical mathematicians does that all the time: actually they do
it each time they prove the existence of some object without exhibiting
precisely that object. Constructivist and engineers can be
disappointed, but platonist or classical mathematicians are quite cool
with such non-constructive proof.
I know by experience that even if I give the solution of the *puzzle*,
many people does not really see the non constructive step. So let me
first illustrate such a non-constructive reasoning on a very cute
example.
It is a "well known" proof that there exist irrational numbers x, y,
such that x^y is rational. We don't ask that x should be different of
y. The question is really (in english): is it possible that a
irrational number exponentiated by an irrational number gives a
rational number?
(I recall that a positive real number r is rational iff there exist
natural numbers n and m such that r is equal to m/n. r will be said
to be irrational if r is not rational. A typical irrational number is
the square root of 2, written sqrt(2)).
Here is the delightful proof by Jarden.
First note that a real number is either rational or ... irrational.
Right?
Well, if you say "yes" to this, you have already leave the constructive
area You have accepted the principle of excluded middle saying that
for any well-defined proposition p, either p is true, or p is false. In
this case p is, for some real number r, the proposition "r is
rational". The excluded middle principle gives then: "r is rational or
r is not rational", or "r is rational or is irrational".
Good ... So you agree that the real number sqrt(2) ^ sqrt(2), that is:
the (square root of two) exponentiated up to the (square root of two)
is rational or irrational. Right?
So we have just two cases to consider:
1) sqrt(2) ^ sqrt(2) is rational. Well, in that case we have a
solution: x = y = sqrt(2).
2) sqrt(2) ^ sqrt(2) is irrational. In that case just take x =
(sqrt(2) ^ sqrt(2)), and y = sqrt(2). Then, if you remember elementary
algebra, i.e. that ((a^b)^c) = a^(bc), then you see that x^y = 2 which
is rational of course.
So in all cases we have end up with an irrational which exponentiated
up to some irrational gives a rational, and we have solve the existence
problem. If you ask me a precise (constructive) solution, this
reasoning is not satisfactory. But the reasoning is far from hopeless:
the solution is given to you in a box, the box (set) containing the
couple (sqrt(2) , sqrt(2)) and the couple (sqrt(2) ^ sqrt(2) ;
sqrt(2)). I can, like St-Exupery, tell you that the solution is in the
two-elements box:
{ (x = sqrt(2) ; y = sqrt(2)) (x = sqrt(2) ^ sqrt(2) ; y =
sqrt(
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Hi,
Here is a little test, just for singling out a typical non
intuitionistic (non constructive) argument.
Such kind of argument makes me recall the tale: "The Little Prince"
written by the French pilot and novelist St-Exupery, where the Little
Prince asked the narrator (a pilot) to draw a sheep. But he can't draw
at all and fails badly in all his attempt to draw a sheep, so that
after a while, and because the Little Prince insisted so much,
eventually he decided to draw just a box, and told the little Prince
that the sheep was in the box.
Well, classical mathematicians does that all the time: actually they do
it each time they prove the existence of some object without exhibiting
precisely that object. Constructivist and engineers can be
disappointed, but platonist or classical mathematicians are quite cool
with such non-constructive proof.
I know by experience that even if I give the solution of the *puzzle*,
many people does not really see the non constructive step. So let me
first illustrate such a non-constructive reasoning on a very cute
example.
It is a "well known" proof that there exist irrational numbers x, y,
such that x^y is rational. We don't ask that x should be different of
y. The question is really (in english): is it possible that a
irrational number exponentiated by an irrational number gives a
rational number?
(I recall that a positive real number r is rational iff there exist
natural numbers n and m such that r is equal to m/n. r will be said
to be irrational if r is not rational. A typical irrational number is
the square root of 2, written sqrt(2)).
Here is the delightful proof by Jarden.
First note that a real number is either rational or ... irrational.
Right?
Well, if you say "yes" to this, you have already leave the constructive
area You have accepted the principle of excluded middle saying that
for any well-defined proposition p, either p is true, or p is false. In
this case p is, for some real number r, the proposition "r is
rational". The excluded middle principle gives then: "r is rational or
r is not rational", or "r is rational or is irrational".
Good ... So you agree that the real number sqrt(2) ^ sqrt(2), that is:
the (square root of two) exponentiated up to the (square root of two)
is rational or irrational. Right?
So we have just two cases to consider:
1) sqrt(2) ^ sqrt(2) is rational. Well, in that case we have a
solution: x = y = sqrt(2).
2) sqrt(2) ^ sqrt(2) is irrational. In that case just take x =
(sqrt(2) ^ sqrt(2)), and y = sqrt(2). Then, if you remember elementary
algebra, i.e. that ((a^b)^c) = a^(bc), then you see that x^y = 2 which
is rational of course.
So in all cases we have end up with an irrational which exponentiated
up to some irrational gives a rational, and we have solve the existence
problem. If you ask me a precise (constructive) solution, this
reasoning is not satisfactory. But the reasoning is far from hopeless:
the solution is given to you in a box, the box (set) containing the
couple (sqrt(2) , sqrt(2)) and the couple (sqrt(2) ^ sqrt(2) ;
sqrt(2)). I can, like St-Exupery, tell you that the solution is in the
two-elements box:
{ (x = sqrt(2) ; y = sqrt(2)) (x = sqrt(2) ^ sqrt(2) ; y =
sqrt(2)) }
But I cannot tell you which one, among the two solutions, is the
correct one.
Put in a different way I did prove a non-constructive OR proposition. I
have proved that
["x = sqrt(2) , y = sqrt(2)" is the solution] OR ["x= sqrt(2) ^
sqrt(2) ; y = sqrt(2)" is the solution].
And the or is non constructive because my reasoning does not allow us
to choose between the solution proposed on the left of the "or" or if
it is the one on the right of the "or".
In this present case, highly complex number theory (including elliptic
function theory, modular form, etc.) can settle the disjunction
constructively, but in theoretical computer science, on the contrary,
we will met many non-constructive "or" which can be proved being
necessarily non constructive. That means the non constructive solution
is the best we can ever hope for.
And that will be the case for the solution of the *puzzle*.
I don't want to jeopardize the pleasure of searching that solution, and
so I let you think a little bit more. Normally, with what Jesse and
Hall (notably) told, and what you have already seen, + the present
post, you have all the tools in the hands to explain exactly and
precisely how we can generate all computable functions in a way
vaccinated from the diagonalization procedure.
Of course, the "or" of the first person talk about its future personal
memory in the Washington Moscow duplication is also a special sort of
non constructive OR. Also, in the field of theoretical artificial
intelligence (or computational learning theory), it can be shown that
almost all "OR" are necessarily non constructive, making almost the
entire field completely empty from an intuitionist perspective.
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Le 05-juin-06, à 18:37, Tom Caylor a écrit : Not to try to answer the Puzzle, but just some thoughts for the conversation: That's the right spirit! At one glance, it seems that the argument is trying to transcend Godel's Incompleteness theorems. The Universal Language is trying to be both universal (complete) and consistent. The Universal Language is trying to be universal, and actually will succeed, if we accept Church thesis. That is, concrete languages like fortran, python, java, c++ , which can all be proved equivalent with respect to the ability to define *computable functions*, *are* universal once we accept Church thesis. But now let me say something quite important. The term "consistent" is not genuinely used here. Consistency is said about a THEORY, and until now we are just talking about "programming language" or machine. A theory is inconsistent if it proves a falsity, but a programming language just prove nothing. There is no axioms, nor any inference rules. There is no theory (not yet!); just primitive instructions which can be used to explain how to compute functions and which can be interpreted by some entities/machines. I am not saying your intuition fails you completely because we are indeed very near a proof of incompleteness theorem for ALL *theories*, but this will be a consequence (here) of accepting Church thesis, and thus understanding how fortran (say) can escape the use of diagonalization for going outside the sequence of functions defined in the language. That is, at some point you will see that incompleteness of theories, i.e. with respect to provability, is a consequence of completeness of universal machine/language, that is with respect to computability. Of course you make me anticipating a little bit, but once you will see that Church thesis CT can be consistently assumed despite the diagonalization, you will see that (with CT): 1) the notion of COMPUTABILITY is ABSOLUTE, and will not depend on any choice of (universal) language, formal system or machine: there exist universal languages (or machines), and they are all equivalent with respect of the definable, codable, describable, computable functions. but then as a consequence (and that's a part of the price): 2) the notion of PROVABILITY is necessarily RELATIVE, and will always depend on the choice of a particular formal system or machines. In particular there will never be any universal theory, even if the discourse domain is restricted just to positive integers or natural numbers. Ah. You see computer science is nice: it assesses both the relativist, at the level of theories and proof, and the absolutist, at the level of programming languages and computations. A good understanding of this will help you later to get a better appreciation of G and G*, which show that, although provability is a relative notion, there are universal feature of provability which can be captured by some modal logics. This Puzzle seems to corresponding to part of Step 7 in your Universal Dovetailer Argument (UDA). In that Step, you perhaps answer the Puzzle so I don't want to simply quote the answer, which might short-circuit my/our understanding. I'm not sure. Step seven introduces the UD and thus relies on Church thesis and I suppose people already knows why the UD and CT is possible despite diagonalization. But I have a problem with answering that the programs which conclude that 0 = 1 simply run forever. Couldn't you build any "complete" system or theories by simply letting programs run forever. You seem to be close to the right idea here ... This seems to be an artificial/arbitrary path to the truth. Couldn't you conclude whatever you want with this method? Perhaps I'm just proving your point. ... but a little bit less here :) PS Rereading some recent mails I wrote, I am ashamed of my style (when I complete a sentences!) and by my enduring mishandling of the singular/plural (the "s" problem). Please accept my apologies, and don't hesitate to correct me or to ask questions in front of ambiguities. Thanks for the interest anyway. It is probably mainly because of English being not your native language. Alas this is only partially true. Well, perhaps it is due to my use of both english and french all the time, but I have a tendency to mess up the "s" in french too. The "s" rule are 90% opposed in french and english. A deeper explanation could perhaps be related to the reason-&-person thread! Once you allow, like Parfit and some people in this list to do thought experiments in which amnesia is accepted, then, as I have already try to explain to Lee Corbin some month ago, you will converge toward the idea that there is only one person possible. For example, if you think that after a duplication Washington/Moscow both of "you" continue to be you *at the first person*, then you should already accept that all the descendants of the amoeba, that is all of us, are in reality the same person
Re: *THE* PUZZLE (was: ascension, Smullyan, ...)
Bruno Marchal wrote: > More comments on George Levy + *THE PUZZLE*. > > > Le 30-mai-06, à 20:42, George Levy a écrit : > > > > > To speak only for myself, I think I have a sufficient understanding of > > the thread. Essentially you have shown that one cannot form a set of > > all > > numbers/functions because given any set of numbers/functions it is > > always possible, using diagonalization, to generate new > > numbers/functions: the Plenitude is too large to be a set. > > > The first person plenitude will be too large or too complex to be a > mechanically generable set. > Just to give the exact wording of the conclusion. The explanation will > follow. I am glad you describe the tranfinite extensions of the set of > (growing or not) computable functions as a plenitude, and it models > indeed well the notion of first person plenitude on which we will > converge with Church thesis, and which describes a quasi solipsistic > transfinitely self-extending self, building from "controllable sets" to > bigger one. > But the sequel should show how Church thesis will force us to accept a > third person comp realm which will somehow transcend the limitation of > the first person, but then with *the* big price. > > > > > > This leads to > > a problem with the assumption of the existence of a Universal > > Dovetailer > > whose purpose is to generate all functions. I hope this summary is > > accurate. > > > > Completely. Let me give you *the puzzle*. What is wrong with the > following "refutation" of Church thesis: > > Let me just recall what is a computable function from N to N. It is > function from N to N which is such that it is exist a finite way to > explain how to compute it in a finite number of steps on any natural > numbers. More precisely: f is computable if there is a language L such > that f admits a finite code/program/description/number explaining how > to compute f(n), in a finite time on any number natural n. > I will say that that a language L is universal, if all computable > functions from N to N admit a code in L. > > A weak form of Church thesis can be put in this way: there exists a > universal language. > > I will say a digital (or finitely describable) machine M is universal > if M can "understand" a universal language L, in the sense of being > able to compute any computable functions described in L (and thus all > given that L is universal) . In term of digital machine, Church thesis > becomes: there exists a universal digital machine. > > Now what is wrong with the following argument: if there is an universal > language or machine, the computable functions can be described by > finite description in that language, or program for that machine. > Such a set is obviously enumerable. There is a bijection between N and > the set of those descriptions: > > 1 f1 > 2 f2 > 3 f3 > 4 f4 > etc. > > So the following function g is well-defined by: > > g(n) = fn(n) + 1 > > Then, to compute it on the number n (439 say), just generate the > description/program of f1 f2 f3 ... until fn, that is f439, apply it > on n to get fn(n), f439(439), and add 1 to get g(n) = fn(n)+1, that is > here: f439(439)+1. > But then g cannot be described in the language L! Why? Suppose g is > described by a code in the language L: then g belongs somewhere in the > list f1, f2, f3, f4, f5, Thus there would exist a number k such > that g = fk, and thus g(k) = fk(k); but g(k) = fk(k)+1. And thus > > fK(k) = fk(k)+1(*) > > And fk(k) is a well defined number given that the fi are all computable > functions from N to N. So I can substract fk(k) on both sides of (*) > just above, and I get 0 = 1 (contradiction). So there is no universal > language, we cannot generate all computable functions, still less, > then, to dovetail on them. > > Where is the error? How could Church still assert that its > "lambda-conversion calculus" (an ancestor of Lisp) is universal? What > about Fortran, Lisp, Python or other Rational Unitary Matrices? > > I (re)assure you (?), I will keep Church thesis, without which there is > no just no UD. What does the above reasoning really prove then? What > price will be asked upon us for keeping consistently our belief in > universal language and universal machine? > > It is not important to find the answer, but it will be capital to > understand it, and for that, it is capital to get the question, to see > the problem. I think that you, George, have seen the problem, and I am > just making higher the probability that others see as clearly as > possible the problem too. Hal and Jesse made big hints toward the > solution but I am not sure they have put the fingers on the very very > pricy consequence (?). > Not to try to answer the Puzzle, but just some thoughts for the conversation: At one glance, it seems that the argument is trying to transcend Godel's Incompleteness theorems. The Universal Language is trying to be both universal (complete) and consistent. This Puzzle seems to correspondin
