> On 1 Jun 2020, at 00:23, Bruce Kellett <[email protected]> wrote: > > On Mon, Jun 1, 2020 at 3:12 AM 'Brent Meeker' via Everything List > <[email protected] <mailto:[email protected]>> > wrote: > On 5/30/2020 10:44 PM, Bruce Kellett wrote: >> On Sun, May 31, 2020 at 2:26 AM Bruno Marchal <[email protected] >> <mailto:[email protected]>> wrote: >> >> Let us write f_n for the function from N to N computed by nth expression. >> >> Now, the function g defined by g(n) = f_n(n) + 1 is computable, and is >> defined on all N. So it is a computable function from N to N. It is >> computable because it each f_n is computable, “+ 1” is computable, and, vy >> our hypothesis it get all and only all computable functions from N to N. >> >> But then, g has have itself an expression in that universal language, of >> course. There there is a number k such that g = f_k. OK? >> >> But then we get that g_k, applied to k has to give f_k(k), as g = f_k, and >> f_k(k) + 1, by definition of g. >> >> >> That is a fairly elementary blunder. g_k applied to k, g_k(k) = f_n(k)+1, by >> definition of g_k. You do not get to change the function from f_n to f_k in >> the expression. It is only the argument that changes: in other words, f_n(n) >> becomes f_n(k). So you are talking nonsense. > > No, I think that's OK. It's a straight substitution n->k. The trick is that > g(n) is not some well defined specific function because n has infinite range. > So none of this works in a finite world. But it's not surprising that there > is incompleteness in an infinite theory. > > > Yes, I had misunderstood what g(n) was supposed to be -- it is simply a > representation of the diagonal elements of the array, plus 1. But Bruno's > attempt to use the diagonal argument here fails, because he has to show that > f_n(n)+1 is not contained in the infinite list. He has failed to do this.
Where? I repeat the argument. If f_n is an enumeration of *al*l computable functions from N to N, then we can define the function g by saying that on each n in N, g(n) = f_n(n) + 1. (Or if you prefer g = [n](f_n(n) + 1) if you dislike (like me) to use f(x) to describe a function. But most people fear the lambda notation ([n]), so I will use the secondary usual denotation of function, with the implicit meaning that x or n are the variable/input. But now we have a contradiction if we assume f_n mechanically (recursively, computably) enumerable. In that case g is a computable defined on all n in N, and thus has to be in the enumeration of all computable function f_n. That means that it exists a number k such g is f_k, but then: g(k) = f_k(k) (by g being a function computable from N to N) g(k) = f_k(k) + 1 (by definition of g) And thus f_k(k) = f_k(k) + 1 And f_k(k) is a number (by definition of what is a function from N to N), so we can subtract it at both sides, and we get 0 = 1. Conclusion: the set of the computable functions from N to N, which is obviously enumerable (as explained in my preceding post) is not mechanically enumerable. Any bijection or surjection associating n to f_n (with possible repletion) is a non computable function. At first sight this seems to contradict Church thesis, but it implies only that if there exist a universal language (CT), i.e. capable of defining all computable functions from N to N, then the enumeration of the expressions (among those computing notably all functions from N to N), there will be other objects, and indeed, some undefined functions on some, i.e. functions from subset of N (called the domain of f) in N. That gives the phi_n, and their domain w_n. We can define g in the universal language, and the diagonal argument, on those phi_n will go through up to phi_k(k) = phi_k(k) + 1 But this does not lead to a contradiction now, as we can derive from this that phi_k(k) is not defined, and can no more be subtracted at the left and right hand side. This entails a strong form of incompleteness, called by Tarski: Essential Incompleteness: it means that *all* effective theory (theory such that we can check mechanically if a proof is valid or not) are incomplete, and cannot be completed by adding axioms (any effective number of axioms). It means that concerning the finite machines, there will always be true, and well determined proposition, which cannot be proved in any theory about them. Indeed if a theory could effectively prove if a phi_n is from N to N or not, then we could filter out the partial functions (not defined on all n in N), and get a computable enumeration of the f_n, and in this case, the diagonal argument lead (again) to 0 = 1. Brent suggest that we might recover completeness by restricting N to a finite domain. That is correct, because all finite function are computable, but then, we have incompleteness directly with respect to the computable functions, even limited on finite but arbitrary domain. In fact, that moves makes the computer simply vanishing, and it makes Mechanism not even definable or expressible. On the contrary, what the diagonal argument shows here is that there are FINITE machines, whose behaviour is not computable, nor most of its attribute. Which one? Well, given that phi_n is mechanically enumerable, and given that we can build a computable bijection between NxN and n, we get a universal machine u, which is such that for all n, m we have phi_u(n, m) = phi_n(m). u is called universal digital machine/number, or computer/intepreter. The computer has been discovered in this way, before its implementation (excepting Babbage machine, never completely implemented though). Definition: I call “universal enumeration” or “universal machinery” the enumeration of the phi_n, (or of the corresponding expressions). I call “universal machine” the number u as defined above. It shows that one finite machine (u) can, given the expression (encoded by its number in the enumeration of expression) computing it on any argument m, on which phi_n is defined. Note that when we have a computable enumeration phi_n, i.e. a universal machinery, we will have all universal machine defined in it. Inversely, give a universal machine u, we get a universal machinery canonically associated with it: phi_u(0, n), phi_u(1, n), phi_u(2, n), phi_u(3, n), phi_u(4, n), phi_u(5, n), phi_u(6, n), … So, universal machinery and universal machine are always canonically associated together. It is but the difference between universal language (something infinite) and the universal machine (which is a finite entity, understanding that language). It is the difference between saying, say, that the notion of Turing machine formalism is Turing universal, and saying this precise universal machine is a computer (universal machine, or universal number). Does this prove Gödel’s original incompleteness theorem? Almost. Gödel’s original incompleteness was about an ultra powerful theory (Principia Mathematica), and all you have to show is to show that his powerful theory can enumerate mechanically some universal machinery. Now, Gödel did much more, as it showed that elementary arithmetic can already enumerate the phi_i and compute the phi_u, and is thus Turing universal. This is much longer and tedious to show, and contains some difficulties, although it becomes simple (but still tedious), if you add the exponential axioms: Exp(n, 0) = 1 Exp(n s(m)) = n * Exp(n, m) What is not entirely obvious here is to proves those axioms in PA (which has only the axioms of addition and multiplication). In that case you can no more represent a list by using the factorisation theorem, and you need to use a bit more of elementary number theory. Gödel famously used the Chinese Lemma. What is terribly more difficult is to shows that Exp can be defined by a diophantine polynomial. This has taken 50 years, starting with Davis and Putnam, quite well developed by Julia Robinson, and transformed by Matiyasevic. This shows that not only arithmetic is Turing universal, but that the diophantine polynômes already are enough. Now, the human are obviously Turing universal. The mechanist hypothesis (well just CT) asserts that we are not *more* than universal machine, with respect to our computability hypothesis. It is easy to show that such a universal machine cannot distinguish between being emulated by this or that universal machine/number. That is why we have to extract physics from a statistic on all computations, as we cannot “localise” ourself in any universal dovetailing, which is emulated in all model of any theory in which we can define the phi_n, like arithmetic as Gödel showed already in his 1931 paper. I explain this with all details in my papers and books. Conclusion: to save physicalism, you need a non mechanist theory of mind. With mechanism, you have “only” to derive the laws of physics (the mathematic of the observable, []p & <>t, p sigma_1 + oracle) from a measure on all (relative) computations. (The need of the oracles is due to step 2: the first person is invariant for the number of step done by the Universal Dovetailer to access their state: then with ZFC + DP, the measure has been proved to exist, and I have already shown that if the measure exists, it obeys quantum logic, with a semantic made in terms of alternate consistent histories: this generalise feynmann integral, and normally should get it exactly, but we still have no precise hamiltonian or Lagrangian, or “action”). Bruno > > Bruce > > -- > 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 [email protected] > <mailto:[email protected]>. > To view this discussion on the web visit > https://groups.google.com/d/msgid/everything-list/CAFxXSLTM9g5G3neSA-bn9Td2PqpVW_g%2BBg3hwV%3DbpiToRwYKxw%40mail.gmail.com > > <https://groups.google.com/d/msgid/everything-list/CAFxXSLTM9g5G3neSA-bn9Td2PqpVW_g%2BBg3hwV%3DbpiToRwYKxw%40mail.gmail.com?utm_medium=email&utm_source=footer>. -- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/790886C7-6F32-47C2-9887-EFC60B782733%40ulb.ac.be.
