> On 1 Jun 2020, at 12:37, Bruce Kellett <[email protected]> wrote: > > On Mon, Jun 1, 2020 at 7:08 PM Bruno Marchal <[email protected] > <mailto:[email protected]>> wrote: > On 1 Jun 2020, at 00:23, Bruce Kellett <[email protected] > <mailto:[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 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.
It can be elsewhere, sure, the problem is that f_k(k) is necessarily also on the diagonal, like f_0(0), f_1(1), f_2(2), …, by the diagonal construction. For all n, g(n) = f_k(n), thus in particular g(k) = f_k(k) But by definition of g, g(k) = f_k(k) + 1. f_k(k) and f_k(k) + 1 are both on the intersection of the row for f_k and the diagonal. No problem if they are both undefined, but big problem if they are both defined, as as f_k are all total, ex hypothesis, they are well defined. Conclusion: either the f_k do not run through all total computable functions, and L is not universal, or we keep faith in the Church Turing thesis, we claim our L universal, but then the language get necessarily richer and describes strictly partial function, added "non algorithmically” to the f_n. We get the phi_i, or phi_n. That shows that conventionalism does not make sense, because who would make the convention of the existence of something that we cannot compute? Of course, you could define “computable” by a large subclass of the total computable functions, but you will have to make it non Turing universal if you want to secure the system. It is enough to send people to the goulag in case they would use an elementary operation not allowed, forbidden, in your language. It shows that the universal machine is born with an hesitation between security and universality/liberty. Universality -> shit happens. Löbianity -> you know that shit happens. If arithmetic is conventional, I would like to meet the guy who decided to add shit, by convention! Bruno > > 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] > <mailto:[email protected]>. > To view this discussion on the web visit > https://groups.google.com/d/msgid/everything-list/CAFxXSLQnjz9LJgtR-pb8BmOO3Ud88hQL0k14kg4LP242Yd9B8w%40mail.gmail.com > > <https://groups.google.com/d/msgid/everything-list/CAFxXSLQnjz9LJgtR-pb8BmOO3Ud88hQL0k14kg4LP242Yd9B8w%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/DB2E724C-06E1-4FD9-B647-BC5E160183A1%40ulb.ac.be.
