Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami

Wersja z 19:32, 21 gru 2014

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 [math] :=, '''while''' '''do''' '''od''' [/math] 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

• Fakt Jego własność stop 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.

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]

co czytamy: 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.
Dla przeprowadzenia dowodu wystarczy udowodnienie innej hipotezy:
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 \ltn) [/math]

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

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.