[Fis] Limits of Formal Systems

[Louis Kauffman]

Dear Carlos,
You ignore the mathematical level when you attempt a distinction between theory and practice.
The mathematical level is practical.
You know why a^2 + b^2 = c^2 for any right triangle. You do not have to measure each one.
You know that Newton’s Laws apply to good approximation to any orbiting object and you can make use of them.
The notion that you can just look at things in a finite world is erroneous.
There are real mathematical problems associated with whether algorithms halt or whether theorems are true or false.
There is real interest in these problems.
Of course it is a matter of taste.
It is possible that you are a person who never got interested in any real mathematical questions.
If so,then at least its my duty to show you the sort of thing I mean.

Euclid proved that there are infinitely many prmes. His proof is summarized  by 
N_{k} = p_{1} x p_{2} x … x p_{k} + 1.
If p_{1},  p_{2},  … ,  p_{k} are the first k prime numbers, then N_{k} is either a prime number or it is divisible by new primes different from
 p_{1},  p_{2},  … ,  p_{k}. Ok. Now consider the sequence N_{1},N_{2}, N_{3}, … Are there infinitely many prime numbers in this sequence?
No one knows, and if you just use a computer it will not tell you the answer. 

Goldbach Conjecture: Every even number greater than 4 appears to be the sum of two odd primes, usually in many ways.
This is something that you can explore with a computer. For example



No one has managed to prove this result. This is a case where I am pretty much convinced by my computer that the Goldbach Conjecture is true.
It is then a great theoretical challenge to find a proof of that conjecture. Would a proof have practical consequences? I do not know, but I bet there would be
practical spinoffs, just as soon there will be very serious practical spinoffs to the Shor quantum factoring algorithm and its theoretical basis.
 
Collate Problem: Let C(n) = 1 if the following algorithm on n halts at 1. Let C(n) = 0 if it does not halt.
n —> n/2 if n even.
n —> 3n + 1 i n odd
Repeat until 1 is reached.
If 1 is reached, STOP.
If 1 is not reached keep computing.
e.g. 7 —> 22 —> 11—> 34 —> 17 —> 52 —> 26 —> 13 —> 40 —> 20 —> 10 —> 5 —> 16 —> 8 —> 4 —> 2 —> 1 , STOP.
No one knows if this algorithm halts, but it has been seen to halt for every n that has ever been tried.
In this case finite computer exploration seems to be one way to get possible insight into the problem.

Famous Example. A 2n x 2n checkerboard has opposite corner squares removed. Can it be paved with dominos with no overhangs?
Answer: No!
Discussion. For small n you can do a computer search and find the answer, but try that for even n= 10^{100} and you will be in trouble.
On the other hand, one can make the intelligent mathematical observation that the two opposite corner squares have the same color, and so there are a different number of 
black and white squares on the deleted checkerboard. Since each domino covers one white square and one black square, this means that the deleted checkerboard cannot be covered by dominos with no overhangs.

At mathematical level we are searching for structural observations that will encompass an infinity of cases. 
This is practical, because it creates an economy of thought and action.
Best,
Lou
P.S. I sent a paper but it bounced. If anyone would like to read a paper that elaborates on the above lletter, send me an email to 
loukau at gmail.com <mailto:loukau at gmail.com>
and I will send it directly to you.



> On Feb 16, 2024, at 4:16 PM, Carlos Gershenson <cgershen at gmail.com <mailto:cgershen at gmail.com>> wrote:
> 
> Dear Lou,
> 
> Thank you for your examples. 
> 
> The Kleene argument precisely shows the relevance of the difference between theory and practice. In theory, there will always be undecidability in “powerful enough” formal systems. In practice, we can arbitrarily try out all algorithms that we want for a finite time, and come up with a table of whether they halted or not. 
> 
> Now, the question would be whether with such a pragmatic approach we can overcome the limits of formal systems that prevent us from representing properly e.g. evolutionary innovations, and changes in function in general. 
> 
> But maybe we just need two levels: one where rules don’t change, and another where we can allow rules and meaning to change. The thing is that the way in which rules and meaning change cannot change… but then if we add another layer… To avoid turtles all the way down, could we have layer A changing layer B and vice versa? A coevolution of formal systems?
> 
> Best wishes,
> Carlos
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listas.unizar.es/pipermail/fis/attachments/20240219/8f6b80fa/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screen Shot 2024-02-17 at 1.57.16 AM.png
Type: image/png
Size: 23142 bytes
Desc: not available
URL: <http://listas.unizar.es/pipermail/fis/attachments/20240219/8f6b80fa/attachment-0001.png>