Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami
Z Lem
| Linia 15: | Linia 15: | ||
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. | ||
| + | :<math>(\forall n)\, \mathbf{while}\ n\neq 1\ \mathbf{do}\ \mathbf{if}\ n\ is\ odd\ \mathbf{then}\ n := 3*n+1\ \mathbf{else}\ n:= n \div 2\ \mathbf{fi}\ \mathbf{od} n=1 </math> | ||
Wersja z 00:01, 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
- 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)\, \mathbf{while}\ n\neq 1\ \mathbf{do}\ \mathbf{if}\ n\ is\ odd\ \mathbf{then}\ n := 3*n+1\ \mathbf{else}\ n:= n \div 2\ \mathbf{fi}\ \mathbf{od} n=1 [/math]
