Collatz: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(Algorytmiczna teoria liczb naturalnych)
Linia 50: Linia 50:
  
 
==Algorytmiczna teoria liczb naturalnych==
 
==Algorytmiczna teoria liczb naturalnych==
\[\tag{ATN}  \mbox{{\scriptsize Axioms of}}\ \mathcal{ATN} \  
+
<math>\[\tag{ATN}  \mbox{{\scriptsize Axioms of}}\ \mathcal{ATN} \  
 
\left \{\begin{array}{l}
 
\left \{\begin{array}{l}
 
  \forall_x\, x+1 \neq 0 \\
 
  \forall_x\, x+1 \neq 0 \\
 
  \forall_{x,y}\,x+1=y+1 \implies x=y \\
 
  \forall_{x,y}\,x+1=y+1 \implies x=y \\
 
  \forall_x\, \{y :=0; \mathbf{while}\ y\neq x\ \mathbf{do}\ y:=y+1\ \mathbf{od} \}\,(y=x)
 
  \forall_x\, \{y :=0; \mathbf{while}\ y\neq x\ \mathbf{do}\ y:=y+1\ \mathbf{od} \}\,(y=x)
\end{array} \right \} \]
+
\end{array} \right \} \] </math>
  
 
==Analiza formuły stopu==
 
==Analiza formuły stopu==

Wersja z 20:27, 19 wrz 2021

Nareszcie!
Praca nad problemem trwała 83 lata.


Udało się zmienić statut z hipoteza Collatza na twierdzenie Collatza.
Argumenty znajdziesz tu.

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.

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

[math]\[\tag{ATN} \mbox{{\scriptsize Axioms of}}\ \mathcal{ATN} \ \left \{\begin{array}{l} \forall_x\, x+1 \neq 0 \\ \forall_{x,y}\,x+1=y+1 \implies x=y \\ \forall_x\, \{y :=0; \mathbf{while}\ y\neq x\ \mathbf{do}\ y:=y+1\ \mathbf{od} \}\,(y=x) \end{array} \right \} \] [/math]

Analiza formuły stopu

xxx

Trójki

xxx

Drzewo Collatza

xxx

Własności obliczeń na trójkach