szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 15 sty 2015, o 11:30 
Użytkownik
Avatar użytkownika

Posty: 401
Lokalizacja: Kraków
Mam wykazać, że dodawanie jest funkcją prymitywnie rekurencyjną. Dysponuję następującymi definicjami:
f: \mathbb{N}^{k+1} \rightarrow \mathb{N} jest definiowana przez rekursję prostą, jeżeli istnieją dwie funkcje g, h takie, że g: \mathbb{N}^{k} \rightarrow \mathb{N}, h: \mathbb{N}^{k+2} \rightarrow \mathb{N} i zachodzi:
\begin{cases} f(x,0) = g(x) \\ f(x,y+1)=h(x,y,f(x,y)) \end{cases}
Klasa funkcji prymitywnie rekurencyjnych jest najmniejszą klasą funkcji zawierającą trzy funkcje inicjujące (zero, następnik i rzutowanie) i zamkniętą na złożenie i rekursję prostą).

Intuicyjnie wiem o co chodzi, ale nie mam do końca formalnego zapisu. Pokazuję schemat rekursji dla funkcji s(x,y)=x+y:
\begin{cases} s(x,0)=x \\ s(x,y+1)= S(s(x,y)) \end{cases}, gdzie S to następnik.
Nie widzę tu tylko, co jest moją funkcją g (a jeśli jest nią g(x)=x, to skąd wiemy że ona też jest funkcją prymitywnie rekurencyjną, nie widzę też funkcji h. Pomocy! :)


edit: ok, doszłam do tego że mogę przyjąć że x jest jednowymiarowym wektorem i g(x)]I^1_1(x) (rzutowanie na pierwszą współrzędną jednowymiarowego wektora). Funkcję h też udało mi się zapisać.

ale to nie koniec ;) jak poradzić sobie z czymś takim? mam funkcję f: \mathbb{N}^k ->\mathbb{N} i g(x,y) =  \sum_{i=0}^{y} f(x,i). Podobnie należy wykazać, że g jest funkcją prymitywnie rekurencyjną.
Mamy więc g(x,0)=f(x,0), a to należy do klasy funkcji p.r. z założenia - to wystarczy? Czy trzeba to jeszcze jakoś rozwinąć, używając funkcji inicjujących?
Podobnie g(x,y+1) = g(x,y) + f(x,y+1) - jeśli wiem już, że suma jest funkcją p.r., to wystarczy?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Udowodnij, że jeśli funkcje f i g są nieparzyste, to:  piwcuk  2
 Uzasadnij ze podana funkcje nie sa roznowartosciowe w swojej  Matematyk1000  1
 Wzór na funkcję malejącą do metody wyceny.  kl1  4
 funkcje odwrotne - zadanie 10  GreyLiar  8
 funkcje cyklometryczne wyprowadzenie  5er  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl