Arytmetyka Algorytmiczna
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}\ n:=n+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:
- Fakt Własność stopu algorytmu Euklidesa nie wynika z aksjomatów Peano, ponieważ algorytm zapętla się w modelu (niestandardowym) arytmetyki liczb naturalnych z dodawaniem.
- Twierdzenie Formuła stopu algorytmu Euklidesa jest twierdzeniem arytmetyki algorytmicznej.
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
L. Collatz sformułował swoją hipotezę w r. 1937, do dzisiaj nie znamy dowodu tej tezy ani kontrprzykladu.
- [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]
co czytamy: dla każdej liczby naturalnej n, powyżej podany program (Collatza) kończy swoje obliczenia.
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.
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
- [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
- [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]
[math]S_0=\{n \in N:\,\exists k\,\ n=2^k \}[/math]
[math]S_1=\{n \in N:\,3n+1 \in S_0 \}[/math]
[math]S_2=\{n \in N:\ n/2 \in S_1 \}[/math]
\dots
[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]
Fakt 3
Hipoteza Collatza jest równoważna następującemu zdaniu
- [math]N= \mathop\bigcup_{i=0}^\infty\,S_i [/math]
Warto zbadać właściwości podzbiorów [math]S_k [/math]
Zbiór (warstwa) [math]S_0[/math] ma oczywiste własności.
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].
Warstwa [math]S_2[/math] opisana jest wzorami [math] b_1=10, \ \ b_{j+1}= 2*(4*b_j+1)[/math].
Hipoteza Collatza jest równoważna hipotezie następującej:
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.
