Tekst źródłowy strony 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.<br />
Zob. poniższy artykuł [[Plik:On-Euclids-algorithm-2018.pdf]].
W wielkim skrócie:<br />


[[Media:http://lem12.uksw.edu.pl/images/4/49/On-Euclids-algorithm-2018.pdf]] 

* '''Fakt''' Jego własność stop nie wynika z aksjomatów Peano, ponieważ algorytm zapętla się w [[Niestandardowy model liczb naturalnych|modelu (niestandardowym) arytmetyki liczb naturalnych z dodawaniem]].
* '''Twierdzenie''' Formuła stopu algorytmu Euklidesa jest twierdzeniem arytmetyki algorytmicznej. 

:Formuła ta, jak i formuła wyrażająca poprawność algorytmu Euklidesa, dają się wyprowadzić z aksjomatów algorytmicznej arytmetyki, zob. [[analiza algorytmu Euklidesa]].

== 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.

== Problem Collatza ==

L. Collatz sformułował swoją hipotezę w r. 1937, do dzisiaj nie znamy dowodu tej tezy ani kontrprzykladu. 
:<math>(\forall n)\left \{ \begin{array}{l} \mathbf{while}\ n\neq 1\\ \mathbf{do}\\ \quad \mathbf{if}\ n\ is\ odd\\ \quad \mathbf{then}\\ \qquad n := 3*n+1\\ \quad \mathbf{else}\\ \qquad n:= n \div 2\\ \quad \mathbf{fi}\\ \mathbf{od}\end{array}\right\} (n=1)  </math>

<small>''co czytamy''</small>: dla każdego 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''' W modelu niestandardowym arytmetyki liczb naturalnych z dodawaniem algorytm Collatza ma obliczenia nieskończone.

'''Hipoteza''' W algorytmicznej teorii liczb naturalnych z dodawaniem (bez mnożenia) powyższa formuła algorytmiczna posiada dowód.<br />
Dla przeprowadzenia dowodu wystarczy udowodnienie innej hipotezy:<br />
'''Hipoteza''' Dla każdej liczby naturalnej n istnieje liczba naturalna k taka, że 
<math>(\forall n)(\exists k)y=n \implies\left \{ \begin{array}{l}    \mathbf{if}\ y\ is\ odd\\   \mathbf{then}\\ \quad y := 3*y+1\\   \mathbf{else}\\ \quad y:= y \div 2\\   \mathbf{fi}\\  \end{array}\right\}^k (y < n)  </math><br />

'''Hipoteza''' Dla każdej liczby naturalnej <math>n</math> istnieje liczba naturalna <math>k</math> taka, że 
<math>(\forall n)(\exists k)(y=n;\, (     \mathbf{if }\ y\ is\ \mathrm{odd} \    \mathbf{ then } \ y := 3*y+1 \   \mathbf{ else } \  y:= y \div 2  \  \mathbf{ fi})^k) (y < n)  </math><br />


To jest teoria w której język jest algorytmiczny, operacja konsekwencji jest okreslona przez aksjomaty i reguły wnioskowania logiki algorytmiczne, aksjomaty specyficzne to aksjomaty 1-go rzędu arytmetyki Presburgera liczb naturalnych z dodawaniem:
Napisac te aksjomaty gdy tylko poprawi sie parser formuł.

'''Pytanie''' Czy mnożenie coś zmieni? Zauważ, ze mnożenie jest określone przez program NAPISZE ten program.



'''Fakt''' Jeśli hipoteza Collatza jest prawdziwa to istnieje dowód w algorytmicznej teorii liczb naturalnych.