Collatz: Różnice pomiędzy wersjami
| Linia 3: | Linia 3: | ||
Work on the problem took 83 years.<br /> | Work on the problem took 83 years.<br /> | ||
We succeeded. We are changing the status of the "Collatz conjecture" to [http://lem12.uksw.edu.pl/images/3/37/CollatzConjecturebecomesTheorem20Nov23.pdf]<br /> | We succeeded. We are changing the status of the "Collatz conjecture" to [http://lem12.uksw.edu.pl/images/3/37/CollatzConjecturebecomesTheorem20Nov23.pdf]<br /> | ||
| − | |||
| − | + | ||
| − | + | June 5, 2022 version [https://dx.doi.org/10.2139/ssrn.4158238 '''Collatz theorem'''] submitted to TCS Journal.<br /> | |
| − | == | + | A shortened and less formal version of the proof can be found here [http://lem12.uksw.edu.pl/images/9/9f/MainPointsProofCollatz.pdf].<br /> |
| − | + | ==Introduction== | |
| − | + | Let's consider the statement<br/> | |
| − | <math>\color{blue}\qquad Cl:\,\left\{\begin{array}{l} | + | for every natural number <math>n</math>, the following program <math>Cl</math> has a finite computation.<br/> |
| − | \quad \mathbf{if}\ | + | <math>\color{blue}\qquad Cl:\,\left\{\begin{array}{l} \mathbf{while}\ n \neq 0 \ \mathbf{do} \\ |
| + | \quad \mathbf{if}\ odd(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{fi} \\ | ||
\mathbf{od} \end{array}\right\} </math> <br /> | \mathbf{od} \end{array}\right\} </math> <br /> | ||
| − | + | We begin by noting that the truth of the above statement entails the truth of Collatz's thesis as it was formulated before World War II. <br /> | |
| − | + | But in 1937, neither computers nor programming languages existed.<br /> | |
| − | . | + | On the other hand, the theory of algorithms did exist and was already well developed. The theory of recursive functions was developed in Göttingen (David Hilbert and his students), Budapest (Rozsza Pterer, Laszlo Kalmar), ...<br /> |
| − | + | In London, Alan Turing created the abstract Turing machine.<br /> | |
| − | + | In Moscow, Kolmogorov and in Kazan, Maltsev explored the concept of a computable function.<br /> | |
<br /> | <br /> | ||
| − | + | In Warsaw, Alfred Tarski, together with his students Mojżesz Presburger and Stanisław Jaskowski, obtained important results concerning the theory of addition of natural numbers. | |
| − | == | + | ==Our observations from 2004== |
| − | * | + | * The Collatz algorithm <math>Cl</math> does not require multiplication or division operations. Multiplying by 3 (because 3x=x+x+x) and dividing by 2 (a simple algorithm adding every other 1 is sufficient), is sufficient. |
| − | * | + | * In the algebraic structure <math>\mathfrak{M}</math>, which is a non-standard model of the elementary theory of addition of natural numbers (there is one, see below), the algorithm <math>Cl</math> has an infinite computation for many arguments. |
| − | * | + | * Therefore, the Collatz theorem cannot be proven based on the axioms of the elementary theory of addition of natural numbers. |
| − | * | + | * Moreover, in the language of elementary theory of addition, there is no stopping formula for the Collatz algorithm! So what do we have to prove? |
| − | == | + | ==Correct formulation of the Collatz theorem== |
| − | + | In the standard structure of natural numbers with the addition operation, | |
| − | + | our program <math>Cl</math> has a finite computation for each argument ''n''. | |
| − | == | + | ==Stop formula== |
| − | + | i.e. | |
| − | === | + | === A necessary and sufficient condition for the computation to be finite=== |
| − | + | Therefore, we need to create a formula <math>\theta</math> (a logical expression) such that it evaluates to true if and only if the computation of the program <math>Cl</math> is finite. There are many such formulas in the language of program calculation, i.e. algorithmic logic.<br/> | |
| − | ,<math>\qquad \theta:\,\left\{\begin{array}{l} | + | ,<math>\qquad \theta:\,\left\{\begin{array}{l} \mathbf{while}\ n \neq 0 \ \mathbf{do} \\ |
| − | \quad \mathbf{if}\ | + | \quad \mathbf{if}\ odd(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{fi} \\ |
\mathbf{od} \end{array}\right\} (n=1) </math> | \mathbf{od} \end{array}\right\} (n=1) </math> | ||
<br /> | <br /> | ||
| − | + | The value of the <math>\theta</math> formula depends only on the initial value of the "n" variable. This formula is satisfied by the value of the variable "n" if and only if the evaluation of the while ... program is finished and the final value of the variable "n" is equal to 1. <br /> | |
| − | + | Other formulas can also be considered, e.g., <br /> | |
| − | ,<math>\qquad \xi:\,\bigcup \left\{\overbrace{\begin{array}{l} | + | ,<math>\qquad \xi:\,\bigcup \left\{\overbrace{\begin{array}{l} \mathbf{if}\ n \neq 0 \ \mathbf{then} \\ |
| − | \quad \mathbf{if}\ | + | \quad \mathbf{if}\ odd(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{fi} \\ |
| − | \mathbf{fi} \end{array} }^{K}\right\} (n=1) </math> | + | \mathbf{fi} \end{array} }^{K}\right\} (n=1) </math> <br /> |
| − | {co | + | {co reads: "there exists an iteration <math>K^i</math> of the program <math>K</math> such that after executing <math>K^i</math> the equality <math>n=1</math> is satisfied."} <br/> |
| − | + | In other words, we are dealing with an upper bound on the values of the formulas <math>K^i(n=1)</math>, where <math>i= 0,1,2 \dots</math>.<br /> | |
| − | + | The second part of the problem is much more difficult: we must prove the stopping formula using the axioms of program calculus and the axioms of the algorithmic theory of natural numbers.<br/> | |
<br /> | <br /> | ||
| − | |||
==Elementarna teoria dodawania liczb naturalnych== | ==Elementarna teoria dodawania liczb naturalnych== | ||
Poprzednia obserwacja stwierdzająca, że w tej teorii nie można przeprowadzić dowodu tezy Collatza pozostaje w mocy. Jednak, w dalszych rozważaniach pomocne będą własności niestandardowego modelu tej teorii a także parę twierdzeń tej teorii.<br /> | Poprzednia obserwacja stwierdzająca, że w tej teorii nie można przeprowadzić dowodu tezy Collatza pozostaje w mocy. Jednak, w dalszych rozważaniach pomocne będą własności niestandardowego modelu tej teorii a także parę twierdzeń tej teorii.<br /> | ||
Wersja z 10:13, 12 sie 2025
Finally!
Work on the problem took 83 years.
We succeeded. We are changing the status of the "Collatz conjecture" to [1]
June 5, 2022 version Collatz theorem submitted to TCS Journal.
A shortened and less formal version of the proof can be found here [2].
Spis treści
- 1 Introduction
- 2 Our observations from 2004
- 3 Correct formulation of the Collatz theorem
- 4 Stop formula
- 5 Elementarna teoria dodawania liczb naturalnych
- 6 Algorytmiczna teoria liczb naturalnych
- 7 Analiza formuły stopu
- 8 Trójki
- 9 Drzewo Collatza
- 10 Własności obliczeń na trójkach
- 11 Kalejdoskop
- 12 Archiwum kolejnych wersji pracy
Introduction
Let's consider the statement
for every natural number [math]n[/math], the following program [math]Cl[/math] has a finite computation.
[math]\color{blue}\qquad Cl:\,\left\{\begin{array}{l} \mathbf{while}\ n \neq 0 \ \mathbf{do} \\
\quad \mathbf{if}\ odd(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{fi} \\
\mathbf{od} \end{array}\right\} [/math]
We begin by noting that the truth of the above statement entails the truth of Collatz's thesis as it was formulated before World War II.
But in 1937, neither computers nor programming languages existed.
On the other hand, the theory of algorithms did exist and was already well developed. The theory of recursive functions was developed in Göttingen (David Hilbert and his students), Budapest (Rozsza Pterer, Laszlo Kalmar), ...
In London, Alan Turing created the abstract Turing machine.
In Moscow, Kolmogorov and in Kazan, Maltsev explored the concept of a computable function.
In Warsaw, Alfred Tarski, together with his students Mojżesz Presburger and Stanisław Jaskowski, obtained important results concerning the theory of addition of natural numbers.
Our observations from 2004
- The Collatz algorithm [math]Cl[/math] does not require multiplication or division operations. Multiplying by 3 (because 3x=x+x+x) and dividing by 2 (a simple algorithm adding every other 1 is sufficient), is sufficient.
- In the algebraic structure [math]\mathfrak{M}[/math], which is a non-standard model of the elementary theory of addition of natural numbers (there is one, see below), the algorithm [math]Cl[/math] has an infinite computation for many arguments.
- Therefore, the Collatz theorem cannot be proven based on the axioms of the elementary theory of addition of natural numbers.
- Moreover, in the language of elementary theory of addition, there is no stopping formula for the Collatz algorithm! So what do we have to prove?
Correct formulation of the Collatz theorem
In the standard structure of natural numbers with the addition operation, our program [math]Cl[/math] has a finite computation for each argument n.
Stop formula
i.e.
A necessary and sufficient condition for the computation to be finite
Therefore, we need to create a formula [math]\theta[/math] (a logical expression) such that it evaluates to true if and only if the computation of the program [math]Cl[/math] is finite. There are many such formulas in the language of program calculation, i.e. algorithmic logic.
,[math]\qquad \theta:\,\left\{\begin{array}{l} \mathbf{while}\ n \neq 0 \ \mathbf{do} \\
\quad \mathbf{if}\ odd(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{fi} \\
\mathbf{od} \end{array}\right\} (n=1) [/math]
The value of the [math]\theta[/math] formula depends only on the initial value of the "n" variable. This formula is satisfied by the value of the variable "n" if and only if the evaluation of the while ... program is finished and the final value of the variable "n" is equal to 1.
Other formulas can also be considered, e.g.,
,[math]\qquad \xi:\,\bigcup \left\{\overbrace{\begin{array}{l} \mathbf{if}\ n \neq 0 \ \mathbf{then} \\
\quad \mathbf{if}\ odd(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{fi} \\
\mathbf{fi} \end{array} }^{K}\right\} (n=1) [/math]
{co reads: "there exists an iteration [math]K^i[/math] of the program [math]K[/math] such that after executing [math]K^i[/math] the equality [math]n=1[/math] is satisfied."}
In other words, we are dealing with an upper bound on the values of the formulas [math]K^i(n=1)[/math], where [math]i= 0,1,2 \dots[/math].
The second part of the problem is much more difficult: we must prove the stopping formula using the axioms of program calculus and the axioms of the algorithmic theory of natural numbers.
Elementarna teoria dodawania liczb naturalnych
Poprzednia obserwacja stwierdzająca, że w tej teorii nie można przeprowadzić dowodu tezy Collatza pozostaje w mocy. Jednak, w dalszych rozważaniach pomocne będą własności niestandardowego modelu tej teorii a także parę twierdzeń tej teorii.
Teoria ta jest wyznaczona przez podanie trzech składników: języka, logiki czyli operacji konsekencji oraz aksjomatów specyficznych dla tej teorii.
Język. Wyrażenia języka zbudowane są z następujących symboli: symbole zmiennych np. x,y,n, symbou + dwuargumentoweji operacji, symbolu = dwuargumentowej relacji, symboli 0,1 stałych i symboli funktorów logicznych oraz symboli pomocniczych np. nawiasy
.
Przykładami wyrażeń są ...
Logika. Operacja konsekwencji (wnioskowania) jest wyznaczona przez podanie aksjomatów logiki pierwszego rzędu i reguł wnioskowania.
Aksjomaty.
Modele arytmetyki Presburgera Zgodnie z przewidywaniami ciąg standardowych wartości 0,1,2,3, ... jest modelem tej teorii.
Stanisław Jaśkowski in 1929 odkrył inny,niestandardowy model arytmetyki Presburgera.
The universe of the model is a subset of the set of complex numbers [math]a+\imath b[/math] where [math]a \in \mathbb{Z} [/math] i.e. a is an integer number and [math]b \in \mathbb{Q}^+ [/math] is a positive rational number. Additionally, whenever [math]b=0 [/math] we have [math]a\gt0[/math]. Addition is defined as usual addition of complex numbers.
Oba modele są obliczalne. Istnieją też modele nieobliczalne, dowolnie wysokiej mocy.
Algorytmiczna teoria liczb naturalnych
- Język. Alfabet języka zawiera zbiór zmiennych, np. x,y. funktor + dwiargumentowego działania dodawania, dwie stałe 0 i 1, znak relacji = równości.
Termy (tj. wyrażenia nazwowe: jest to najmniejszy zbiór wyrażeeń zawierający zmienne, stałe i zamknięty ze wzgledu na lączenie dwu termów w ten sposób (t1 + t2).
Formuły.
- Logika. Rachunek programów. Rachunek programów zawiera w sobie logikę pierwszego rzędu. Język rachunku programów oprócz formuł pierwszego rzędu zaiera formuły algorytmiczne. Najprostsza taka formuła to napis składający się z programu i następującej po nim formuły (zwykle formuły pierwszego rzędu).
Do aksjomatów logiki pierszego rzędu należy dodać aksjomaty opisujące własności spójników programotwórczych, zob. Logika algorytmiczna.
Do reguł wnioskowania logiki pierwszego rzędu należy dodać reguły specyficzne dla rachunku programów.
- Aksjomaty teorii.
Tylko trzy formuły.
[math]
\begin{eqnarray}
\tag{ATN1} \forall_x\, x+1 \neq 0 &&\\
\tag{ATN2} \forall_{x,y}\,x+1=y+1 \implies x=y &&\\
\tag{ATN3}\forall_x\, \{y :=0; \mathbf{while}\ y\neq x\ \mathbf{do}\ y:=y+1\ \mathbf{od} \}\,(y=x) &&
\end{eqnarray} [/math]
Są to właściwie aksjomaty teorii następnika.
Formuła ATN1 stwierdza, że 0 nie jest następnikiem żadnej liczby naturalnej.
Formuła ATN2 stwierdza, że następnik jest funkcją róznowartosciową.
Formuła ATN3 stwierdza, że każda liczba naturalna jest osiągalna z zera przez dodanie skończonej liczby jedynek.
W tej teorii można napisać definicje działań dodawania, mnożenia i każdej funkcji obliczalnej.
Analiza formuły stopu
xxx
Trójki
Spostrzeżenie (wynikłe z przygladania się formule stopu).
[math]\forall_{n \neq 0} \exists_{x,y,z}\ n \cdot 3^x+y=2^z [/math]
Drzewo Collatza
Własności obliczeń na trójkach
Tutaj napiszemy więcej
Kalejdoskop
Oglądaj rysunki, wykonuj obliczenia, rozwiązuj zadania, formułuj swoje zdanie, próbuj je uzasadnić, ...
Tu znajdziesz ....
Obliczenia utemperowane
Trzy zadania. Odpowiedz czy są one jakos powiązane?
- Masz do dyspozycji bardzo wiele trójkątnych płytek, w dwu kolorach.
Czy potrafisz ułożyć chodnik łączący posesje o numerze n z numerem 1?
- Ułamek piętrowy
- Czy obliczenie 3x+1 jest skończone dla każdej liczby naturalnej?
Struktury algebraiczne
Struktura liczb naturalnych.
Algebra Jaśkowskiego.
Teorie
elementarna teoria liczb naturalnych z dodawaniem.
algorytmiczna teoria liczb naturalnych
Zadania
[math]\alpha[/math]
Archiwum kolejnych wersji pracy
[CollatzConjecturebecomesTheorem11Aug23 http://lem12.uksw.edu.pl/images/3/3b/CollatzConjecturebecomesTheorem11Aug23.pdf]
