Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami
Z Lem
| Linia 10: | Linia 10: | ||
Operacje dodawania i mnożenia są programowalne | Operacje dodawania i mnożenia są programowalne | ||
| − | [[Algorytm Euklidesa] | + | == [[Algorytm Euklidesa] == |
* Jego własność stop nie wynika z aksjomatów Peano, ponieważ algorytm zapętla się w modelu (niestandardowym) arytmetyki liczb naturalnych z dodawaniem. | * Jego własność stop nie wynika z aksjomatów Peano, ponieważ algorytm zapętla się w modelu (niestandardowym) arytmetyki liczb naturalnych z dodawaniem. | ||
* Natomiast daje się wyprowadzić z aksjomatów algorytmicznej arytmetyki, zob. [[analiza algorytmu Euklidesa]]. | * Natomiast daje się wyprowadzić z aksjomatów algorytmicznej arytmetyki, zob. [[analiza algorytmu Euklidesa]]. | ||
| − | Algorytmiczny aspekt ostatniego twierdzenia Fermata | + | == Algorytmiczny aspekt ostatniego twierdzenia Fermata == |
| + | |||
| + | == Problem Collatza == | ||
| − | |||
L. Collatz sformułował swoją hipotezę w r. 1937, do dzisiaj nie znamy dowodu tej tezy ani kontrprzykladu. | L. Collatz sformułował swoją hipotezę w r. 1937, do dzisiaj nie znamy dowodu tej tezy ani kontrprzykladu. | ||
| − | :<math>(\forall n)\ | + | :<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 | ||
| + | |||
| + | W modelu niestandardowym arytmetyki liczb naturalnych z dodawaniem algorytm Collatza ma obliczenia nieskończone. | ||
| + | |||
| + | Fakt | ||
| + | |||
| + | Jeśli hipoteza Collatza jest prawdziwa to istnieje dowód w algorytmicznej teorii liczb naturalnych. | ||
Wersja z 08:07, 21 lut 2013
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]
- Jego własność stop nie wynika z aksjomatów Peano, ponieważ algorytm zapętla się w modelu (niestandardowym) arytmetyki liczb naturalnych z dodawaniem.
- Natomiast daje się wyprowadzić z aksjomatów algorytmicznej arytmetyki, zob. analiza algorytmu Euklidesa.
Algorytmiczny aspekt 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
W modelu niestandardowym arytmetyki liczb naturalnych z dodawaniem algorytm Collatza ma obliczenia nieskończone.
Fakt
Jeśli hipoteza Collatza jest prawdziwa to istnieje dowód w algorytmicznej teorii liczb naturalnych.
