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
A calculus of personal identity (was:*THE* PUZZLE)
Bruno Marchal writes: > 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 (?)). The problem hinges on an answer to the question, what criteria must be satisfied for two instantiations of a person to be the "same" person? In the world with which we are familiar, most people would agree that there is an objectively right or wrong answer. Our brains have evolved so that we are sure that we are the same person today as we remember being yesterday, and will remember having been tomorrow. I might add that this isn't a view that is subject to revision in the light of new information, like the belief that the world is flat; rather, it has been so fundamental to our evolution that it has a tenacity at the visceral level that is only otherwise seen in the delusions of the psychotic patient. But evolution has not had to cope with teleportation, mind duplication, duplication with partial amnesia in one copy, partial or complete mind merging, and all the other fantastic possibilities which may or may not one day be realised. If it had (or if it will, in the far future), we might be left with a view of personal identity something like that espoused by Lee Corbin, where each copy is regarded as "self" and the (selfish) aim of life is not to preserve a single linear temporal sequence of related copies, but to maximise the total number of copies, even at the cost of a single individual's death. Returning to the question of teleportation and probabilities, I would say that objectively there is only one unequivocal answer: you don't survive the experiment at all, but people who look like you and believe they are you materialise in Washington, Sydney and Beijing with P=1. Subjectively, I would try to apply the (delusional, or may as well be delusional) belief that you are a single person persisting through time as best as I can to the unnatural situation. I think that the best answer in the two-step teleportation (Br..>W,M; M..>S,Be) is that you should expect P(W)=1/2, P(S)=P(Be)=1/4. I prefer this to an equal P of 1/3 for each destination city because (again, due to our evolved psychology, not because it is the "truth") we anticipate all possible candidates for the "next moment", but once this next moment arrives, all the other concurrent copies become irrelevant, and the only thing that matters is the *next* next moment. Consistent with this method, if there is complete amnesia for all that happens in Moscow, it is as if that stage has not occurred, and from Br you can anticipate arriving in W, S and Be with equal probability. In the case of intermediate levels of amnesia in Moscow, I suppose this would yield intermediate probabilities. However, I'm not very confident about this, because our minds are simply not made to deal with the situation. It would be like trying to define a subjective "up" and "down" in an environment where the direction of gravity is rapidly changing: you would probably just get very dizzy! Stathis PapaioannouExpress 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, ...)
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 -~--~~~~--~~--~--~---
