Re: Key Post 1, toward Church Thesis and Lobian machine
Le 11-févr.-08, à 17:58, Mirek Dobsicek a écrit : But thanks to that crashing, *Church thesis remains consistent*. I would just say An existence of a universal language is not ruled out. I am ok with you. Consistent (in math) means basically not rule out. Formally consistent means not formally ruled out, or not refutable. That is: Consistent(p) is the same as ~ Provable(~ p) ~ = negation like Provable(p) is equivalent with ~ Consistent( ~ p) All right... Now, let me just rephrase few points of the key post one more time. I will try to be picky with wording. Points which are not mentioned - I fill comfortable with. 1\ There is no language/algorithm/procedure/machine which can describe/execute all total computable functions. I guess (and have some confirmation below) that you mean here that there is no language/algorithm/procedure/machine which can describe/execute all total computable functions AND ONLY TOTAL COMPUTABLE FUNCTIONS. Right? Otherwise you would be saying that Church Thesis is false. 2\ There exists non-empty set of all machine computable functions (inevitably includes both total and strict partial functions). Let us call this set MC (machine computable). OK. (this confirms what I say above). 3\ Church himself *defined* the set of so-far-known-computable-functions as those computable by lambda calculus. Well, for Church, Lambda does define the set of all computable (total and partial) functions, not just the so-far-known-comp-functions. 4\ What we use to call a *Church thesis* today says, that MC is in fact equal to the set of functions computable by lambda calculus. Yes. 5\ Church thesis is refutable. Yes. (It is enough to give a function which we can compute, but which would not be Turing or Lambda computable. * * * Something else: to us verify MM = SII(SII) does crash the system: SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = ... (crashing). Working with SK combinators, I had a bit problems with omitted parenthesis. Just avoid writing the left parentheses. SII(SII) is really put for (((SI)I)((SI)I)) which is conceptually clearer, but practically unreadable. Also it was not clear to me what is the meaning of eg. (SKK) since S is expected to take three arguments. OK, my fault. It means the construct is stable and waiting for more argument. so SKK, without any added inputs remains SKK and constitutes a combinator described as being SKK. Such construct are useful for making data structures for example. Such construct are called normal forms. The idea is that the 2-variables function Lx Ly (x + y) when applied on just one argument, 5, say, gives a new function Ly (5 + y), which is a 1-variable function adding 5 to its input. It is the way Schoenfinkel managed to have only function of one argument. What helped me was the unlambda language (http://www.madore.org/~david/programs/unlambda/) At first sight this is just lambda calculus (and thus combinator) with awkward notation So here is my crashing sequence (yep, yours is shorter) (I don't expand the I term to keep it short) Good idea. I is really a macro for SKK. I hope everybody see that SKKx = x for any x. SKKx = Kx(Kx) = x. (cf Sabc = ac(bc); Kab = a) SII(SI(S(KI)I)) Hmmm... ok, that's working, but S(KI)I is really I, and you could have make something simpler ... a reference implementation in unlambda: ```sii``si``s`kii the ` stands for 'apply' operation, aka left parenthesis. You really need spectacles here ... with a small modification ```sii``si``s`k.ui we can achieve the computer to print u in an endless loop. .u is a special function with a side effect of printing the character u. You are not supposed to use anything but K and S (or anything you have already define with K and S) ... I'm not completely sure what you mean by k.ui (the dot) ... hmm... I see, it prints, well ok then. I will try to comment your UDA paper post asap. Best, 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 [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
But thanks to that crashing, *Church thesis remains consistent*. I would just say An existence of a universal language is not ruled out. I am ok with you. Consistent (in math) means basically not rule out. Formally consistent means not formally ruled out, or not refutable. That is: Consistent(p) is the same as ~ Provable(~ p) ~ = negation like Provable(p) is equivalent with ~ Consistent( ~ p) All right... Now, let me just rephrase few points of the key post one more time. I will try to be picky with wording. Points which are not mentioned - I fill comfortable with. 1\ There is no language/algorithm/procedure/machine which can describe/execute all total computable functions. 2\ There exists non-empty set of all machine computable functions (inevitably includes both total and strict partial functions). Let us call this set MC (machine computable). 3\ Church himself *defined* the set of so-far-known-computable-functions as those computable by lambda calculus. 4\ What we use to call a *Church thesis* today says, that MC is in fact equal to the set of functions computable by lambda calculus. 5\ Church thesis is refutable. * * * Something else: to us verify MM = SII(SII) does crash the system: SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = ... (crashing). Working with SK combinators, I had a bit problems with omitted parenthesis. Also it was not clear to me what is the meaning of eg. (SKK) since S is expected to take three arguments. What helped me was the unlambda language (http://www.madore.org/~david/programs/unlambda/) So here is my crashing sequence (yep, yours is shorter) (I don't expand the I term to keep it short) SII(SI(S(KI)I)) a reference implementation in unlambda: ```sii``si``s`kii the ` stands for 'apply' operation, aka left parenthesis. with a small modification ```sii``si``s`k.ui we can achieve the computer to print u in an endless loop. .u is a special function with a side effect of printing the character u. Best, Mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
Bruno, thanx. You play loose with 'context': not observed with the baby's diapers, but observed with K and S - (what I didnot specify at all, in the contrary: I spoke about (any) symbol in the sentence what fou failed to misunderstand rightly. ) You seem to comfortably refer to 'matter' (vs numbers) while we are not on 'physical' basis. (I still cannot fathom how the originating 'numbers' (integers) have the consciousness and will to 'generate' the world. I did not learn that, all I learned was: they are tools I can manipulate. (Of course I am no mathematician and 'learned' mostly applied math). One cow has 4 legs, eo ipso 4 cows have 16. It does not solve Hal's Nothing problem. Your 'numbers' religion still requires a 'numbers God' - or did they bootstrap themselves? This view does not represent a different one to any other what people believe in. I confess freely in my narrative that ...and further BACK we know nothing, I 'imagine' a behavior and take it from there to arrive at the situation we think we see today - using (MY) common sense. I have to see something 'better' than what I use to accept it - instead. I am glad you replied BEFORE your coffe, So I could (more or less) follow it. John M On Thu, Feb 7, 2008 at 10:41 AM, Bruno Marchal [EMAIL PROTECTED] wrote: John, Le 06-févr.-08, à 23:56, John Mikes a écrit : Bruno, here is my out of order and off topic remark. We are here in theoretical theorizing by theory-laden theoretic ways. It is ALL the product of a mental exercise. Even a Loebian kick in the ass can be a theoretical halucination. I could agree. But then *all* theories are hallucinations, all right? Even the baby's theories according to which they have a mother is a theoretical hallucination, most probably emerging from a conversation between billions of connected speculative amoeba/neurons betting on some personal reality ... You wrote: ... - ... But does 'M exist? ,,, - ... (Never mind in what context. ) exist is a hard word. I am not so sure. I mean that in some context the question is clearcut and meaningful (independently of the complexity of solving it). In the current context K and S exists, by definition, and all their descendants (their combinations) exist, by definition too. Now they have all a rather well-defined behavior due to the behavior of K and S, and the question of the existence of M (defined by its duplicator behavior) is becoming a pure engineering problem. Ask me examples if this is not clear. Contemplating in a generalized way, I would say: Everything (not in Hal's sense) exists what we THINK of, if not otherwise: in our ideas. Yes sure. Actually K is so perverse (in the eyes of some logicians, like Church) that some wants to say that K does not make sense, and Curry (one of the (re)discover of K) defended the existence of K as an idea of thought. Yes sure: eliminating something is a widespread idea. Does 'K' or 'S' have a better than mental existential veracity? I would suggest you to take a look at my paper Theoretical computer Science and the natural laws. In that paper I sum up (a bit roughly) the Physics of Newton by K does not exists (in nature), and I sum up the Physics of Einstein-Podolski-Rosen-Everett-Deutsch-Zurek-Wooters, by S does not exist. Indeed K eliminate information (like a classical black hole) and S duplicates arbitrary informations (a problem in QM). So yes K and S are on the mind side, not on the matter side. But this is not needed in the present context, where I introduced S and K just as an example of programming language (typically already on the mind side). We can think of a symbol that it does or does not exist, it does not change that it DOES indeed exist in our mental domain. I don't understand that sentence. (don't confuse the symbol K with the primitive instruction K defined by Kxy = x, it is the left- projection or the right elimination: it send (x, y) on x (eliminating y). Do you have a better 'domain' (e.g. a physical existence)? I doubt. In our 1st person world it would not make sense. Physical existence is, by UDA, at best a first person (plural) construct. I recall you that in my theory (my favorite hallucination which I try to share with you) numbers and combinators and alike exists before anything material. Matter emerges as a relative border of the machines/numbers ignorance. I do have a better 'domain': numbers (integers). All the rest are number's hallucinations or first person perspectives. But some hallucination can last lawfully, and the question is why. With comp, the question can be made 100% math, and that makes comp testable. And if you don't like numbers, you could take directly combinators instead (their are just less known for contingent reason like we have digits).
Re: Key Post 1, toward Church Thesis and Lobian machine
John, Le 06-févr.-08, à 23:56, John Mikes a écrit : Bruno, here is my out of order and off topic remark. We are here in theoretical theorizing by theory-laden theoretic ways. It is ALL the product of a mental exercise. Even a Loebian kick in the ass can be a theoretical halucination. I could agree. But then *all* theories are hallucinations, all right? Even the baby's theories according to which they have a mother is a theoretical hallucination, most probably emerging from a conversation between billions of connected speculative amoeba/neurons betting on some personal reality ... You wrote: ... - ... But does 'M exist? ,,, - ... (Never mind in what context. ) exist is a hard word. I am not so sure. I mean that in some context the question is clearcut and meaningful (independently of the complexity of solving it). In the current context K and S exists, by definition, and all their descendants (their combinations) exist, by definition too. Now they have all a rather well-defined behavior due to the behavior of K and S, and the question of the existence of M (defined by its duplicator behavior) is becoming a pure engineering problem. Ask me examples if this is not clear. Contemplating in a generalized way, I would say: Everything (not in Hal's sense) exists what we THINK of, if not otherwise: in our ideas. Yes sure. Actually K is so perverse (in the eyes of some logicians, like Church) that some wants to say that K does not make sense, and Curry (one of the (re)discover of K) defended the existence of K as an idea of thought. Yes sure: eliminating something is a widespread idea. Does 'K' or 'S' have a better than mental existential veracity? I would suggest you to take a look at my paper Theoretical computer Science and the natural laws. In that paper I sum up (a bit roughly) the Physics of Newton by K does not exists (in nature), and I sum up the Physics of Einstein-Podolski-Rosen-Everett-Deutsch-Zurek-Wooters, by S does not exist. Indeed K eliminate information (like a classical black hole) and S duplicates arbitrary informations (a problem in QM). So yes K and S are on the mind side, not on the matter side. But this is not needed in the present context, where I introduced S and K just as an example of programming language (typically already on the mind side). We can think of a symbol that it does or does not exist, it does not change that it DOES indeed exist in our mental domain. I don't understand that sentence. (don't confuse the symbol K with the primitive instruction K defined by Kxy = x, it is the left- projection or the right elimination: it send (x, y) on x (eliminating y). Do you have a better 'domain' (e.g. a physical existence)? I doubt. In our 1st person world it would not make sense. Physical existence is, by UDA, at best a first person (plural) construct. I recall you that in my theory (my favorite hallucination which I try to share with you) numbers and combinators and alike exists before anything material. Matter emerges as a relative border of the machines/numbers ignorance. I do have a better 'domain': numbers (integers). All the rest are number's hallucinations or first person perspectives. But some hallucination can last lawfully, and the question is why. With comp, the question can be made 100% math, and that makes comp testable. And if you don't like numbers, you could take directly combinators instead (their are just less known for contingent reason like we have digits). --- Excuse my rambling and please, consider it 'entertainment' rather than discussion-post. Your rambling could help me to make things clearer perhaps, but ok, the deepest purpose here is fun and entertainment. Thanks for your attention. Now I will hallucinate a bit on a cup of coffee ..., Best, Bruno - On Wed, Feb 6, 2008 at 10:40 AM, Bruno Marchal [EMAIL PROTECTED] wrote: Le 05-déc.-07, à 23:08, Mirek Dobsicek a écrit : But thanks to that crashing, *Church thesis remains consistent*. I would just say An existence of a universal language is not ruled out. I am ok with you. Consistent (in math) means basically not rule out. Formally consistent means not formally ruled out, or not refutable. That is: Consistent(p) is the same as ~ Provable(~ p) ~ = negation like Provable(p) is equivalent with ~ Consistent( ~ p) Some thoughts: Thanks to Godel completeness theorem for the first order theory (1930) you can also read consistent(p) by there is a world satisfying p (a world where p is true). This relates a syntactical notion (the non existence of a chain of formula derived from the axioms by the use of the inference rules and ending with f) with a semantical: the existence of a mathematical structure satisfying the formula. At least in the frame of many formal classical theories, it is
Re: Key Post 1, toward Church Thesis and Lobian machine
Le 05-déc.-07, à 23:08, Mirek Dobsicek a écrit : But thanks to that crashing, *Church thesis remains consistent*. I would just say An existence of a universal language is not ruled out. I am ok with you. Consistent (in math) means basically not rule out. Formally consistent means not formally ruled out, or not refutable. That is: Consistent(p) is the same as ~ Provable(~ p) ~ = negation like Provable(p) is equivalent with ~ Consistent( ~ p) Some thoughts: Thanks to Godel completeness theorem for the first order theory (1930) you can also read consistent(p) by there is a world satisfying p (a world where p is true). This relates a syntactical notion (the non existence of a chain of formula derived from the axioms by the use of the inference rules and ending with f) with a semantical: the existence of a mathematical structure satisfying the formula. At least in the frame of many formal classical theories, it is related to the recurrent modal duality: Permitted p ~ Obligatory ~p Obligatory p ~ Permitted ~p Somewhere p ~ Everywhere ~p Everywhere p ~ Somewhere ~p Sometimes p ~ Always ~p Always p ~ Sometimes ~p Like the usual first order quantifiers: (Ax = for all x; Ex = it exists a x) Ex F(x) ~ Ax ~ F(x) Ax F(x) ~ Ex ~F(x) (all cats are ferocious it does not exist a non ferocious cat) And with formal provability we have also: Consistent p ~ provable ~p Provable p ~ consistent ~p But yes, it is by allowing the machine to crash, and actually by allowing it to crash in a *necessarily* not always predictible way, which makes it possible to be universal. In a nutshell: Universality == insecurity kicking back reality and then (knowledge of your universality) == (knowledge of your relative insecurity) (knowledge of a kicking back reality) === anticipating an independent reality (knowledge of your universality) = lobianity (this I intend to explain later) Mirek asked also in trhe same post: And my last question, consider the profound function f such that f(n) = 1 if there is a sequence of n consecutive fives in the decimal expansion of PI, and f(n) = 0 otherwise Is this an example of a partial computable function? Yes. Or is this function as such already considered as un-computable function? It could be uncomputable on some value, that is, everywhere the function has value 1, you can in principle compute it (just search the sequence: if it exists you will find it because PI is constructive). If the value is zero, it could be that you will be able to know it, but it could be that you will never know it ... * * * Something else: Mirek, Brent, Barry, Tom (and all those inclined to do a bit of math): don't read what is following unless you don't want to find the crashing combinators by yourself. I give the solution for the crashing combinators: it is enough to ... mock a mockingbird. Raymond Smullyan calls mocking bird a combinator M such that Mx = xx. It is a sort of diagonalisor or duplicator. Now if you apply M on itself, M, that is if you evaluate MM, this matches the left of equation Mx = xx, so MM gives MM gives MM gives MM gives MM ... (crashing!). But does M exists? If you recall well, we know only the existence of K and S, and their descendants: like KK, KS, S(KS), SK(KS)(S(KK)), ... (Recall we don't write any left parenthesis, but something like SK(KS)(S(KK)) really abbreviate the result of applying (SK) to (KS) i.e. ((SK)(KS)) on (S(KK)), i.e. (((SK)(KS))(S(KK))). each combinator can be thought as a function of one variable (itself varying on the combinators). We search a combinator playing the role of M (defined by its behavior Mx = xx). We have only K, S, and their combinations. And we have the two axioms giving the behavior of K and S. Kxy = x K axiom and Sxyz = xz(yz) S axiom Explanation. You can see K as a projector sending (xy) on x, for any y. (imo it is the *subjective* entity per excellence, in particular K discards or eliminate informations like projection does. Church will not allow K or any eliminators in its main systems). Functionally K is Lx Ly . x The variable y is abstracted in some irrelevant way. We want Mx = xx. But xx does not match either x or xz(yz), so that we could use the axioms above directly. But imagine we dispose of the subroutine combinators I such that Ix = x. The identity combinators. Then Mx = xx = Ix(Ix), and this does match xz(yz), so that Ix(Ix) is really SIIx (in Sxyz = xz(yz), so SIIx = Ix(Ix) = xx. So SII can play the role of M, it behaves like M. We could define M by SII. Let us verify MM = SII(SII) does crash the system: SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = ... (crashing). Now we have to still find an identity combinator I such that Ix = x. Now x does match the right of the first axiom Kxy = x. Except that K on
Re: Key Post 1, toward Church Thesis and Lobian machine
Bruno, here is my out of order and off topic remark. We are here in theoretical theorizing by theory-laden theoretic ways. It is ALL the product of a mental exercise. Even a Loebian kick in the ass can be a theoretical halucination. You wrote: ... - ... But does 'M exist? ,,, - ... (Never mind in what context. ) exist is a hard word. Contemplating in a generalized way, I would say: Everything (not in Hal's sense) exists what we THINK of, if not otherwise: in our ideas. Does 'K' or 'S' have a better than mental existential veracity? We can think of a symbol that it does or does not exist, it does not change that it DOES indeed exist in our mental domain. Do you have a better 'domain' (e.g. a physical existence)? I doubt. In our 1st person world it would not make sense. --- Excuse my rambling and please, consider it 'entertainment' rather than discussion-post. John M On Wed, Feb 6, 2008 at 10:40 AM, Bruno Marchal [EMAIL PROTECTED] wrote: Le 05-déc.-07, à 23:08, Mirek Dobsicek a écrit : But thanks to that crashing, *Church thesis remains consistent*. I would just say An existence of a universal language is not ruled out. I am ok with you. Consistent (in math) means basically not rule out. Formally consistent means not formally ruled out, or not refutable. That is: Consistent(p) is the same as ~ Provable(~ p) ~ = negation like Provable(p) is equivalent with ~ Consistent( ~ p) Some thoughts: Thanks to Godel completeness theorem for the first order theory (1930) you can also read consistent(p) by there is a world satisfying p (a world where p is true). This relates a syntactical notion (the non existence of a chain of formula derived from the axioms by the use of the inference rules and ending with f) with a semantical: the existence of a mathematical structure satisfying the formula. At least in the frame of many formal classical theories, it is related to the recurrent modal duality: Permitted p ~ Obligatory ~p Obligatory p ~ Permitted ~p Somewhere p ~ Everywhere ~p Everywhere p ~ Somewhere ~p Sometimes p ~ Always ~p Always p ~ Sometimes ~p Like the usual first order quantifiers: (Ax = for all x; Ex = it exists a x) Ex F(x) ~ Ax ~ F(x) Ax F(x) ~ Ex ~F(x) (all cats are ferocious it does not exist a non ferocious cat) And with formal provability we have also: Consistent p ~ provable ~p Provable p ~ consistent ~p But yes, it is by allowing the machine to crash, and actually by allowing it to crash in a *necessarily* not always predictible way, which makes it possible to be universal. In a nutshell: Universality == insecurity kicking back reality and then (knowledge of your universality) == (knowledge of your relative insecurity) (knowledge of a kicking back reality) === anticipating an independent reality (knowledge of your universality) = lobianity (this I intend to explain later) Mirek asked also in trhe same post: And my last question, consider the profound function f such that f(n) = 1 if there is a sequence of n consecutive fives in the decimal expansion of PI, and f(n) = 0 otherwise Is this an example of a partial computable function? Yes. Or is this function as such already considered as un-computable function? It could be uncomputable on some value, that is, everywhere the function has value 1, you can in principle compute it (just search the sequence: if it exists you will find it because PI is constructive). If the value is zero, it could be that you will be able to know it, but it could be that you will never know it ... * * * Something else: Mirek, Brent, Barry, Tom (and all those inclined to do a bit of math): don't read what is following unless you don't want to find the crashing combinators by yourself. I give the solution for the crashing combinators: it is enough to ... mock a mockingbird. Raymond Smullyan calls mocking bird a combinator M such that Mx = xx. It is a sort of diagonalisor or duplicator. Now if you apply M on itself, M, that is if you evaluate MM, this matches the left of equation Mx = xx, so MM gives MM gives MM gives MM gives MM ... (crashing!). But does M exists? If you recall well, we know only the existence of K and S, and their descendants: like KK, KS, S(KS), SK(KS)(S(KK)), ... (Recall we don't write any left parenthesis, but something like SK(KS)(S(KK)) really abbreviate the result of applying (SK) to (KS) i.e. ((SK)(KS)) on (S(KK)), i.e. (((SK)(KS))(S(KK))). each combinator can be thought as a function of one variable (itself varying on the combinators). We search a combinator playing the role of M (defined by its behavior Mx = xx). We have only K, S, and their combinations. And we have the two axioms giving the behavior of K and S. Kxy =
Re: Key Post 1, toward Church Thesis and Lobian machine
Hi Barry and Mirek, (and Brent, David, ). Thanks for telling, New year is good for me. As you know I am a bit of a platonist so time has no real meaning for me. I told you that this year I'm teaching Church thesis at my Saturday Course on computer science for a large (not necessarily mathematician) public, and I am much slow there than here (we have not yet begin the bijection!). I will take the time to make all things clear, even for those without any knowledge in math, but of course it would help if they dare to ask questions. The key post is certainly not perfect, and will evolve thanks to you and my students. In the meantime I will provide a little summary (which I have already try to make, but it goes repeatedly in the trash because it is too long). I intent also to give some sample of universal system. By a universal system, I mean the whole complex of a universal machine, its formal universal language, the set of its instructions, codes, etc. Let me give you already an example or two. The Shepherdson Sturgis coffee-bar formal definition of computability. (A variant by Cutland). Here is a job offer in an (infinite) coffee bar in Platonia. (Infinite, just for making things a bit simpler.) The basic instructions are the following 3 types + 1. a. - Please add a coffee cup on table 17 (say) b.- Please put on table 24 as many coffee cups than there are coffee cups on table 42 (say) c. - Please make sure there is no more coffee cups on table 56 The last instruction is a bit more difficult. To do the job you need minimal ability to read a language in which the preceding instructions can be described. Also, to economize paper (yes in Platonia Forest are protected too!), the instruction a. - Please add a coffee cup on table 17 (say) is written S(17) b.- Please put on table 24 as many coffee cups than there are coffee cups on table 42 (say) is written T(42, 24) c. - Please make sure there is no more coffee cups on table 56 is written Z(56) (Z is for zero cup of coffee) For the last instruction you have to know that a job is the given of an ordered, even numbered instructions. For example, a typical Job is 1) Z(1) 2) S(1) 3) S(2) Here the job consists in making sure there are no more coffee cups on table one. Then to add a cup of coffe on table one, and then add a cup of coffee on table 2. Now here is the last instruction: d. - if the number of coffee cups on table 14 (say) is equal to the number of coffee cups on table 45 (say) then proceed from the instruction 5 (say) described in your job. In case there are no instruction numbered 5, stop (the job will be said to be completed); in case the number of coffee cups on table 14 is not equal to the number of coffee cups on table 45, then proceed from the next instruction. It is written: J(14, 45, 5). DEFINITION: A function f from N to N is said to be Shepherdson Sturgis coffee bar computable, if there is a job (a list of numbered instructions) such that when putting n cups of coffee on table one, then, after the job is completed there is f(n) cups of coffee on table one. Similarly, a function h from NXN to N is said to be Shepherdson Sturgis coffee bar computable if there is a job such that, after having put n cups of coffee on table one and m cups of coffee on table two, then, after the job is completed there is h(n,m) cups of coffee on table one. I have to go, so I give some Exercise for the week-end (I provide solution monday) 1) find a short job crashing the coffee bar computer. Such a job will never be completed. 2) find a job which computes addition (which is of course a function from NXN to N) 3) using the preceding job, find a job which computes multiplication. 4) is the following proposition plausible: a function from N to N is intuitively computable if and only if it can be computed by some coffee bar job. 5) describe informally the coffee-bar language, and, choosing an order on its alphabet, write the first 7 jobs in the lexicographical order. The alphabet contains all symbols needed in the jobs, including commas, parentheses, etc. + some grammatical rules making clear that Z(23) is a good instruction, but 23(Z) is not, ... Bruno Le 13-déc.-07, à 01:27, Barry Brent a écrit : Seems fine to me too. Barry On Dec 12, 2007, at 12:58 PM, Mirek Dobsicek wrote: Hi Bruno, From what you told me, I think you have no problem with Cantor 's diagonal. Yep, no problem. Are you ok with the key post, that is with the two supplementary uses of the diagonal in the enumerable context? 95% grasped, and for the rest I'm lacking time to do a sufficient amount of scribes in order to get it completely. But nothing fundamental ... Now, I'm very busy with finishing my phd thesis (study and simulations of a certain two-qubit procedure, a sort of benchmark). I guess, I'll be fine
Re: Key Post 1, toward Church Thesis and Lobian machine
Hi Bruno, From what you told me, I think you have no problem with Cantor 's diagonal. Yep, no problem. Are you ok with the key post, that is with the two supplementary uses of the diagonal in the enumerable context? 95% grasped, and for the rest I'm lacking time to do a sufficient amount of scribes in order to get it completely. But nothing fundamental ... Now, I'm very busy with finishing my phd thesis (study and simulations of a certain two-qubit procedure, a sort of benchmark). I guess, I'll be fine at the beginning of the New Year. Sincerely, Mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
Seems fine to me too. Barry On Dec 12, 2007, at 12:58 PM, Mirek Dobsicek wrote: Hi Bruno, From what you told me, I think you have no problem with Cantor 's diagonal. Yep, no problem. Are you ok with the key post, that is with the two supplementary uses of the diagonal in the enumerable context? 95% grasped, and for the rest I'm lacking time to do a sufficient amount of scribes in order to get it completely. But nothing fundamental ... Now, I'm very busy with finishing my phd thesis (study and simulations of a certain two-qubit procedure, a sort of benchmark). I guess, I'll be fine at the beginning of the New Year. Sincerely, Mirek Dr. Barry Brent [EMAIL PROTECTED] http://home.earthlink.net/~barryb0/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
Hi Brent, Mirek, David, From what you told me, I think you have no problem with Cantor 's diagonal. Are you ok with the key post, that is with the two supplementary uses of the diagonal in the enumerable context? Let me sum up, please consult the preceding posts for details. 1) Cantor: If f_1 f_2 f_3 f_4 represents the image of a candidate bijection from N to N^N, then the diagonal function g, defined by g(n) = f_n(n) + 1 gives a counter-example, that is, a function from N to N, which is not in the image of the candidate bijection. This works for any candidate bijection, so we can conclude that there are no bijections between N and N^N. 2) We restrict the set of all functions from N to N. Now we consider that the functions have to be computable, and this means that there exist a language in which we can define those functions. Lemma (= preliminary proposition): the set of things definable in a language L is enumerable. (All right?) Is there a universal language in which we can define all (total) computable function from N to N? a) Theorem: the answer to that question is NO, if it is asked that all expressions (= well formed instructions for one variable function, say) in the language define all AND ONLY ALL computable functions. Proof: if it was the case that all the expressions (for function of one variable) defines all total computable function from N to N, then, by the lemma, the set of such functions are not only enumerable, but can be enumerated mechanically, computably, etc. b) Theorem: if the answer is yes, then a universal machine cannot be securized by any machine. Oops: I'm interrupted. I let you try to finish this post. I come back on it friday, or next week. Please don't hesitate to ask me any question, or to make any remark, including meta-remarks, jokes, or whatever. It would help me to have an idea if most of you get the point or if most of you did not get it ... It is simple, but admittedly not so simple, sure. 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 [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
Le 07-déc.-07, à 00:22, Russell Standish a écrit : On Thu, Dec 06, 2007 at 03:37:10PM +0100, Bruno Marchal wrote: Thanks Russell. About the use of asshole I am afraid it is more popular, or vulgar, than I thought. You are very kind to tell me. Should I use dumb instead? The idea consists in not attributing No dumb is the wrong word. Dumb people can of course be quite creative (literally dumb means not able to speak, but derogatively it also means stupid, which is a slight on dumb people). All right. I knew only the derogative meaning. I would have gone with something like mindless robot - although this has problems of implying artificiality. Ah Ah I was expecting someone asking if the asshole I did mention (sorry), was not just the one we are used to call machine. As you say, this implies in general some artificiality, but not necessarily so. After all the doctrine of Mechanism (related to Descartes) is the thesis that we (actually only animals for Descartes) are machine. And this does not mean we are artificial. BTW note that the term artificial is artificial itself, and so is natural, and thus artificial, and thus natural, and thus artificial But yes, in the informal ,pregodelian sense of machine, the term machine is not so bad (and obviously more polite than the one I used). Perhaps mindless servant - you want to get across the idea of following orders to the letter without question. Mindless servant is rather good too, with the informal sense. But saying that a function is computable if it can be computed without mind can be considered as a definition as negative as saying that a computation can be done without invoking Gods. Term like mind, God are a bit problematic when used at the start of the enquiry. Doesn't trou de cul have a similar meaning to arsehole in French? Yes, literally. But trou de cul is a bit old fashioned. I suspect the closer translation might be connard though. Or the simpler con, which is used a lot, but it is not only vulgar, but also disrespectful for woman (like most insults in french). Best, 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 [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
Thanks Russell. About the use of asshole I am afraid it is more popular, or vulgar, than I thought. You are very kind to tell me. Should I use dumb instead? The idea consists in not attributing anything like intuition, intelligence, cleverness, etc. for the followers of unambiguous instructions. It will be clearer when I will give example of universal language, but I really do not want to do that to much quickly, because a main point here is that we can get rigorously many incompleteness and unsolvability results on formal language and machine without using any specific machine or formal theory. This is a key for learning to separate the different level of reasoning we will have to do. I hope you did not disturb too much the appetite of your mother's cousin's son :) Cheers, Bruno Le 06-déc.-07, à 00:01, Russell Standish a écrit : On Tue, Dec 04, 2007 at 03:55:50PM +0100, Bruno Marchal wrote: Hi David, Mirek, Tom, Barry and All, ... The cardinality of the set of computable functions. Thanks for this post. I was in the position of trying to explain your work to someone (actually a son of my mother's cousin) at a dinner party a couple of weeks ago, and having explained Cantor's diagonalisation proof of the uncountability of the reals, I got to the point about computable functions being countable and got stuck. I just had to say well its true, but I can't quite recall the proof!. Your exposition is eminently dinner-party standard, although I might use a different word than asshole! Cheers -- --- - A/Prof Russell Standish Phone 0425 253119 (mobile) Mathematics UNSW SYDNEY 2052 [EMAIL PROTECTED] Australiahttp://www.hpcoders.com.au --- - 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 [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
Hello Mirek, Le 05-déc.-07, à 23:08, Mirek Dobsicek a écrit : thank you for your post. I read it a couple of times in order to more or less grasp it, but it worth it. I have some questions... Suppose there is a secure universal machine M. The set of expressions it can compute provide a secure universal language L. That set is not only enumerable (given that it is a subset of an enumerable set) but above all, it can be enumerated effectively (by the ashole). What do you mean here by effectively? I understand it as you just want to emphasize that the set is really enumerable. I guess I will come back on this in the next post. But the point is that a set can be enumerable, yet NOT effectively enumerable. Effectively enumerable means enumerated by following unambiguous instructions in some language (universal or not). A dumb idiotic can do that. To sum up a bit: Recall that by a function from A to B, I always mean a function defined for all elements of A having value in B. In particular a function from N to N is defined on all natural number. To emphasize on this I will say sometimes TOTAL function. Then I will say strictly partial function for a function from S to N, when S is a proper subset of N. Cantor's diagonal on N^N shows that the set of functions from N to N, i.e. N^N, is not enumerable (uncountable, ... mathematician have a lot of synonyms). So there is no bijection from N to N^N. Let us define N^N-comp as the set of computable functions in the sense described in the key post. It is the set of total computable functions, or better described (but less usual) it is the total functions which are computable. Then N^N-comp is enumerable (indeed their corresponding set-of-instructions is a subset of all expressions in the language, which is already enumerable). Diagonalisation on N^N-comp shows that, although N^N-comp is enumerable, it is *not effectively enumerable*. The bijection between N^N-comp and N exist, yes, but is not a computable function. If it was, then the diagonal function g (with g(n) = f_n(n) +1) would be computable, in the list, and then 0 = 1, as I have try to explain. So it is really the bijection sending n on f_n which is not computable, and which makes g not computable. We can still believe there is a universal language in which we can define all total computable function, but then the language has to define more than the total computable one. In that case we get a language L which defines a more general class of computable functions, the one which are no more defined on all inputs. In that case the diagonal function g can be defined in the language, but then such function has to be undefined on its godel number k, that is, the number k such that g = f_k. And the key point is that no set of instructions at all can help the universal machine to distinguish in all case a code of a total function from a code of a strictly partial function. For if that was possible, then we could securise the universal machine making it computing only total functions, and then the diagonal will strike again and prove 0 = 1. Note this discovery: If A is enumerable, and if B is included in A, then B is enumerable. But if A is effectively enumerable (meaning really that the ass..., er I mean the dumb one can enumerate A), it DOES NOT follow that any subset of A is effectively enumerable. There is a bijection between the set of code (instructions, expressions) of total computable function and N, but what the second diagonalization shows, is that such a bijection is not a computable bijection. The set of code of total function is an enumerable, but not effectively enumerable subset of the set of code of the partial (strict and not strict) functions. So, as you know, Church did *define* a computable function by a function computable by a lambda expression, in its conversion calculus. Why do you introduce here the term 'lambda expression'? I'm asking this because in the sequel you work just with 'a well specified language which is promised to be universal' and you prove that such a promise is not ruled out. I do not see how you reached the conlusion: But thanks to that crashing, *Church thesis remains consistent*. I would just say An existence of a universal language is not ruled out. OK. But Church thesis says that Lambda is universal, and so a weaker form of Church thesis (the one which asserts the existence of a universal language) remains consistent. OK. Each expression like that denotes now either a computable function from N to N, or as we have to expect something else. And we have to expect they are no computable means to distinguish which U_i represents functions from N to N, and which represents the other beast. Can I say that the other beasts are only and only infinite loops? I assume that the machine cannot destroy itself, so it either stops after computing a computable function or enters
Re: Key Post 1, toward Church Thesis and Lobian machine
On Thu, Dec 06, 2007 at 03:37:10PM +0100, Bruno Marchal wrote: Thanks Russell. About the use of asshole I am afraid it is more popular, or vulgar, than I thought. You are very kind to tell me. Should I use dumb instead? The idea consists in not attributing No dumb is the wrong word. Dumb people can of course be quite creative (literally dumb means not able to speak, but derogatively it also means stupid, which is a slight on dumb people). I would have gone with something like mindless robot - although this has problems of implying artificiality. Perhaps mindless servant - you want to get across the idea of following orders to the letter without question. Doesn't trou de cul have a similar meaning to arsehole in French? I suspect the closer translation might be connard though. -- A/Prof Russell Standish Phone 0425 253119 (mobile) Mathematics UNSW SYDNEY 2052 [EMAIL PROTECTED] Australiahttp://www.hpcoders.com.au --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
On Tue, Dec 04, 2007 at 03:55:50PM +0100, Bruno Marchal wrote: Hi David, Mirek, Tom, Barry and All, ... The cardinality of the set of computable functions. Thanks for this post. I was in the position of trying to explain your work to someone (actually a son of my mother's cousin) at a dinner party a couple of weeks ago, and having explained Cantor's diagonalisation proof of the uncountability of the reals, I got to the point about computable functions being countable and got stuck. I just had to say well its true, but I can't quite recall the proof!. Your exposition is eminently dinner-party standard, although I might use a different word than asshole! Cheers -- A/Prof Russell Standish Phone 0425 253119 (mobile) Mathematics UNSW SYDNEY 2052 [EMAIL PROTECTED] Australiahttp://www.hpcoders.com.au --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
On Wed, Dec 05, 2007 at 11:08:34PM +0100, Mirek Dobsicek wrote: Each expression like that denotes now either a computable function from N to N, or as we have to expect something else. And we have to expect they are no computable means to distinguish which U_i represents functions from N to N, and which represents the other beast. Can I say that the other beasts are only and only infinite loops? I assume that the machine cannot destroy itself, so it either stops after computing a computable function or enters some silly loop. Not unless the total number of states was finite. In a Turing machine case, the tape being infinite and readable/writeable allows the machine to compute forever without entering a loop. For instance, a program outputting the digits of Pi onto the tape computes forever and never enters a loop (since Pi is irrational, periodic sequences of digits are ruled out). -- A/Prof Russell Standish Phone 0425 253119 (mobile) Mathematics UNSW SYDNEY 2052 [EMAIL PROTECTED] Australiahttp://www.hpcoders.com.au --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Key Post 1, toward Church Thesis and Lobian machine
Hi Bruno, thank you for your post. I read it a couple of times in order to more or less grasp it, but it worth it. I have some questions... Suppose there is a secure universal machine M. The set of expressions it can compute provide a secure universal language L. That set is not only enumerable (given that it is a subset of an enumerable set) but above all, it can be enumerated effectively (by the ashole). What do you mean here by effectively? I understand it as you just want to emphasize that the set is really enumerable. So, as you know, Church did *define* a computable function by a function computable by a lambda expression, in its conversion calculus. Why do you introduce here the term 'lambda expression'? I'm asking this because in the sequel you work just with 'a well specified language which is promised to be universal' and you prove that such a promise is not ruled out. I do not see how you reached the conlusion: But thanks to that crashing, *Church thesis remains consistent*. I would just say An existence of a universal language is not ruled out. Each expression like that denotes now either a computable function from N to N, or as we have to expect something else. And we have to expect they are no computable means to distinguish which U_i represents functions from N to N, and which represents the other beast. Can I say that the other beasts are only and only infinite loops? I assume that the machine cannot destroy itself, so it either stops after computing a computable function or enters some silly loop. Indeed, the diagonalisation above, where now the f_i are the *partial computable functions*, meaning they are from N to N, OR from a subset of N to N, does no more lead to a contradiction. I have a problem with this paragraph, could you please write more on this? I understand to partial computable functions as to functions which are not *defined* for every possible input (total functions are defined for all inputs, in my limited understanding). Do you say in that paragraph that beasts are only and only these partial functions? Huh, now what do I mean by *defined* ... maybe I should say 'which are not computable for every possible input'. I am really lost here... And my last question, consider the profound function f such that f(n) = 1 if there is a sequence of n consecutive fives in the decimal expansion of PI, and f(n) = 0 otherwise Is this an example of a partial computable function? Or is this function as such already considered as un-computable function? With best regards, Mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Key Post 1, toward Church Thesis and Lobian machine
Hi David, Mirek, Tom, Barry and All,
In the preceding post, I gave you an informal proof in naïve set theory
that the set of functions from N to N was not enumerable.
Note: the preceding post =
http://www.mail-archive.com/everything-list@eskimo.com/msg14063.html
It is not in my intention at all to convince you that Cantor's result
is true. A problem which occurs is the many invocation of Gods. Cantor
himself will hide paradoxes and also will discuss with theologians on
those problems.
Today we know Cantor's theorem is provable in reasonably sound accounts
of sets, like Zermelo Fraenkel Set Theory, ZF.
But it is not my purpose to dwelve into set theory. My purpose is
computability theory.
What happens if we try to restrict ourselves to *computable* functions
from N to N, instead of *all* functions from N to N.
In this case we would not be obliged to refer to Gods, those who were
able to see an arbitrary and infinite long sequence of numbers.
But we get somehow the anti-problem. How to define what is a computable
function?
We can hardly be satisfied by an anti-solution like:
Anti-definition: A function from N to N is computable if it can be
computed without any invocation to any Gods.
So we have to find a more positive definition, and invoke *finite and
humble* creature instead. Humble, because we have to be sure not
attributing to them any magical and hard to define qualities like
cleverness, intelligence, intuition or any god-like predicate.
So here is an informal definition of what is an (intuitively)
computable function from N to N.
Definition: a function f is computable if there is a finite set of
instructions such that a complete asshole can, on each n compute in a
finite time the result f(n).
OK. complete asshole is probably a bit popular, and I will use the
adverb unambiguously instead.
Also, what are the instructions? Whatever they are, they have to be
described in some language, which has to be unambiguous (understandable
by that humble finite creature).
So here is a better definition of what is a computable function from
N to N.
A function f from N to N is said (intuitively) computable if there is a
language L in which it is possible to describe unambiguously through a
finite expression in L how, for any n to compute f(n) in a finite time.
The finite expression are intended to express the instructions. A
language is the given of a finite alphabet A, and a subset L of
unambiguous expressions. If A is a finite or enumerable alphabet, then
I will denote by A°, the set of finite expressions written with the
alphabet A. I recall that If A is finite or enumerable, then A° is
enumerable too. Indeed, you can put an alphabetical order on all
sequences of length 1, and then of length 2, etc.
Exemple: A = {S, K, (, ) }
Ordering the finite expressions, using the order K S ( ) on
the alphabet:
finite expressions=
K, S, (, ), [length one]
KK, KS, K(, K), SK, SS, S(, S), (K, (S, ((, (), )K, )S, )(, )),
[length two]
KKK , ... [length 3]
, ... [length 4]
Note that )))KK))S()) is a finite expression on the alphabet. It is
does not refer to a combinator, which are associated only to
well-formed expressions, like, if you remember, (K(SK)), or
((S(KS))K), making a subset of the set of all (finite) expressions.
Now, two fundamental definitions:
Universal Language: A language L is universal if all computable
functions (from N to N) can be described in L.
Universal Machine: A machine M is universal if M understands L, and so
M can actually compute the value f(n) of any computable function from
its description in the universal language L and the input n.
(Note that such a universal *machine*, should be describable itself by
an expression in the universal language. We will come back on this
later).
Now the question is: Is there an universal language? Is there a
universal machine?
Is that an obvious question? Definitions like above are not proof of
existence.
Traditionnaly here I do sometimes present a proof, by diagonalization,
that there are no universal machine, and ask the student to find
possible errors. Here I will NOT proceed like that and proceed directly
instead.
For this I will first consider the problem of the cardinality of the
set of computable functions, and then provide more definitions.
The cardinality of the set of computable functions.
Well, if L is a language, it has a finite alphabet A. Then, the subset
of its unambiguous expressions (for the instruction) is a subset of the
set of all its finite expressions, which we have seen to be enumerable.
So the set of computable functions from N to N is enumerable. By
Cantor, the set of functions from N to N is not enumerable: thus there
are drastically more uncomputable functions than computable functions.
Definition: Perfect Universal Machine (or Language): I will say that a
universal machine (or language) is perfect, or secure, if the machine
