Collatz theorem: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(Collatz thesis reformulate)
(Elementary theory od addition of natural numbers and its models)
 
(Nie pokazano 9 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
Collatz conjecture is  valid in the standard structure of natural numbers, therefore  it is  Collatz theorem .<br />
+
Collatz conjecture is  valid in the standard structure of natural numbers, therefore  it is  <big>Collatz theorem</big> .<br />
  
 
Finally!<br />
 
Finally!<br />
Linia 7: Linia 7:
 
An abridged version of the proof is  [http://lem12.uksw.edu.pl/images/9/9f/MainPointsProofCollatz.pdf  here].<br />
 
An abridged version of the proof is  [http://lem12.uksw.edu.pl/images/9/9f/MainPointsProofCollatz.pdf  here].<br />
 
==ntroduction==
 
==ntroduction==
Rozpatrzmy zdanie<br/>
+
Consider the following sentence<br/>
dla każdej liczby naturalnej <math>n</math>, poniższy program <math>Cl </math> ma obliczenie sończone<br/>
+
for every natural number  <math>n</math>, the program <math>Cl </math> has the finite computation<br/>
<math>\color{blue}\qquad Cl:\,\left\{\begin{array}{l}  \mathbf{while}\ n \neq 0 \ \mathbf{do} \\
+
<math>\qquad Cl:\,\left\{\begin{array}{l}  \mathbf{while}\ n \neq 0 \ \mathbf{do} \\
\quad \mathbf{if}\  nieparzyste(n) \ \mathbf{then}\  n:=3n+1 \  \mathbf{else}\ n:=n/2\  \mathbf{fi} \\
+
\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 />
Zaczynamy od uwagi, że prawdziwośc powyższego zdania pociaga za sobą prawdzowość tezy Collatza, tak jak ona została sformułowana przed II wojną światową. <br />
+
Note, the truthfulness of the above sentence implies the truthfulness of Collatz's thesis, as it was formulated before World War II, in 1937.. <br />
Ale w  r.1937  nie istniały komputery ani języki programowania<br />
+
But then there were no computers or computer programming languages<br />
.Z drugiej strony istniała i była już mocno rozwinięta teoria algorytmów. Teorię funkcji rekurencyjnych rozwijanow w Getyndze (David Hilbert i jego uczniowie), Budapeszcie (Rozsza Pterer, Laszlo Kalmar), ...<br />
+
On the other hand, there was and was already a highly developed theory of algorithms. The theory of recursive functions was developed in Göttingen (David Hilbert and his students), Budapest (Rozsza Pterer, Laszlo Kalmar), ... <br />
W Londynie Alan Turing stworzył abstrakcyjną maszynę Turinga.<br />
+
In Princeton, Alonzo Church published papers on <math>\lambda</math>-calculus.
W Moskwie Kołmogorow i w Kazaniu Malcew badali pojęcie funkcji obliczalnej. <br />
+
In London, Alan Turing created the abstract Turing machine. <br />
 +
In Moscow, Kolmogorov and in Kazan, Maltsev studied the concept of a computable function. <br />
 
<br />
 
<br />
W Warszawie Alfred Tarski wraz z uczniami Mojżeszem Presburgerem, Stanisławem Jaskowskim uzyskali ważne wyniki dotycące teorii dodawania liczb naturalnych.
+
In Warsaw, Alfred Tarski and his students Mojżesz Presburger and Stanisław Jaskowski obtained important results on the theory of adding natural numbers.
  
 
==Remark made in  2004==
 
==Remark made in  2004==
Linia 56: Linia 57:
  
  
Nonstandard model of Presburger arithmetic was invented by Stanisław Jaśkowski in 1929.
+
<big>Nonstandard model of Presburger arithmetic</big> was invented by Stanisław Jaśkowski in 1929.
  
 
[[Plik:MonStandardModel.png|center|thumb|600px|Nonstandard model of Presburger arithmetic]]
 
[[Plik:MonStandardModel.png|center|thumb|600px|Nonstandard model of Presburger arithmetic]]
 
The universe of the model is a subset of the set of complex numbers <math>a+\imath b</math>  
 
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,
+
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>0</math>.
with usual addition of complex numbers.
+
Addition is defined as  usual addition of complex numbers.
  
 
==Algorithmic theory of natural numbers ==
 
==Algorithmic theory of natural numbers ==

Aktualna wersja na dzień 13:39, 28 wrz 2022

Collatz conjecture is valid in the standard structure of natural numbers, therefore it is Collatz theorem .

Finally!
Many people worked on the Collatz problem for more than 83 years.
We succeeded. The statute of 'Collatz conjecture" is now Collatz theorem.
Here is a version of June 5, 2022 theorem of Collatz submitted to TCS Journal .
An abridged version of the proof is here.

ntroduction

Consider the following sentence
for every natural number [math]n[/math], the program [math]Cl [/math] has the finite computation
[math]\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]
Note, the truthfulness of the above sentence implies the truthfulness of Collatz's thesis, as it was formulated before World War II, in 1937..
But then there were no computers or computer programming languages
On the other hand, there was and was already a highly developed theory of algorithms. The theory of recursive functions was developed in Göttingen (David Hilbert and his students), Budapest (Rozsza Pterer, Laszlo Kalmar), ...
In Princeton, Alonzo Church published papers on [math]\lambda[/math]-calculus. In London, Alan Turing created the abstract Turing machine.
In Moscow, Kolmogorov and in Kazan, Maltsev studied the concept of a computable function.

In Warsaw, Alfred Tarski and his students Mojżesz Presburger and Stanisław Jaskowski obtained important results on the theory of adding natural numbers.

Remark made in 2004

  • The Collatz algorithm does not require operations of multiplication and division. For the operation of multiplying by 3 is done as x+x+x. Division by 2 is done by an auxiliary algorithm.
  • In the non-standard model of elementary theory of addition of natural numbers (best known as Presburger arithmetic) the computation of Collatz algorithm [math]Cl[/math] is infinite for every unreachable number [math]n[/math].
  • Hence, Collatz conjecture is unprovable in the elementary theory of addition of natural numbers.
  • Moreover, the halting property of Collatz algorithm is not expressible in the language of first-order theory of addition of natural numbers (aka Presburger arithmetic).

Collatz thesis reformulated

In the standard model of natural numbers with addition the Collatz algorithm [math] CL [/math] for every number [math] n [/math] terminates.
But, how to describe standard model up to isomorphisms?

Halting formula

Należy zatem stworzyć formułę [math]\theta[/math] (wyrażenie logiczne) taką, że przyjmuje ona wrtośc prawda wtedy i tylko wtedy gdy obliczenie programu [math]Cl[/math] jest skończone. Takich formuł jest wiele w języku urachunku programów, tj. logiki algorytmicznej.
,[math]\qquad \theta:\,\left\{\begin{array}{l} \mathbf{while}\ n \neq 0 \ \mathbf{do} \\ \quad \mathbf{if}\ nieparzyste(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{fi} \\ \mathbf{od} \end{array}\right\} (n=1) [/math]
Można też rozważać inne formuły, np,
,[math]\qquad \xi:\,\bigcup \left\{K:\,\begin{array}{l} \mathbf{if}\ n \neq 0 \ \mathbf{then} \\ \quad \mathbf{if}\ nieparzyste(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{fi} \\ \mathbf{fi} \end{array}\right\} (n=1) [/math]
{co się czyta: istnieje taka iteracja ,[math]K^i[/math] programu [math]K[/math], że po wykonaniu [math]K^i[/math] zachodzi równość [math]n=1[/math] .}
Druga część zadania jest znacznie trudniejsza: nalezy przeprowadzić dowód formuły stopu posiłkując się aksjomatami rachunku programów i aksjomatami algorytmicznej teorii liczb naturalnych.


Elementary theory od addition of natural numbers and its models

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.


Nonstandard model of Presburger arithmetic was invented by Stanisław Jaśkowski in 1929.

Nonstandard model of Presburger arithmetic

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.

Algorithmic theory of natural numbers

  • 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

Triples

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]

Collatz tree

xxx

Własności obliczeń na trójkach

Archive

\On Collatz theorem II.pdf wersja z 5 czerwca 2022

]wersja z 20 wrzesnia 2021

algorytmy wokół Collatzowe

wersja z 27 wrzesnia 2021

wersja z 7 pażdziernika 2021