Katerina89 ha scritto:
perdippiu' se qlc1 vuole provarci puo' provare a dimostrare quella cosa del for (che la *, insomma quella * strana, non si puo' fare col ciclo for e l'if soltanto)
il profe dice che e' un teorema vecchio e l'hanno dimostrato prima ancora che esistessero i compiuter, chissa' poi perche'?
Cia' e' raga!!!!11
Io ci provo...
Vogliamo far vedere che la funzione x*y cresce troppo velocemente perchè si possa fare col for. Allora un punto di partenza potrebbe essere definire "velocemente".
Sia A l'insieme delle funzioni crescenti da N in N.
Se $ ~ f,g \in A $, allora dico che f è veloce almeno quanto g, e scrivo $ ~ f \succeq g $, se esistono k,n naturali tali che per ogni x>n si ha $ ~ f^k(x) \ge g(x) $. (f^k è la composizione di f k volte)
Questa relazione è riflessiva e transitiva, e quindi considerando due funzioni equivalenti se $ ~ f \succeq g \land g \succeq f $, otteniamo una relazione d'ordine sulle classi di equivalenza.
O meglio, definiamo $ ~ f \succ g $ se $ ~ f \succeq g $ ma non è vero che $ g \succeq f $.
Lemma -1: se $ ~ f(x) \ge g(x) $ per ogni x sufficientemente grande, allora $ ~ f \succ g $.
Proof: ovvio, k=1
Lemmino 0: data $ ~ f \in A $, sia $ ~ g(x) = f^x(x) $ un'altra funzione, ancora crescente. Allora $ ~ g \succ f $.
Questo perchè, per ogni k, per ogni x>k, si ha $ ~ g(x) = f^x(x) > f^k(x) $, quindi è impossibile che $ f \succeq g $, il viceversa è ovvio per il lemma -1, oppure ovvio e basta.
Lemma 1: se $ ~ f \succeq g $ e $ ~f \succeq h $ allora $ f \succeq g \circ h $. Lasciamolo al lettore
Ora torniamo ai nostri programmi. Sia $ ~ f \in A $, e sia g una funzione calcolata da un programma in cui sono permesse le seguenti istruzioni:
- l'uso di una qualsiasi funzione $ ~ h \in A $ tale che $ ~ f \succeq h $
- if, se proprio volete
- il for è
assolutamente vietato
Vogliamo dimostrare che $ ~ f \succeq g $.
Come si fa? Poichè il for è vietato, il programma avrà un numero (fortunatamente finito) di linee, e ciascuna sarà eseguita al più una volta.
Gli if dimentichiamoceli pure, e vediamo che in ogni linea utile del programma avremo qualcosa del tipo:
variabile da qualche parte in memoria = composizione di funzioni veloci al più tanto quanto f, usando come valori quello che ho già in memoria.
Da questo, applicando tante volte il lemma 1, segue la tesi.
Ora, per quello che mi serve, il lemmino 0 è troppo debole.
Quindi mi invento il lemma 2, che è più forte del lemma 0:
Sia $ ~ f \in A $ una funzione tale che per un certo n si abbia f(n) > n+1.
Allora $ ~ f^x(0) \succ f(x) $.
Dimostrazione: per ogni k naturale, da un certo x in poi avremo $ ~ f^{x-k}(0) > x $. Questo perchè è crescente, e da un certo punto in poi $ ~ f(x) \ge x+2 $, aumenta di 2 alla volta, mentre x aumenta di 1, quindi riesce a recuperare il k che gli manca.
Ora avremo finalmente che: $ ~ f^x(0) = f^k(f^{x-k}(0)) > f^k(x) $.
Ora finalmente siamo abbastanza vicini alla fine.
Per ogni k, sia $ ~ f_k(x) = k * x $ con la * protagonista della discussione.
Per il lemma 2 (più o meno eh), avremo che $ ~ f_{k+1} \succ f_k $ per k>0.
Quindi, se vogliamo scrivere un programma per calcolare $ ~ f_{k+1} $ con a disposizione solo istruzioni per $ ~ f_i, i \le k $, ci servirà
almeno un for.
Se supponiamo che il linguaggio di programmazione abbia solo a disposizione un'istruzione per incrementare una variabile, per scrivere $ ~ f_{k+1} $ servono almeno k for!
Ora, supponiamo che esista un programma che calcola x*y. Allora esiste un programma che calcola la funzione crescente c(x) = x*x, no?
Dimostriamo che $ ~ c \succ f_k $ per ogni k. Ma questo è un corollario del lemma. Quale lemma? Questo, il lemma 3:
Sia $ ~ \{g_i\}_{i \in \mathbb{N}} $ una catena di funzioni crescenti N->N tali che $ ~ i > j \Rightarrow g_i \succ g_j $. Allora, detta $ ~ G(x) = g_x(x) $, si ha $ ~ G \succ g_n $ per ogni n.
Dimostrazione: per x>n avremo $ ~ G(x) \ge g_{n+1}(x) $ quindi per il lemma -1, $ ~ G \succeq g_{n+1} $, aggiungi che $ ~ g_{n+1} \succ g_n $, per la prop. transitiva, $ ~ G \succ g_n $.
Ora è finita: supponiamo che esista un programma con i for che calcola c. Diciamo che ha n for. Ma questo implica che è impossibile che $ ~ c \succ f_{k+1} $, assurdo perchè $ ~ c \succ f_k $ per ogni k.
Argh che casino che ho scritto
speriamo ci sia qualcosa di sensato.
Avrei qualche domanda, che però si basa sul fatto che ci sia qualcosa di sensato, che è un'ipotesi davvero troppo forte
- l'ordinamento che ho definito ha catene discendenti infinite?
