[Fis] Limits of Formal Systems

Mon Feb 12 20:16:09 CET 2024

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 <mailto: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!WdqhpnzOlsHXIDjVEP8bcYLnvMenRNag22AyItgviwJ12dV3qBU3eR6d_sg1-MW9A02b7K8_b_h1WZm5$   <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!WdqhpnzOlsHXIDjVEP8bcYLnvMenRNag22AyItgviwJ12dV3qBU3eR6d_sg1-MW9A02b7K8_b1kzb2x3$  <https://urldefense.com/v3/__https://tendrel.binghamton.edu__;!!D9dNQwwGXtA!Q9Wf2QzNb33Rbcm_rxf9I_P4EziZ3qwzNM9drNcS2M856SZcvJx6al-U8ZnYt5Fj0OfDWnNsNDd2yTKmSVg$>
>> 
>> 
>> _______________________________________________
>> Fis mailing list
>> Fis at listas.unizar.es <mailto:Fis at listas.unizar.es>
>> http://listas.unizar.es/cgi-bin/mailman/listinfo/fis <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 <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 <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!WdqhpnzOlsHXIDjVEP8bcYLnvMenRNag22AyItgviwJ12dV3qBU3eR6d_sg1-MW9A02b7K8_b_QQ45Pj$  <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$> <x-msg://124/#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>_______________________________________________
> Fis mailing list
> Fis at listas.unizar.es <mailto: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/20240212/de53a74d/attachment-0001.html>