Collatz: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(Formuła stopu)
(Formuła stopu)
Linia 26: Linia 26:
 
==Formuła stopu==
 
==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.<br/>
 
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.<br/>
,<math> \theta:\,\left \begin{tabular}{l} \mathbf{while}\ n \neq 0 \ \mathbf{do} \\
+
,<math> \theta:\,\left\{ \begin{tabular}{l} \mathbf{while}\ n \neq 0 \ \mathbf{do} \\
 
\quad \mathbf{if}\  nieparzyste(n) \ \mathbf{then}\  n:=3n+1 \  \mathbf{else}\ n:=n/2\  \mathbf{fi} \\
 
\quad \mathbf{if}\  nieparzyste(n) \ \mathbf{then}\  n:=3n+1 \  \mathbf{else}\ n:=n/2\  \mathbf{fi} \\
\mathbf{od} \end{tabular} \right (n=1) </math>
+
\mathbf{od} \end{tabular} \right\} (n=1) </math>
 
<br />
 
<br />
 
Można też rozważać inne formuły. <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.
 
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:36, 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.

Wprowadzenie

Rozpatrzmy zdanie
dla każdej liczby naturalnej [math]n[/math], poniższy program ma obliczenie sończone

while n<> 0 do
if nieparzyste(n) then n:=3n+1 else n:=n/2 fi
od

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.
,[math] \theta:\,\left\{ \begin{tabular}{l} \mathbf{while}\ n \neq 0 \ \mathbf{do} \\ \quad \mathbf{if}\ nieparzyste(n) \ \mathbf{then}\ n:=3n+1 \ \mathbf{else}\ n:=n/2\ \mathbf{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.