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 -~--~~~~--~~--~--~---