Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(→‎Problem Collatza)
(→‎Na problem Collatza)
 
(Nie pokazano 64 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 4: Linia 4:
 
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  
 
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{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{ 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
 
:- <math> \mathcal{A}</math> jest to zbiór złożony z trzech formuł wyliczonych poniżej
Linia 13: 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}\ n:=n+1\ \mathbf{od}](m=n)</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
 
Niektóre fakty
  
 
Operacje dodawania i mnożenia są programowalne  
 
Operacje dodawania i mnożenia są programowalne  
  
−
== [[Algorytm Euklidesa]] ==  
+
== Algorytm Euklidesa ==  
−
* '''Fakt''' Jego własność stop nie wynika z aksjomatów Peano, ponieważ algorytm zapętla się w [[Niestandardowy model liczb naturalnych|modelu (niestandardowym) arytmetyki liczb naturalnych z dodawaniem]].
+
Jesteśmy szczęśliwi mogąc przedstawić nowy dowód poprawności algorytmu Euklidesa.<br />
−
* '''Twierdzenie''' Formuła stopu algorytmu Euklidesa jest twierdzeniem arytmetyki algorytmicznej.
+
Zob. poniższy artykuł [[Media:On-Euclids-algorithm-2018.pdf]].<br />
  
−
: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]].
+
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 ==
Linia 31: Linia 37:
 
Oba te fakty sa konsekwencją ostatniego twierdzenia Fermata.
 
Oba te fakty sa konsekwencją ostatniego twierdzenia Fermata.
  
−
== Problem Collatza ==
+
== Na problem Collatza ==
 +
 
 +
 
 +
The newest version<br />
 +
[[Media:DowodStopu-20-12-2018.pdf ]]
 +
 
  
−
L. Collatz sformułował swoją hipotezę w r. 1937, do dzisiaj nie znamy dowodu tej tezy ani kontrprzykladu.  
+
[22 września 2018] Poniżśze  wersje planowanego artykułu, zob. poniżej, obarczone są błędem.  
−
:<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.
+
Older versions<br />
−
Istnieje obszerna literatura tego zagadnienia. Ustanowiono nagrodę pieniężną za rozwiązanie problemu.
+
  
−
Spostrzeżenie
+
[[Media:Na twierdzenie Collatza 20-11-2018.pdf]]<br />
  
−
'''Fakt''' W modelu niestandardowym arytmetyki liczb naturalnych z dodawaniem algorytm Collatza ma obliczenia nieskończone.
+
[[Media:OnCollatzTheorem14Sep2018.pdf]]<br />
  
−
'''Fakt''' W algorytmicznej teorii liczb naturalnych z dodawaniem (bez mnozenia) powyższa formuła algorytmiczna nie ma dowodu.
+
[[Media:OnCollatzTheorem13Sep2018.pdf]]
−
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:
+
−
<math>\forall n s(n)\neq 0 <\math>
+
  
 +
[[Media:OnCollatzTheorem--12Sep2018.pdf]]<br />
  
−
'''Fakt''' Jeśli hipoteza Collatza jest prawdziwa to istnieje dowód w algorytmicznej teorii liczb naturalnych.
+
[[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:



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
Źródło „http://lem12.uksw.edu.pl/index.php?title=Arytmetyka_Algorytmiczna&oldid=2675”