On Mon, Jun 1, 2020 at 7:08 PM Bruno Marchal <[email protected]> wrote:
> 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]> wrote: > >> On 5/30/2020 10:44 PM, Bruce Kellett wrote: >> >> On Sun, May 31, 2020 at 2:26 AM Bruno Marchal <[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 can't show where you are not doing something! 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) > But there is no need for this computable number to lie on the diagonal. It could well be f_k(x), for x!=k. Bruce > 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 > -- 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/CAFxXSLQnjz9LJgtR-pb8BmOO3Ud88hQL0k14kg4LP242Yd9B8w%40mail.gmail.com.
