Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami

Wersja z 12:24, 30 lip 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}\ 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 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 Jeśli hipoteza Collatza jest prawdziwa to istnieje jej dowód w algorytmicznej teorii liczb naturalnych.