Mivel általános matematikai módszereket végülis senki sem tudot javasolni, ezért az information-junkie/google-huszár módszert alkalmaztam. Egy fél délelőtt alatt átnéztem egy csomó oldalt és nagyjából a következőkre jutottam:
- A válaszhoz talán ez az cikk jár a legközelebb. Bár az ilyen szintű matekot egyáltalán nem látom át, van egy sejtésem. Ha a linkelt oldalon a B tételben szereplő függvény valamilyen kapcsolatban áll a szám -> "collatz-sor hossza" függvénnyel és ez a kapcsolat azt jelenti, hogy nagyobb k-ra az order is nagyobb lesz (bármit is jelentsen ez) és identitás csak 1-es ordernél lehetséges akkor nem lesz több fixpont a triviálisokon kívül. :) (Ha valaki ért a felsőbb matekhoz és van egy csomó felesleges ideje ránézhet a cikkre, és kijavíthat.)
- Amennyit megértettem az alapfogalmakból és ezek alkalmazásáról, abból úgy tűnik, hogy a szokásos fixpont-konstrukciós módszerek nem alkalmazhatóak a kérdésbeli C függvényen, mert az nem monoton.
- Bizonyára a limitált előismereteimmel lehet a probléma, de néhol egymásnak ellentmondónak látszó állításokat lehet találni a wikipédiában. Egyfelől lehet ilyet olvasni: "Every lambda expression has a fixed point, and a fixed point combinator is a "function" which takes as input a lambda expression and produces as output a fixed point of that expression." (itt). De mindjárt ott van egy másik cikk, ahol pedig ezt olvashatjuk: "There can be no such function for Y, because some functions (for example, the successor function) do not have a fixed point." (itt). Van egy tippem, hogy mi lehet a megoldás (szintaxis és szemantika különbsége) de nagyon örülnék minden magyarázatnak.
- A sok böngészés közben lehet igazán érdekes dolgokat is találni. Például létezik olyan fixpont-kombinátor, amelyik alkalmazható applicative-ordert használó nyelvekben is. Míg az Y csak normal order nyelvekben használható, a belőle levezethető Z már például Pythonban is működik (itt). Ha tehát pl. így implementáltuk a C függvényünket:
def C(num): if num == 1: return 1 elif num%2 == 0: return 1+C(num/2) else: return 1+C(3*num+1)akkor a Z kombinátort
Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))és némi trükközést
col = lambda f: lambda x: (x == 1 and 1) or (x%2==0 and 1+f(x/2)) or 1+f(3*x+1)felhasználva így is megkaphatjuk C értékeit:
>>> Z(col)(13) 10Vagány, nem? :)
-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO