Sign in or Join FriendFeed
FriendFeed is the easiest way to share online. Learn more »
Non sono Bob
Non sono Bob
"qualsiasi algoritmo deve possedere un numero di regole finite" colleghi a me. (a me pare proprio di no, ma non mi viene in mente nessun esempio descrivibilile)
June 3, 2012 - Comments disabled - Share
è per definizione. - Heart Attack
la definizione mi pare parli di numero finito di passi, non di regole. - eslr
@Bob per regola intendi la cosa che dato lo stato di esecuzione dell'algoritmo ti dice quale è il prossimo passo, giusto? - eslr
La macchina a stati finiti che definisce il linguaggio ha, appunto, stati finiti (il "linguaggio macchina"). Non ricordo se c'era una regola simile anche per il programma. - Non sono Bob
Poi, chiaramente, un programma che termina non mandererà in esecuzione tutte le regole citate. - Non sono Bob
è possibile selezionare regole infinite con un algoritmo più efficiente di O(n)? - Heart Attack
Quello mi pare un altro problema (scrivere quel programma) - Non sono Bob
il punto è che se in un determinato passo del sistema, le possibili regole applicate sono infinite, lo è anche il tempo necessario per selezionare le regole, pertanto il problema oggetto dell'algoritmo non viene risolto e pertanto non è un algoritmo ;-) - Heart Attack
No, ammesso che io abbia capito la tesi. Esempio banale, che però non mi pare risponda in modo interessante alla mia domanda: 1) print "Ciao" 2) halt 3) ... +inf) altri statement a caso - Non sono Bob
In termini più generali: il fatto che le regole siano infinite[1] non implica che il tempo di computazione sia sempre infinito. - Non sono Bob
[1] non mi pare che - Non sono Bob
un algoritmo è una sequenza di passi finita che ha lo scopo di risolvere un problema. Se ad un determinato passaggio del percorso per arrivare alla soluzione, il tempo di esecuzione di quel passaggio è infinito, il problema non arriva mai a soluzione. Ergo quell'algoritmo non risolve il problema. - Heart Attack
Altro esempio: nel costruire una frase in una lingua naturale ho una funzione succ(frase parziale) che produce la prossima parola, le regole per calcolarla sono infinite, solo che io ogni volta prendo la prima, o le prime n, che hanno a che fare con il contesto dato ignorando le altre. - Non sono Bob
pare che la definizione di algoritmo non sia una cosa così banale: http://en.wikipedia.org/wiki... - zar
HA: Secondo me stai confondendo il numero di passi necessari, la complessità, con la grandezza del programma. - Non sono Bob
@Bob.Draco: perdonami, ma se puoi metterle in un qualche ordine, non sono infinite. - Heart Attack
HA: eh? - Non sono Bob
Vedi alla voce: assioma della scelta. (o più banalmente insieme numerabile) - Non sono Bob
ma se il problema è infinito? vedi crivello di eratostene - braciola
Eratostene risolve il problema, in tempo finito, "trova l'ennesimo numero primo" non "trova tutti i numeri primi". Sono due cose diverse. - Non sono Bob
(io non ne capisco una fava di sta roba ma un programma ad istruzioni finite che continua fino all'infinito c'è) - braciola
(il problema era l'inverso :) ) - Non sono Bob
( ahahahahah, scusa ho ancora troppa sugna in circolo ) - braciola
@Bob.Draco: sei tu che fai confusione, ritenendo che le regole per la formulazione del linguaggio siano infinite, ma numero molto grande != infinito ;-) - Heart Attack
E ALLORA UN ALGORITMO FINITO PER SCRIVERE UN ALGORIMO INFINITO??? EH? - braciola
HA: Sinceramente non so di che stai parlando. - Non sono Bob
E LE FOIBE? - braciola
@Bob.Draco: non puoi scrivere un algoritmo in passi finiti per ordinare un insieme infinito. - Heart Attack
(comunque 'mo mi leggo il link di @zar) - Non sono Bob
(chiaramente non puoi ordinarlo tutto, in tempo finito, ma puoi stabilire quali sono i primi n, finiti, elementi) - Non sono Bob
@Bob.Draco: hai scritto "nel costruire una frase in una lingua naturale ho una funzione succ(frase parziale) che produce la prossima parola, le regole per calcolarla sono infinite" <= NO, non sono infinite. - Heart Attack
Era una definizione, un esempio... - Non sono Bob
@Bob.Draco: se l'insieme è numerabile, vuol dire che ha un ordine precostituito, ma le regole linguistiche non sono numerabili. - Heart Attack
"Posto che siano infinite, allora..." - Non sono Bob
Bella ipotesi, andrebbe dimostrata però. - Non sono Bob
(se sono finite sono numerabili per forza, se sono infinite dipende) - Non sono Bob
Se le regole fossero numerabili, avrebbero lo stesso ordine indipendentemente dal valore di "frase parziale". - Heart Attack
Ah, fra l'altro "se l'insieme è numerabile, vuol dire che ha un ordine precostituito" è banalmente falso, ammesso che io abbia capito cosa intendi con "precostituito". - Non sono Bob
HA: dimostrazione? - Non sono Bob
se è numerabile, deve rispondere ad uno o più criteri di ordinamento. Se i criteri di ordinamento fossero infiniti, saremmo al punto di partenza: l'insieme dei criteri di ordinamento non è ordinabile in un tempo finito, etc. - Heart Attack
Gli insiemi finiti possono essere ordinati in n! modi, gli insiemi infiniti in infiniti modi. Non capisco il problema. - Non sono Bob
inoltre, se l'insieme di regole è numerabile, vuol dire che esiste una correlazione tra la regola ed un valore ed in tal caso non si tratterebbe di una regola, ma di un dato. - Heart Attack
('mo ti cerco la paginetta adatta, se hai pazienza un secondo) - Non sono Bob
io ho pazienza se ne hai altrettanta, dovermi sbattere a dimostrare 'sta roba senza un minimo di aiuto da parte tua è una gran rottura di cazzi ;-) - Heart Attack
Eh? (la "correlazione tra una regola e un valore" è una possibile definizione, informale, di algoritmo) - Non sono Bob
facendo un salto un attimo nel mondo della teoria degli insiemi, gli assiomi di Zermelo-Fraenkel sono infiniti (uno di essi è uno schema di assiomi, cioè un insieme infinito di assiomi che funzionano tutti secondo una certa regola, ma dal punto di vista logico sono infiniti). Non so se può aiutare... http://it.wikipedia.org/wiki... - zar
HA: Va be', fa gnente, non importa. :) - Non sono Bob
@zar ohhh, sì credo di sì. - Non sono Bob
@zar: hai detto giusto: "una certa regola" La regola non include il dato. È come se dicessi "l'algoritmo per risolvere una somma include infinite regole: la regola per aggiungere 1, la regola per aggiungere 2, la regola per aggiungere 3, etc." <= NOAOAOAOA. - Heart Attack
se si trattasse di regole non logicamente correlate tra di loro, il tempo per trovare la regola n sarebbe O(n) e quindi potenzialmente infinito, per insiemi di regole infinite. "la regola per aggiungere 1", "la regola per aggiungere 2" e tutto ciò che segue, sono logicamente correlate da una funzione unica, quindi sono l'espressione di un'unica regola, finita. - Heart Attack
Ok, grazie a HA ho trovato l'esempio che cercavo. Descrivo estensivamente succ(n), in termini più prosaici scrivo la tabella infinita che associa un numero al suo successore, e la uso per computare succ(n). Il programma termina sempre, dovrebbe essere facile dimostrarlo, ha complessità n, ma ha infinite linee di programma. - Non sono Bob
non ha infinite linee di programma. ha 1 linea di programma. - Heart Attack
in un linguaggio di programmazione usuale sarebbe qualcosa del tipo: if (n== 1) return 2 else if (n==2) return 3 else... - Non sono Bob
confondi i dati con le regole. Prendi la macchina di turing: il nastro magnetico può essere infinito, ma le regole del sistema sono finite. - Heart Attack
<<La macchina a stati finiti che definisce il linguaggio ha, appunto, stati finiti (il "linguaggio macchina"). Non ricordo se c'era una regola simile anche per il programma.>> quarto commento. - Non sono Bob
se ha infinite linee di programma, non è un algoritmo: hai infiniti "else if", ergo infiniti passaggi. - Heart Attack
l'algoritmo per calcolare il successore è f(x) = x +1 - Heart Attack
HA: ti lascio rileggere con calma, ciao. - Non sono Bob
potresti considerare switch(x), che ha un solo passaggio O(1), ma il numero di scelte dovrebbe essere finito. - Heart Attack
@Bob.Draco: confondi il programma con i dati. Il programma della macchina a stati finiti legge il nastro, il nastro non è parte del programma. - Heart Attack
fammi un esempio di algoritmo con infinite regole e poi ne parliamo. - .mau. from m.ctor.org
ESEMPIO COMPLETO. :> - Heart Attack
@.mau. : be', sopra ne ho descritto uno, non va bene? :) - Non sono Bob
@Bob.Draco: non è un algoritmo. - Heart Attack
non lo so se in astratto può esistere un algoritmo con regole infinite, verrebbe da chiedersi a cosa serve, però. nel caso dei linguaggi, ad esempio, è chiaro che se vogliamo che un linguaggio sia apprendibile deve consistere in un insieme di regole finite (le quali danno luogo a un insieme potenzialmente infinito di enunciati, ma è un altro discorso) - thomas morton ☢
il tuo succ(n) esplicitato? Non è un algoritmo, perché devi prima definire tutti gli infiniti numeri (oppure scrivere una regola che crei il successore, ma allora non è più infinita ) - .mau. from m.ctor.org
(seguo) - massimiliano l. from Android
@.mau. Ovvero stai dicendo che non può essere scritto, in tempo finito. Se esistesse, non in potenza ma in atto, sarebbe un algoritmo e terminerebbe per ogni input. - Non sono Bob
@Bob.Draco: no, perché ciascuna "else if" implica una nuova istruzione, perciò O(n) tempo di esecuzione: a regole infinite corrisponde tempo infinito di esecuzione. - Heart Attack
HA: non hai capito, fidati. - Non sono Bob
bob, mi stai diventando teista. Come scegli il successore? Fai un lookup in una tabella infinita? - .mau. from m.ctor.org
il problema è che non ha capito nessuno - thomas morton ☢
mi sento meno solo :-) - Heart Attack
(cancellato, non avevo capito io a 'sto giro, ci penso) - Non sono Bob
E' un "algoritmo" diverso dal mio e non è una dimostrazione. - Non sono Bob
(ho l'impressione che queste cose vengano studiate, ho anche l'impressione, più forte, che vadano oltre la mia capacità di comprensione http://www.springerlink.com/content... ) - Non sono Bob
http://phil.gu.se/logic... questo le chiama ISIT-machines - Non sono Bob
mi sa che stiamo parlando di sesso degli angeli - thomas morton ☢
O di antani? - Non sono Bob
(finisco il gin lemon, leggo domani) - Ivan Crema
"infinitary" non è propriamente "infinite". Ribadisco comunque che se sei un Essere Supremo, o almeno uno infinito, allora puoi avere un "algoritmo infinito"; ma non è lo stesso tipo di algoritmo che usiamo noi. - .mau.
ma anche down - m.fisk from m.ctor.org
un gin lemon per favore (mi associo a quelli che non hanno capito un cazzo, o nello specifico la distizione tra passi dell'algoritmo e regole. regole de che?) - Angelo
va be', rifo e chiarisco va. - Non sono Bob