> On 27 Aug 2018, at 20:02, agrayson2...@gmail.com wrote: > > > > On Saturday, August 25, 2018 at 9:11:47 AM UTC-6, John Clark wrote: > On Sat, Aug 25, 2018 at 2:21 AM <agrays...@gmail.com <javascript:>> wrote: > > >I plan to study Cantor's theorem on the Internet and compare it with your > >proof. > > Every time Bruno useless a personal pronoun in the "proof" that involves > people duplicating machines ask yourself what exactly is the referent. If you > can figure it out let me know because I can't and neither can Bruno. > > John K Clark > > Thanks. I'll keep that in mind when I study Cantor's theorem, by Cantor and > Bruno. I've always been fascinated with the levels of infinity discovered by > great mathematicians, whom I hold in the highest esteem. AG
OK Grayson. So why is Church’s thesis a miracle? Are you OK with this what follows? If a set is enumerable (which means that there is some bijection between that set and N) then any of its subset is finite or enumerable. OK? That follows from the fact that a subset cannot have more elements than the set it is a subset from. That is intuitively obvious, but unfortunately our intuition of infinie sets has often been shown inconsistent, so today some definition of sets are provided, and in that setting the fact alluded above becomes a consequence of a well known theorem in set theory (Cantor-Bernstein-Schrceder theorem). I don’t want to delve into set theories. Later I can explain why I prefer to put set theory, analysis, and physics in the psychological tool of the universal machine. So, why Church’s thesis is a miracle? Read what follow at ease. Study it. Ask *any* question. A function is computable if we can explain to a dumb (but docile) human being how to compute it, on any of its argument. This assumes some universal language in which we can describe how to compute the functions. A weakening of Church’s thesis is that such a universal language exist. Church thesis itself was “lambda calculus” is a universal language, (and thus in which we can define and compute all computable functions from N to N.) This means that each computable function will have some code, or program, our description of how to compute them, and this entails that the set of computable functions from N to N is enumerable. This means that there is a bijection between them and N. This means there is a sequence, denoted by f_i, of all computable functions from N to N, f_0, f_1, f_2, f_3, … Now consider the function g defined by g(n) = f_n(n) + 1. (f_n(n) means f_n applied to n) That function cannot be computable! If it is, it would be in the list, and there would be a number k such that g = f_k. But then g(k) = f_k(k) = f_k(k) + 1, and again, as all f_k are function from N to N, f_k(k) is a number that we can subtract on both sides, so we get 0 = 1. Contradiction. That function g cannot be computable. Now, g(n) is f_n(n) + 1. Each f_n is computable (by definition!) and so each f_n(n) can be computed, and adding one is certainly computable, so, the only thing which can be NOT computable is the bijection itself. This means that the f_i, although enumerable, are not recursively enumerable. If a universal language exist, then it cannot compute the enumeration of all computable function from N to N. But is there a universal language? When Church said that lambda calculus can compute all computable functions, Kleene thought he would quickly refute that pretension to universality for computability, by a simple diagonalisation. That failed, and invented the expression “Church’s thesis”, and an ardent enthusiast of it. He saw also that it entails incompleteness. The only possibility which remains consistent with the diagonalisation above is that the language will describe more objects than the computable functions from N to N. Take any universal programming language. They are truly universal with respect to computability if we assume Church’s thesis. But here we *can* enumerate the functions from N to N in that language, except for a little problem which will be soon clear. We get an enumeration of such functions, by enumerating the programs lexicographically. In that case we get an algorithmic sequence of the one we denoted phi_i (in the standard literature). What happens with g defined by phi_n(n) + 1 ? Now, it is thoroughly programmable, because the phi_i can be algorithmically generated by the lexicographical algorithm: we do have the language! As I said, as we dispose of the language we can enumerate them mechanically, computably. So, in this case, g does belong to the phi_i, and thus there is a number k such that g = phi_k. And what happens if we apply g on k, i.e. phi_k on k? Well, we get that phi_k(k) = phi_k(k) + 1, but we are saved from the contradiction, because phi_k(k) will never stop. phi_k(k) is no more a number, and we can’t subtract that on both sides of the equation. What happened is that we crash the computer. And what really happens is worst than that. The language might be universal, but then the functions from N to N are distributed in a non computable manner among a more general notion of function, which are functions with subset of N as domain, and are not defined elsewhere, meaning that the computer will never stop in many case. That is essentially what we first proved: the computable functions from N to N is not recursively enumerable, so not only a universal machine can crash, but there is no effective theories capable of predicting this in advance for arbitrary arguments. Universality confronts the machine to the Unknown. Now, what Turing discovered is that when you have a universal language, and thus a universal machinery phi_i, it exist a number u such that phi_u(<i,j)> = phi_i(j), where <I,j> is some coding of the couple of numbers i j like 2^i* 3^j. That u is the universal program or machine. It means that a universal language can described itself, like it can describe and compute any other universal language, and any universal machine can imitate exactly (emulate) any other universal machines. There are compiling and interpreting theorems in between them. Now, what can seem extraordinary, but is known since long, is that very elementary arithmetic is Turing universal, and if you are OK with the idea that 2+2=4 is true independently of you, all computations exist, and stop or not, with some growing in complexity, in arithmetic, independently of you, and its leads to a problem similar to the measurement problem in physics. No universal machine can be sure which machine she is, and they know that their soul has many relative representations. You can see the set of total computable functions (those from N to N) as the “Controllable” or “Security”. The price to get all of it consists in allowing the non controllable, which is Liberty, I mean Universality. All universal machine discover this by self-referential thinking/reasoning. Note this answered your question, Grayson. Either a code describe a function from N to N, or a strictly partial function. But there is no algorithm capable of telling so, and all theories will only scratch the who is who identify of functions and programs. The semantic of programs is an appetiser for the more complex mind-body problem. Read this post until you are sure you see well what happens. It is a short reasoning which shows that universality has a big price as it makes truth (even the arithmetical truth) transcendental, unknown and full or surprises. We can only scratch the surface. Then the Löbian machine are those universal machine which knows that they are universal, and so get acquainted with the consequences (the infinite, the non provable, the non observable, …). Here there is a second miracle, which is that the propositional part of the theology is decidable! It is sum up by a modal logic G*, which decomposes itself in many different modes, due to incompleteness. More than 4 good books have been written around those logic, arithmetical self-reference is an “old” branch of mathematical logic. It might help to avoid usual traps in that domain. It is also testable as the observable is described by one of those modes, so we can compare with the empirical reality, and it fits up to now. I will illustre many of this with the combinators. In fact I will show that each universal machinery phi_i transforms the set of natural numbers into a combinatory algebra. The basic idea is very simple: define (i j) by phi_i(j). Then the SMN theorem can be used to recover the needed curryfication. This also shows a relation which run deep between the combinators and programming language. To sum up: Church thesis is a miracle because it can be consistent only if some (quickly many) definable relations get absolutely uncomputable, like the enumeration of the computable functions from N to N. Being a computable function from N to N, is not a computable predicate! Bruno > > -- > You received this message because you are subscribed to the Google Groups > "Everything List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to everything-list+unsubscr...@googlegroups.com > <mailto:everything-list+unsubscr...@googlegroups.com>. > To post to this group, send email to everything-list@googlegroups.com > <mailto:everything-list@googlegroups.com>. > Visit this group at https://groups.google.com/group/everything-list > <https://groups.google.com/group/everything-list>. > For more options, visit https://groups.google.com/d/optout > <https://groups.google.com/d/optout>. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
