Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(→‎Przyczynki do problemu Collatza)
Linia 39: Linia 39:
 
== Przyczynki do problemu Collatza ==
 
== Przyczynki do problemu Collatza ==
  
−
L. Collatz sformułował swoją hipotezę w r. 1937, do dzisiaj nie znamy dowodu tej tezy ani kontrprzykladu.
+
  [Media:OnCollatzTheorem.pdf]
−
:<math>(\forall n \in N)\left \{ \begin{array}{l} \mathbf{while}\ n\neq 1\ \mathbf{do}\\ \quad \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\ \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi}\\ \mathbf{od}\end{array}\right\} (n=1)  </math>
+
−
 
+
−
<small>''co czytamy''</small>: dla każdej liczby naturalnej n, powyżej podany program (Collatza) kończy swoje obliczenia.<br />
+
−
 
+
−
Istnieje obszerna literatura tego zagadnienia. Ustanowiono nagrodę pieniężną za rozwiązanie problemu.
+
−
 
+
−
Spostrzeżenie
+
−
 
+
−
'''Fakt 1''' W modelu niestandardowym arytmetyki liczb naturalnych z dodawaniem algorytm Collatza ma obliczenia nieskończone. Zob. dodatek A w pracy [[Media:On-Euclids-algorithm-2018.pdf]] i sprawdź, że argumenty wykazujące niemożność udowodnienia algorytmu Euklidesa w elementarnej arytmetyce liczb naturalnych (teorii Peano) przenoszą się na przypadek algorytmu Collatza.<br />
+
−
 
+
−
'''Fakt 2''' Jeśli hipoteza Collatza jest prawdziwa to istnieje jej dowód w algorytmicznej teorii liczb naturalnych.
+
−
 
+
−
 
+
−
Korzystając z rachunku programów tj. logiki algorytmicznej możemy formułę stopu tego programu zapisać tak<br />
+
−
 
+
−
:<math>\bigcup\, \{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \} (\exists k \ n=2^k)  </math>
+
−
 
+
−
Stosując wielokrotnie aksjomat Ax21 otrzymamy kolejne równoważne formuły<br />
+
−
: <math>\begin{array}{l}
+
−
\bigcup\, \{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \} (\exists k \ n=2^k) \Leftrightarrow  \\
+
−
 
+
−
(\exists k \ n=2^k) \lor \\ \qquad \bigcup\, \{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \} \left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \}(\exists k \ n=2^k)\right ) \Leftrightarrow  \\
+
−
 
+
−
(\exists k \ n=2^k) \lor \\ \left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \}(\exists k \ n=2^k)\right ) \lor \\ \qquad  \bigcup\, \{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \} \left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \}^2 (\exists k \ n=2^k)\right )  \Leftrightarrow  \\
+
−
 
+
−
(\exists k \ n=2^k) \lor \\
+
−
\left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \}(\exists k \ n=2^k)\right ) \lor \\
+
−
\left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \}^2(\exists k \ n=2^k)\right ) \lor \\
+
−
\qquad  \bigcup\, \{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \} \left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3*n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \}^3 (\exists k \ n=2^k)\right )  \Leftrightarrow  \\
+
−
 
+
−
\dots \\
+
−
 
+
−
(\exists k \ n=2^k) \lor \\
+
−
\left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3n+1\  \mathbf{else}\  n\leftarrow n / 2 \ \mathbf{fi} \}(\exists k \ n=2^k)\right ) \lor \\
+
−
\left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3n+1\  \mathbf{else}\  n\leftarrow n / 2 \ \mathbf{fi} \}^2(\exists k \ n=2^k)\right ) \lor \\
+
−
\ \ \ \dots \\
+
−
\left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3n+1\  \mathbf{else}\  n\leftarrow n \div 2 \ \mathbf{fi} \}^i(\exists k \ n=2^k)\right ) \lor \\
+
−
\qquad  \bigcup\, \{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3n+1\  \mathbf{else}\  n\leftarrow n / 2 \ \mathbf{fi} \} \left (\{  \mathbf{if}\ n\ is\ odd \ \mathbf{then}\  n \leftarrow 3n+1\  \mathbf{else}\  n\leftarrow n / 2 \ \mathbf{fi} \}^{i+1} (\exists k \ n=2^k)\right )  \Leftrightarrow  \\
+
−
\end{array}</math> 
+
−
 
