Wikipedysta:Wieczyk/brudnopis a

Z Wikipedii

Ta strona użytkownika jest teraz edytowana przez Wieczyk.
Prosimy nie edytować strony do czasu zniknięcia tej wiadomości. Nazwa użytkownika, który dodał tę wiadomość, jest wyświetlona na stronie historii. Jeżeli ta strona nie była edytowana od paru godzin, prosimy usunąć szablon. Założeniem tego szablonu jest zmniejszenie konfliktów edycji.

Brudnopis, kartka A.

Twierdzenie Kleene'a o punkcie stałym.

Niech $f: A \rightarrow A$ będzie funkcją ciągłą w zbiorze $(A, \leq)$ zupełnie uporzadkowanym. W tedy istnieje najmniejszy punkt stały $\mu = \sup \left\{ f(\bot)^n : n \in \mathbb{N} \right\}$ . Gdzie $\bot$ oznacza najmniejszy element w zbiorze $A$ .

Rozbuduję i poprawię definicję --wieczyk (dyskusja) 22:42, 23 kwi 2008 (CEST)

[edytuj] Dowód

Napiszę i skomentuję dowód --wieczyk (dyskusja) 22:42, 23 kwi 2008 (CEST)

[edytuj] Zastosowanie

Znam jedynie powierzchownie wykorzystanie w informatyce, nie znam się na teorii rekursji --wieczyk (dyskusja) 22:42, 23 kwi 2008 (CEST)

[edytuj] Informatyka

W informatyce twierdzenie Kleene'a ma zasadnicze znaczenie przy badaniu funkcji częściowych oraz wyznaczaniu znaczenia definicji, w których używa się równań rekurencyjnych.

Klasycznym przykładem jest silnia: Niech dany będzie zbiór funkcji częściowych z liczb naturalnych w liczby naturalne uporządkowanych przez relację zawierania $A = ( \mathbb{N}^{\subseteq \mathbb{N}}, \subseteq)$ oraz funkcjonał (będący funkcją ciągłą) na tym zbiorze $\varphi: A \rightarrow A$ .

$\varphi(f)(n) = \begin{cases} 1 & : n = 0\\ n \cdot f(n-1) & : n > 0 \wedge (n-1) \in \mbox{Dom}(f) \end{cases}$

Omówię tego sens --wieczyk (dyskusja) 22:42, 23 kwi 2008 (CEST)

...

Jak powstaje punkt stały funkcjonału $\varphi$ - tzn jak powstaje silnia.

$\varphi^0(\bot)(n) = \mbox{id}$

Gdzie id to funkcja identyczności (złożenie dowolnej funkcji "zero razy" ze sobą jest funkcją identyczności).

Elementem najmniejszym w zbiorze $A$ , jak i dowolnym podzbiorze skierowanym tego zbioru, jest zbiór pusty $\bot = \emptyset$ , jest więc to funkcja pusta (posiadająca pustą dziedzinę).

Zgodnie z definicją funkcjonału, dla $f = \bot$ jest on funkcją częściową z tylko jednym elementem w dziedzienie.

$\varphi(\bot)(n) = \begin{cases} 1 & : n = 0\\ \mbox{nieokreslona} & : \mbox{p.p} \end{cases}$

...

Skometuję jak buduję się silnia --wieczyk (dyskusja) 22:42, 23 kwi 2008 (CEST)

$\varphi^2(\bot)(n) = \varphi(\varphi(\bot))(n) = \begin{cases} 1 & : n = 0\\ 1 & : n = 1\\ \mbox{nieokreslona} & : \mbox{p.p} \end{cases}$

$\varphi^3(\bot)(n) = \varphi(\varphi^2(\bot))(n) = \varphi(\varphi(\varphi(\bot)))(n) = \begin{cases} 1 & : n = 0\\ 1 & : n = 1\\ 2 & : n = 2\\ \mbox{nieokreslona} & : \mbox{p.p} \end{cases}$