Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(→‎Algorytm Euklidesa)
(→‎Problem Collatza)
Linia 37: Linia 37:
 
Oba te fakty sa konsekwencją ostatniego twierdzenia Fermata.
 
Oba te fakty sa konsekwencją ostatniego twierdzenia Fermata.
  
−
== Problem Collatza ==
+
== Przyczynki do problemu 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)\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>
+
:<math>(\forall n)\left \{ \begin{array}{l} \mathbf{while}\ n\neq 1\ \mathbf{do}\\ \quad \mathbf{if}\ n\ is\ odd \quad \mathbf{then}   n \leftarrow 3*n+1 \mathbf{else} n\leftarrow 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.<br />
  
−
<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.
 
Istnieje obszerna literatura tego zagadnienia. Ustanowiono nagrodę pieniężną za rozwiązanie problemu.
  
Linia 50: Linia 51:
  
 
'''Hipoteza''' W algorytmicznej teorii liczb naturalnych z dodawaniem (bez mnożenia) powyższa formuła algorytmiczna posiada dowód.<br />
 
'''Hipoteza''' W algorytmicznej teorii liczb naturalnych z dodawaniem (bez mnożenia) powyższa formuła algorytmiczna posiada dowód.<br />
−
Dla przeprowadzenia dowodu wystarczy udowodnienie innej hipotezy:<br />
+
   
−
'''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 < n)  </math><br />
+
−
 
+
−
'''Hipoteza''' Dla każdej liczby naturalnej <math>n</math> istnieje liczba naturalna <math>k</math> taka, że
+
−
<math>(\forall n)(\exists k)(y=n;\, (    \mathbf{if }\ y\ is\ \mathrm{odd} \    \mathbf{ then } \ y := 3*y+1 \  \mathbf{ else } \  y:= y \div 2  \  \mathbf{ fi})^k) (y < n)  </math><br />
+
−
 
+
−
 
+
−
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.
 
'''Fakt''' Jeśli hipoteza Collatza jest prawdziwa to istnieje dowód w algorytmicznej teorii liczb naturalnych.

Wersja z 12:10, 30 lip 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}\ n:=n+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.

Przyczynki do problemu 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} n \leftarrow 3*n+1 \mathbf{else} n\leftarrow 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.



Fakt Jeśli hipoteza Collatza jest prawdziwa to istnieje dowód w algorytmicznej teorii liczb naturalnych.

Źródło „http://lem12.uksw.edu.pl/index.php?title=Arytmetyka_Algorytmiczna&oldid=2507”