+
−
Inspirując się powyższymi równoważnościami przyjmujemy następującą definicję indukcyjną ciągu podzbiorów zbioru <math>N</math><br />
+
−
<math>S_0=\{n \in N:\,\exists k\,\ n=2^k \}</math><br />
+
−
<math>S_1=\{n \in N:\,3n+1 \in S_0 \}</math><br />
+
−
<math>S_2=\{n \in N:\ n/2 \in S_1 \}</math><br />
+
−
\dots <br />
+
−
<math>S_{i+1}=\{n \in N:\ n\ \mathrm{jest\ nieparzyste\ i\ }3n+1 \in S_i \ \mathrm{lub\ n\ parzyste \ i\ }n/2 \in S_i \}</math><br />
+
−
'''Fakt 3'''
+
−
Hipoteza Collatza jest równoważna następującemu zdaniu<br />
+
−
:<math>N= \mathop\bigcup_{i=0}^\infty\,S_i </math> <br />
+
−
 
+
−
Warto zbadać właściwości podzbiorów <math>S_k </math> <br />
+
−
Zbiór (warstwa) <math>S_0</math> ma oczywiste własności. <br />
+
−
Kolejna warstwa <math>S_1=\{5, 21,85, 341, \dots \} </math> . Elementy tej warstwy możemy wyznaczyć posługując się następującymi zależnościami <math> a_1=5, \ \ a_{j+1}= 4*a_j+1</math>.  <br />
+
−
Warstwa <math>S_2</math> opisana jest wzorami <math> b_1=10, \ \ b_{j+1}= 2*(4*b_j+1)</math>.<br />
+
−
 
+
−
Hipoteza Collatza jest równoważna hipotezie następującej:<br />
+
−
'''Fakt 4''' ''Każda liczba naturalna <math> n </math> jest numerem pary <math>\langle i,j \rangle </math> takiej, że liczba  <math> i </math>  jest numerem warstwy w której znajduje się liczba <math> n </math>, a <math> j </math>  jest numerem liczby <math> n </math>  w tej warstwie. ''
+

Wersja z 08:28, 12 wrz 2018

Jest to zalążek dłuższego tekstu.

Algorytmiczna teoria liczb naturalnych, w skrócie arytmetyka algorytmiczna, jest sformalizowaną teorią wyznaczoną przez trójkę [math]\langle \mathcal{L, C, A} \rangle[/math] gdzie

- [math] \mathcal{L}[/math] jest językiem algorytmicznym. Alfabet języka zawiera zbiór zmiennych, funktory: [math] +1, 0 [/math], predykat [math] = [/math] oraz operatory logiczne [math] \lor, \land, \implies. \neg [/math], funktory programotwórcze  :=, while do od oraz zbiór symboli pomocniczych: nawiasy, przecinek etc.
- [math] \mathcal{ C}[/math] jest operacją konsekwencji wyznaczoną przez aksjomaty i reguły wnioskowania logiki algorytmicznej oraz pojęcie dowodu. Operacja konsekwencji przyporzadkowuje każdemu zbiorowi Z formuł zbiór formuł posiadających dowód w oparciu o zbiór Z.
- [math] \mathcal{A}[/math] jest to zbiór złożony z trzech formuł wyliczonych poniżej

Aksjomaty algorytmicznej teorii liczb naturalnych:

(N1) [math]\color{blue} (\forall n) (n+1 \neq 0 ) [/math]
(N2) [math]\color{blue} (\forall n)(\forall m)(n+1=m+1 \Rightarrow n=m)[/math]
(N3) [math]\color{blue} (\forall n)[m:=0; \mathbf{while}\ m \neq n\ \mathbf{do}\ m:=m+1\ \mathbf{od}](m=n)[/math]

Niektóre fakty

Operacje dodawania i mnożenia są programowalne

Algorytm Euklidesa

Jesteśmy szczęśliwi mogąc przedstawić nowy dowód poprawności algorytmu Euklidesa.
Zob. poniższy artykuł Media:On-Euclids-algorithm-2018.pdf.

W wielkim skrócie:



Algorytmiczny aspekt ostatniego twierdzenia Fermata

  • Pewien program PF4 ma obliczenie dowolnej długości (tj. zapetla sie).
  • Pewien program PF5 zawsze zakończy swe obliczenia.

Oba te fakty sa konsekwencją ostatniego twierdzenia Fermata.

Przyczynki do problemu Collatza

[Media:OnCollatzTheorem.pdf]
Źródło „http://lem12.uksw.edu.pl/index.php?title=Arytmetyka_Algorytmiczna&oldid=2539”