Dyskusja:Funkcja rekurencyjna: Różnice pomiędzy wersjami

S(m) ?
(proszę przemyslec...)
(S(m) ?)
Co oznacza S(m) ? Nie ma definicji S(.) i m ? Jestem laikiem.
--[[Specjalna:Wkład/212.76.37.154|212.76.37.154]] ([[Dyskusja wikipedysty:212.76.37.154|dyskusja]]) 02:08, 19 lis 2009 (CET)
 
 
Operacja minimum musi byc albo na funkcjach efektywnych albo musi byc to minimum ograniczone. Nie ma obliczalnej funkcji minimum. Jeśli mamy dowolna funkcję F to nei wiemy czy mozna obliczyc takie y że F(X,y)=0. Skoro nie ma tego warunkui to być może to jest nieobliczalne!!! Brak tego warunku prowadziłby do sprzeczności np. z twierdzeniem o istnieniu funkcji uniwersalnych: gdyby operacja minimum nieograniczonego należała do definicji funkcji rekurencyjnych istniałaby taka funkcja rekurencyjna G(p,X) której wartości dla odpowiednich p byłyby równe wartościom dowolnej wybranej funkcji rekurencyjnej f: Ep AX G(p,X)=f(X) gdzie Ep oznacza "istnieje takie p ze", zas Ax oznacza "dla kazdego X". Istnienie takiej funkcji rekurencyjnej byłoby zatem równoważne twierdzeniu, ze każda funkcja rekurencyjna jest szczególnym przypadkiem pewnej określonej i danej funkcji G(p,X). Skoro operacja minimum nieograniczonego mogłaby być uzyta w jej definicji to G(p,X) byłaby rekurencyjna a co za tym idzie każda relacja rekurencyjna ( reprezentowana przez dowolna funkcje rekurencyjną) byłaby rekurencyjnie wyliczalna i nawet rekurencyjnie prosta. Prowadzio by to do m. in. do rozwiazani aproblemu stopu ( skoro wszystko mozna wyliczyć?). [[Wikipedysta:Kakaz|kakaz]]
Anonimowy użytkownik