Collatz: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(Formuła stopu)
 
(Nie pokazano 66 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
 
Nareszcie!<br />
 
Nareszcie!<br />
 
Praca nad problemem trwała 83 lata.<br />
 
Praca nad problemem trwała 83 lata.<br />
 
+
Udało się. Zmieniamy statut   ''hipotezy Collatza'' na [http://lem12.uksw.edu.pl/images/2/21/HotelCollatza.pdf  '''twierdzenie Collatza'''].<br />
 
+
Wersja z 5 czerwca 2022 [https://dx.doi.org/10.2139/ssrn.4158238 '''twierdzenie Collatza''']  przedłozona do TCS Journal  .<br />
Udało się zmienić statut z ''hipoteza Collatza'' na '''twierdzenie Collatza'''.<br />
+
Skróconą i niezbyt formalną wersję dowodu znajdziesz w tym [http://lem12.uksw.edu.pl/images/9/9f/MainPointsProofCollatz.pdf miejscu].<br />
Argumenty znajdziesz [http://lem12.uksw.edu.pl/images/a/a2/On-Collatz-thm-3-09-21.pdf tu].<br />
+
 
+
 
==Wprowadzenie==
 
==Wprowadzenie==
 
Rozpatrzmy zdanie<br/>
 
Rozpatrzmy zdanie<br/>
dla każdej liczby naturalnej <math>n</math>, poniższy program ma obliczenie sończone<br/>
+
dla każdej liczby naturalnej <math>n</math>, poniższy program <math>Cl </math> ma obliczenie sończone<br/>
{| class="wikitable"
+
<math>\color{blue}\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} \\
'''while''' n<> 0 '''do'''<br/>
+
\mathbf{od} \end{array}\right\} </math> <br />
'''if''' nieparzyste(n) '''then''' n:=3n+1  '''else''' n:=n/2 '''fi'''<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 />
'''od''' <br/>
+
Ale w  r.1937  nie istniały komputery ani języki programowania<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 />
 +
W Londynie Alan Turing stworzył abstrakcyjną maszynę Turinga.<br />
 +
W Moskwie Kołmogorow i w Kazaniu Malcew badali pojęcie funkcji obliczalnej. <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.
  
Zaczynamy od uwagi, że prawdziwośc powyższego zdania pociaga za sobą prawdzowość tezy Collatza. Ale w  r.1937  nie istniały komputery ani języki programowania.
 
 
==Spostrzeżenie z r. 2004==
 
==Spostrzeżenie z r. 2004==
* algorytm nie potrzebuje operacji mnożenia,
+
* algorytm nie potrzebuje operacji mnożenia ani dzielenia przez 2,
* w strukturze algebraicznej, która jest niestandardowym modelem elementarnej teorii dodawania liczb naturalnychnasz algorytm ma obliczenie nieskończone.
+
* w strukturze algebraicznej, która jest niestandardowym modelem elementarnej teorii dodawania liczb naturalnych  (jest taka) algorytm <math>Cl</math> ma dla pewnych argumentów obliczenie nieskończone.
* Tezy Collatza nie można udowodnić na podstawie aksjomatów elementarnej teorii dodawania liczb naturalnych.
+
* a więc tezy Collatza nie można udowodnić na podstawie aksjomatów elementarnej teorii dodawania liczb naturalnych,
 +
* co więcej, w języku elementarnej teorii dodawania nie istnieje formuła stopu dl algorytmu Collatza!. Czego więc mamy dowieść?
 +
 
 
==Poprawiamy sformułowanie tezy==
 
==Poprawiamy sformułowanie tezy==
 
W standardowej strukturze liczb naturalnych z operacją dodawania
 
W standardowej strukturze liczb naturalnych z operacją dodawania
Linia 26: Linia 29:
 
==Formuła stopu==
 
==Formuła stopu==
 
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.<br/>
 
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.<br/>
,<math> \theta:\,\left\{\begin{array}{l}  \mathbf{while}\ n \neq 0 \ \mathbf{do} \\
+
,<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} \\
 
\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>
 
\mathbf{od} \end{array}\right\} (n=1) </math>
 
<br />
 
<br />
Można też rozważać inne formuły. <br/>
+
Można też rozważać inne formuły, np, <br/>
Druga część zadania jest znacznie trudniejsza: przeprowadzić dowód formuły stopu posiłkując się aksjomatami rachunku programów i aksjomatami algorytmicznej teorii liczb naturalnych.<br/>
+
,<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>  <br/>
 +
{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>  .} <br/>
 +
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.<br/>
  
 
<br />
 
<br />
 +
==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 />
 +
<br />
 +
Teoria ta jest wyznaczona przez podanie trzech składników: języka, logiki czyli operacji konsekencji oraz aksjomatów specyficznych dla tej teorii. <br />
 +
'''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<br />
 +
.
 +
Przykładami wyrażeń są ...<br />
 +
 +
'''Logika.''' Operacja konsekwencji (wnioskowania) jest wyznaczona przez podanie aksjomatów logiki pierwszego rzędu i reguł wnioskowania. <br />
 +
'''Aksjomaty.'''
 +
 +
==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.<br />
 +
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).<br />
 +
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. <br />
 +
 +
* Aksjomaty teorii. <br />
 +
Tylko trzy formuły. <br />
 +
<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><br />
 +
 +
Są to właściwie aksjomaty teorii następnika.<br/>
 +
Formuła ATN1 stwierdza, że 0 nie jest następnikiem żadnej liczby naturalnej. <br/>
 +
Formuła ATN2 stwierdza, że następnik jest funkcją róznowartosciową. <br/>
 +
Formuła ATN3 stwierdza, że każda liczba naturalna jest ''osiągalna'' z zera przez dodanie skończonej liczby jedynek.<br/>
 +
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).<br />
 +
 +
<math>\forall_{n \neq 0} \exists_{x,y,z}\ n \cdot 3^x+y=2^z  </math>
 +
 +
==Drzewo Collatza==
 +
xxx
 +
==Własności obliczeń na trójkach==
 +
 +
== Archiwum kolejnych wersji pracy ==
 +
[https://dx.doi.org/10.2139/ssrn.4158238 \On Collatz theorem II.pdf wersja z 5 czerwca 2022 ]
 +
 +
][http://lem12.uksw.edu.pl/images/a/ab/On-Collatz-thm17-09-21.pdf wersja z 20 wrzesnia 2021]
 +
 +
[http://lem12.uksw.edu.pl/images/7/7d/Algorytmy-bliskie-Collatzowi.pdf  algorytmy wokół Collatzowe]
 +
 +
[http://lem12.uksw.edu.pl/images/c/c0/On-Collatz-thm-27-09-21.pdf  wersja z 27 wrzesnia 2021]
 +
 +
[http://lem12.uksw.edu.pl/images/8/8f/On-Collatz-thm-7-10-21.pdf  wersja z 7 pażdziernika 2021]

Aktualna wersja na dzień 12:04, 5 wrz 2022

Nareszcie!
Praca nad problemem trwała 83 lata.
Udało się. Zmieniamy statut hipotezy Collatza na twierdzenie Collatza.
Wersja z 5 czerwca 2022 twierdzenie Collatza przedłozona do TCS Journal .
Skróconą i niezbyt formalną wersję dowodu znajdziesz w tym miejscu.

Wprowadzenie

Rozpatrzmy zdanie
dla każdej liczby naturalnej [math]n[/math], poniższy program [math]Cl [/math] ma obliczenie sończone
[math]\color{blue}\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} \\ \mathbf{od} \end{array}\right\} [/math]
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ą.
Ale w r.1937 nie istniały komputery ani języki programowania
.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), ...
W Londynie Alan Turing stworzył abstrakcyjną maszynę Turinga.
W Moskwie Kołmogorow i w Kazaniu Malcew badali pojęcie funkcji obliczalnej.

W Warszawie Alfred Tarski wraz z uczniami Mojżeszem Presburgerem, Stanisławem Jaskowskim uzyskali ważne wyniki dotycące teorii dodawania liczb naturalnych.

Spostrzeżenie z r. 2004

  • algorytm nie potrzebuje operacji mnożenia ani dzielenia przez 2,
  • w strukturze algebraicznej, która jest niestandardowym modelem elementarnej teorii dodawania liczb naturalnych (jest taka) algorytm [math]Cl[/math] ma dla pewnych argumentów obliczenie nieskończone.
  • a więc tezy Collatza nie można udowodnić na podstawie aksjomatów elementarnej teorii dodawania liczb naturalnych,
  • co więcej, w języku elementarnej teorii dodawania nie istnieje formuła stopu dl algorytmu Collatza!. Czego więc mamy dowieść?

Poprawiamy sformułowanie tezy

W standardowej strukturze liczb naturalnych z operacją dodawania nasz program ma obliczenie skończone, dla każdego argumentu n..

Formuła stopu

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.


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.

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

xxx

Własności obliczeń na trójkach

Archiwum kolejnych wersji pracy

\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