Collatz: Różnice pomiędzy wersjami
| Linia 24: | Linia 24: | ||
W standardowej strukturze liczb naturalnych z operacją dodawania | W standardowej strukturze liczb naturalnych z operacją dodawania | ||
nasz program ma obliczenie skończone, dla każdego argumentu ''n''.. | nasz program ma obliczenie skończone, dla każdego argumentu ''n''.. | ||
| − | + | ==Formuła stopu== | |
| + | Należy zatem sformułować formułę ,math>\theta</math> (wyrażenie logiczne) taką, że przyjmuje ona wrtośc prawda wtedy i tylko wtedy gdy obliczenie programu <math>Cl</math> jest skończone. Takich formuł jest wiele w języku urachunku programów, tj. logiki algorytmicznej.<be/> | ||
| + | ,math> \theta:\,\left \begin{tabular}{l} \mathbf{while}\ n<> 0 \ \mathbf{do} \\ | ||
| + | \quad \mathbf{if}\ nieparzyste(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbff{fi} \\ | ||
| + | \mathbf{od} \end{tabular} \right (n=1) </math> | ||
<br /> | <br /> | ||
| + | Można też rozważać inne formuły. <br/> | ||
| + | Druga część zadania jest znacznie trudniejsza: przeprowadzić dowód formuły stopu posiłkując się aksjomatami rachunku programów i aksjomatami algorytmicznej teorii liczb naturalnych. | ||
Wersja z 12:27, 8 wrz 2021
Nareszcie!
Praca nad problemem trwała 83 lata.
Udało się zmienić statut z hipoteza Collatza na twierdzenie Collatza.
Argumenty znajdziesz tu.
Spis treści
Wprowadzenie
Rozpatrzmy zdanie
dla każdej liczby naturalnej [math]n[/math], poniższy program ma obliczenie sończone
Zaczynamy od uwagi, że prawdziwośc powyższego zdania pociaga za sobą prawdzowość tezy Collatza. Ale w r.1937 nie istniały komputery ani języki programowania.
Spostrzeżenie z r. 2004
- algorytm nie potrzebuje operacji mnożenia,
- w strukturze algebraicznej, która jest niestandardowym modelem elementarnej teorii dodawania liczb naturalnychnasz algorytm ma obliczenie nieskończone.
- Tezy Collatza nie można udowodnić na podstawie aksjomatów elementarnej teorii dodawania liczb naturalnych.
Poprawiamy sformułowanie tezy
W standardowej strukturze liczb naturalnych z operacją dodawania nasz program ma obliczenie skończone, dla każdego argumentu n..
Formuła stopu
Należy zatem sformułować formułę ,math>\theta</math> (wyrażenie logiczne) taką, że przyjmuje ona wrtośc prawda wtedy i tylko wtedy gdy obliczenie programu [math]Cl[/math] jest skończone. Takich formuł jest wiele w języku urachunku programów, tj. logiki algorytmicznej.<be/>
,math> \theta:\,\left \begin{tabular}{l} \mathbf{while}\ n<> 0 \ \mathbf{do} \\
\quad \mathbf{if}\ nieparzyste(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbff{fi} \\
\mathbf{od} \end{tabular} \right (n=1) </math>
Można też rozważać inne formuły.
Druga część zadania jest znacznie trudniejsza: przeprowadzić dowód formuły stopu posiłkując się aksjomatami rachunku programów i aksjomatami algorytmicznej teorii liczb naturalnych.
