Collatz: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
Linia 50: Linia 50:
  
 
==Algorytmiczna teoria liczb naturalnych==
 
==Algorytmiczna teoria liczb naturalnych==
<math>\[\tag{ATN}  \mbox{{Axioms of}}\ \mathcal{ATN} \  
+
{| class="wikitable"
 +
|-
 +
! Tekst nagłówka !! Tekst nagłówka !! Tekst nagłówka
 +
|-
 +
| Treść komórki || Treść komórki || Treść komórki
 +
|-
 +
| Treść komórki || Treść komórki || Treść komórki
 +
|-
 +
| Treść komórki || Treść komórki || Treść komórki
 +
|}
 +
<math>\tag{ATN}  \mbox{{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 \} \] </math>
+
\end{array} \right \} </math>
  
 
==Analiza formuły stopu==
 
==Analiza formuły stopu==

Wersja z 20:31, 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

Tekst nagłówka Tekst nagłówka Tekst nagłówka
Treść komórki Treść komórki Treść komórki
Treść komórki Treść komórki Treść komórki
Treść komórki Treść komórki Treść komórki

[math]\tag{ATN} \mbox{{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