Arytmetyka Algorytmiczna: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
Linia 1: Linia 1:
 
Jest to ''zalążek'' dłuższego tekstu.
 
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
 +
:- <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
 
algorytmicznej teorii liczb naturalnych:
 
algorytmicznej teorii liczb naturalnych:

Wersja z 17:38, 21 lut 2013

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
- [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

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.

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.

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

Fakt 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.