[Fis] Limits of Formal Systems

Wed Feb 14 08:26:42 CET 2024

This is a smart analogy, Lou.
Thank you for (reminding us) this.
What remains to us is to train our will.
As the Romans said once: per aspera ad astra ...

Best,

Plamen

On Mon, Feb 12, 2024 at 8:16 PM Louis Kauffman <loukau at gmail.com> wrote:

> Dear Folks,
> Please examine the Kleene argument that you cannot list all algorithms
> (that halt) because you can form
> F(n) = F_{n}(n) + 1.
> This is exactly Cantor diagonal transposed to algorithms.
> It is the core of incompleteness.
> It is what it is.
> You cannot sweep it under the rug.
>
> This argument fits into many different formal systems and once you place
> it there,
> then the fact that all algorithms in a given formal system (not
> necessarily halting) can be listed (it is routine to check if some text is
> an algorithm, not routine to see if it halts),
> shows that there can be no way in the formal system to decide whether
> algorithms halt. If you could do that, you could list all the halting
> algorithms and run into
> a contradiction from the above.
>
> Thus (Turing)  the halting problem is undecideable in a wide class of
> formal systems.
>
> This part of the limitations of formal systems is just what it is.
>
> There is something else however and I would like to illustrate it with the
> Goldbach problem.
> Try writing even numbers > 4 as a sum of two odd primes.
>
> 6 = 3 + 2
> 8 = 5 + 3
> 10 = 7 + 3 = 5 + 5
> 12 = 7 + 5
> 14 = 11 + 3 = 7 + 7
> 16 = 13 + 3 = 11 + 5
> 18 = 13 + 5 = 11 + 7
> 20 = 17 + 3 = 13 + 7
> 22 = 19 + 3 = 17 + 5 = 11 + 11
> 24 = 19 + 5 = 17 + 7 = 13 + 11
> 26 = 23 + 3 = 19 + 5 = 13 + 13
> 28 = 23 + 5 = 17 + 11
> 30 = 23 + 7 = 19 + 11 = 17 + 13
> 32 = 29 + 3 = 19 + 13
> …
> These decomposition go up and down but the number of decompositions grows
> as the even numbers get larger.
> There is some principle here that we are missing about how numbers get
> constructed.
> The problem to prove that there is at least ONE way to write any even
> number greater than 4 as a sum of two odd primes is completely open.
> That is the Goldbach Conjecture.
> It bet that 12 is the last time you get only one decomposition for an even
> number into two odd primes.
>
> It is possible that by thinking about how numbers are made
> we will find new principles by which to reason about them and hence new
> formal systems, unknown at this time.
> Any number theorist worth his or her salt is going to think about this.
> This means that the number theorist is thinking outside of the
> known formal systems, trying to find new and better ways to work. This is
> normal. We need to promote the fact that creative thinking may use formal
> systems, but is
> not limited to using only systems that already exist.
> Best,
> Lou
>
>
> On Feb 9, 2024, at 9:44 AM, eric werner <eric.werner at oarf.org> wrote:
>
> Dear Carlos,
>
> Notice you contradicted yourself:
> On 2/5/2024 4:43 PM, Carlos Gershenson wrote:
>
> It is clear that models/descriptions will never be as rich as the
> modeled/phenomena, and that is the way it should be. As Arbib wrote, “a
> model that simply duplicates the brain is no more illuminating than the
> brain itself”. [1]
>
> On the one hand, you state that a model/description will never be as rich
> as the model/phenomena it describes. And, then in the next sentence you
> quote Arbib who presupposes that there could be a model that duplicates the
> brain.  Duplicating the brain presupposes that that model is as rich in
> structure and information as the thing it models, namely the brain.
>
> Of course, Arbib is wrong. If we did have model that duplicates the brain,
> then given the model is something like an LLM residing on my laptop, that
> model would not only be as rich but richer in many ways than the brain it
> modeled.  It would give us unprecedented insight into the organization and
> function of its architecture.
>
> My point is that models are often richer than the object that is modeled.
> They often have further dimensions that go beyond the object modeled. This
> extra-dimensionality and richness enable us to understand that object and
> utilize it.
>
> To be fair, you do state that computers can go beyond axiomatic systems,
> implying perhaps that they can model phenomena that axiomatic systems
> cannot.  But I am skeptical of what appears to be your wish to throw all
> axiomatic systems together and then get meaning out of such a hodgepodge.
>
> I must admit I long for the beauty of mathematics and logic, the
> crystalline world of truth, even if Goedel and other's seem to have made a
> mess of it.
>
> And yet if you actually read Goedel's proof, reading as I did while a
> student of Kleene (who was a student of Goedel's at Princeton) and later
> teaching it as I did to undergrads, that proof is itself a thing of beauty
> even if a bit messy.
>
> But Goedel did steal the core idea from Cantor's diagonal method. And,
> someday we may find that Cantor's method is flawed, in yet another higher
> dimensional mathematical space.  Which will bring us back to the Greeks!
>
> Thank you for your contribution, Carlos, and remember this is all in good
> fun,
>
> -Eric
>
> ****
> Dr. Eric Werner, FLS
>
>
>
> On 2/5/2024 4:43 PM, Carlos Gershenson wrote:
>
> In the 1920s, David Hilbert's program attempted to get rid once and for
> all from the paradoxes in mathematics that had arisen from the work of
> Cantor, Russell, and others. Even when Hilbert’s PhD student — John von
> Neumann — was working avidly on demonstrating that mathematics were
> complete, consistent, and decidable, Kurt Gödel proved in the early 1930s
> that formal systems are incomplete and inconsistent, while Alan Turing
> proved in 1936 their undecidability (for which he proposed the "Turing
> Machine", laying the theoretical basis for computer science).
>
> Digital computers have enabled us to study concepts and phenomena for
> which we did not have the proper tools beforehand, as they process much
> more information than the one our limited brains can manipulate. These
> include intelligence, life, and complexity.
>
> Even when computers have served us greatly as "telescopes for complexity",
> the limits of formal systems are becoming even more evident, as we attempt
> to model and simulate complex phenomena in all their richness, which
> implies emergence, self-organization, downward causality, adaptation,
> multiple scales, semantics, and more.
>
> Can we go beyond the limits of formal systems? Well, we actually do it
> somehow. It is natural to adapt to changing circumstances, so we can say
> that our "axioms" are flexible. Moreover, we are able to simulate this
> process in computers. Similar to an interpreter or a compiler, we can
> define a formal system where some aspects of it can be modified/adapted.
> And if we need more adaptation, we can generalize the system so that a
> constant becomes a variable (similar to oracles in Turing Machines).
> Certainly, this has its limits, but our adaptation is also limited: we
> cannot change our physics or our chemistry, although we have changed our
> biology with culture and technology.
>
> Could it be that the problem lies not in the models we have, but in the
> modeling itself? We tend to forget the difference between our models and
> the modeled, between the map and the territory, between epistemology and
> ontology; simply because our language does not make a distinction between
> phenomena and our perceptions of them. When we say "this system is
> complex/alive/intelligent", we assume that these are inherent properties of
> the phenomenon we describe, forgetting that the moment we name anything, we
> are already simplifying and limiting it. It is clear that
> models/descriptions will never be as rich as the modeled/phenomena, and
> that is the way it should be. As Arbib wrote, “a model that simply
> duplicates the brain is no more illuminating than the brain itself”. [1]
>
> Still, perhaps we're barking up the wrong tree. We also tend to forget the
> difference between computability in theory (Church-Turing's) and
> computability in practice (what digital computers do). There are
> non-Turing-computable functions which we can compute in practice, while
> there are Turing-computable functions for which there is not enough time in
> the universe to compute. So maybe we are focussing on theoretical limits,
> while we should be concerned more with practical limits.
>
> As you can see, I have many more questions than answers, so I would be
> very interested in what everyone thinks about these topics.
>
> I'll just share some idea I've been playing with recently, although it
> might be that it won't lead anywhere. For lack of a better name, let's call
> them "multi-axiom systems". For example in geometry, we know that if we
> change the 5th axiom (about intersecting parallel lines), we can go from
> Euclidean to other geometries. We can define a "multi-axiom geometry", so
> that we can switch between different versions of the 5th axiom for
> different purposes. In a similar way, we could define a multi-axiom system
> that contains several different formal systems. We know we cannot have all
> at once universal computation and completeness and consistency. But then,
> in first-order logic, we can have completeness and consistency. In
> second-order logic we have universal computation but not completeness. In
> paraconsistent logics we sacrifice consistency but gain other properties.
> Then, if we consider a multi-axiom system that includes all of these and
> perhaps more, in theory we could have in the same system all these nice
> properties, but not at the same time. Would that be useful? Of course, we
> would need to find rules that would determine when to change the axioms.
> Just to relate this idea to last month's topic — as it was motivated by
> Stu's and Andrea's paper [2] — if we want to model evolution, we can have
> "normal" axioms at short timescales (and thus predictability), but at
> longer (evolutionary) timescales, we can shift axioms set, and then the
> "rules" of biological systems could change, towards a new configuration
> where we can use again "normal" axioms.
>
>
>
> [1] Michael Arbib, The Metaphorical Brain 2. Neural Networks and Beyond
> (1989)
> [2] Stuart Kauffman, Andrea Roli. Is the Emergence of Life an Expected
> Phase Transition in the Evolving Universe?
> https://urldefense.com/v3/__https://arxiv.org/abs/2401.09514v1__;!!D9dNQwwGXtA!W_8_89WZh2VhyUljTzLdER-EnhYlnAP1W7p-DTctMfXu-oNrWSIVYiZ8Ffc8BTNMI7g2k0aV3UvgmZE_jQUBIifkUr83$ 
> <https://urldefense.com/v3/__https://arxiv.org/abs/2401.09514v1__;!!D9dNQwwGXtA!Q9Wf2QzNb33Rbcm_rxf9I_P4EziZ3qwzNM9drNcS2M856SZcvJx6al-U8ZnYt5Fj0OfDWnNsNDd2RoZgOmc$>
>
>
> Carlos Gershenson
> SUNY Empire Innovation Professor
> Department of Systems Science and Industrial Engineering
> Thomas J. Watson College of Engineering and Applied Science
> State University of New York at Binghamton
> Binghamton, New York 13902 USA
> https://urldefense.com/v3/__https://tendrel.binghamton.edu__;!!D9dNQwwGXtA!W_8_89WZh2VhyUljTzLdER-EnhYlnAP1W7p-DTctMfXu-oNrWSIVYiZ8Ffc8BTNMI7g2k0aV3UvgmZE_jQUBIsNA-fmS$ 
> <https://urldefense.com/v3/__https://tendrel.binghamton.edu__;!!D9dNQwwGXtA!Q9Wf2QzNb33Rbcm_rxf9I_P4EziZ3qwzNM9drNcS2M856SZcvJx6al-U8ZnYt5Fj0OfDWnNsNDd2yTKmSVg$>
>
>
> _______________________________________________
> Fis mailing listFis at listas.unizar.eshttp://listas.unizar.es/cgi-bin/mailman/listinfo/fis
> ----------
> INFORMACIÓN SOBRE PROTECCIÓN DE DATOS DE CARÁCTER PERSONAL
>
> Ud. recibe este correo por pertenecer a una lista de correo gestionada por la Universidad de Zaragoza.
> Puede encontrar toda la información sobre como tratamos sus datos en el siguiente enlace: https://sicuz.unizar.es/informacion-sobre-proteccion-de-datos-de-caracter-personal-en-listas
> Recuerde que si está suscrito a una lista voluntaria Ud. puede darse de baja desde la propia aplicación en el momento en que lo desee.http://listas.unizar.es
> ----------
>
>
>
> <https://urldefense.com/v3/__http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient__;!!D9dNQwwGXtA!S9usrOp9JhvW8UwJEq9dcFtq7FKcSNqNVPec2sX1BgZjKXwC0mnBUV_SDjdu1Sa_AS3w3prDwKITzaqB41fYZVU$>
> Virus-free.https://urldefense.com/v3/__http://www.avg.com__;!!D9dNQwwGXtA!W_8_89WZh2VhyUljTzLdER-EnhYlnAP1W7p-DTctMfXu-oNrWSIVYiZ8Ffc8BTNMI7g2k0aV3UvgmZE_jQUBIjsn4cYI$ 
> <https://urldefense.com/v3/__http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient__;!!D9dNQwwGXtA!S9usrOp9JhvW8UwJEq9dcFtq7FKcSNqNVPec2sX1BgZjKXwC0mnBUV_SDjdu1Sa_AS3w3prDwKITzaqB41fYZVU$>
> _______________________________________________
> Fis mailing list
> Fis at listas.unizar.es
> http://listas.unizar.es/cgi-bin/mailman/listinfo/fis
> ----------
> INFORMACI�N SOBRE PROTECCI�N DE DATOS DE CAR�CTER PERSONAL
>
> Ud. recibe este correo por pertenecer a una lista de correo gestionada por
> la Universidad de Zaragoza.
> Puede encontrar toda la informaci�n sobre como tratamos sus datos en el
> siguiente enlace:
> https://sicuz.unizar.es/informacion-sobre-proteccion-de-datos-de-caracter-personal-en-listas
> Recuerde que si est� suscrito a una lista voluntaria Ud. puede darse de
> baja desde la propia aplicaci�n en el momento en que lo desee.
> http://listas.unizar.es
> ----------
>
>
> _______________________________________________
> Fis mailing list
> Fis at listas.unizar.es
> http://listas.unizar.es/cgi-bin/mailman/listinfo/fis
> ----------
> INFORMACIÓN SOBRE PROTECCIÓN DE DATOS DE CARÁCTER PERSONAL
>
> Ud. recibe este correo por pertenecer a una lista de correo gestionada por
> la Universidad de Zaragoza.
> Puede encontrar toda la información sobre como tratamos sus datos en el
> siguiente enlace:
> https://sicuz.unizar.es/informacion-sobre-proteccion-de-datos-de-caracter-personal-en-listas
> Recuerde que si está suscrito a una lista voluntaria Ud. puede darse de
> baja desde la propia aplicación en el momento en que lo desee.
> http://listas.unizar.es
> ----------
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listas.unizar.es/pipermail/fis/attachments/20240214/25fd7b18/attachment-0001.html>