Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami
Z Lem
(→Algorytm Euklidesa) |
(→Na problem Collatza) |
||
| (Nie pokazano 73 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
| Linia 1: | Linia 1: | ||
| + | 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 | Aksjomaty | ||
| Linia 5: | Linia 13: | ||
:(N1) <math>\color{blue} (\forall n) (n+1 \neq 0 ) </math> | :(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> | :(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}\ | + | :(N3) <math>\color{blue} (\forall n)[m:=0; \mathbf{while}\ m \neq n\ \mathbf{do}\ m:=m+1\ \mathbf{od}](m=n)</math> |
Niektóre fakty | Niektóre fakty | ||
Operacje dodawania i mnożenia są programowalne | 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ł [[Media:On-Euclids-algorithm-2018.pdf]].<br /> | |
| − | + | W wielkim skrócie:<br /> | |
| + | |||
| + | |||
| + | |||
| + | |||
| + | * '''Fakt''' Własność stopu algorytmu Euklidesa 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. | ||
== Algorytmiczny aspekt ostatniego twierdzenia Fermata == | == 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. | ||
| + | |||
| + | == Na problem Collatza == | ||
| + | |||
| + | |||
| + | The newest version<br /> | ||
| + | [[Media:DowodStopu-20-12-2018.pdf ]] | ||
| − | |||
| − | + | [22 września 2018] Poniżśze wersje planowanego artykułu, zob. poniżej, obarczone są błędem. | |
| − | + | ||
| − | < | + | Older versions<br /> |
| − | + | ||
| − | + | [[Media:Na twierdzenie Collatza 20-11-2018.pdf]]<br /> | |
| − | + | [[Media:OnCollatzTheorem14Sep2018.pdf]]<br /> | |
| + | [[Media:OnCollatzTheorem13Sep2018.pdf]] | ||
| + | [[Media:OnCollatzTheorem--12Sep2018.pdf]]<br /> | ||
| − | + | [[Media:OnCollatzTheorem12Sep2018.pdf]] | |
Aktualna wersja na dzień 20:58, 20 gru 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}\ m:=m+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.
Na problem Collatza
The newest version
Media:DowodStopu-20-12-2018.pdf
[22 września 2018] Poniżśze wersje planowanego artykułu, zob. poniżej, obarczone są błędem.
Older versions
Media:Na twierdzenie Collatza 20-11-2018.pdf
Media:OnCollatzTheorem14Sep2018.pdf
Media:OnCollatzTheorem13Sep2018.pdf
Media:OnCollatzTheorem--12Sep2018.pdf
Media:OnCollatzTheorem12Sep2018.pdf
