Discussioni utente:Blakwolf/Info

Ultimo commento: 15 anni fa, lasciato da AlanAdler in merito all'argomento file audio

screensaver modifica

Avevo postato qui, ma ho il sospetto che sia meglio scriverti direttamente. Ciao, grazie, LellaTs 22:41, Ago 16, 2005 (CEST)
(scusa, sto ancora cercando di capire il funzionamento del tutto)

algoritmi modifica

Sull'affermazione:

"é possibile mostrare che per ogni algoritmo, esiste almeno un input per cui questo non termina"

purtroppo non conosco la teoria che tu citi, ma ho studiato macchine di Turing e tutto il resto e posso dirti con assoluta certezza che, presa letteralmente, la frase di cui sopra e' falsa. Probabilmente esiste una formulazione simile ma non identica, e le cose cambiano. Pero' posso farti 1000 esempi di algoritmi che terminano per qualsiasi input:

- bubblesort, shakersort e tutti gli altri algoritmi di ordinamento - l'algoritmo che insegnano alle medie per calcolare massimo comun divisore e minimo comune multiplo - l'algoritmo vuoto - tutti gli algoritmi classici per calcolare il fattoriale

In effetti se prendi letteralmente la frase di cui sopra, e aggiungi che per algoritmo si intende un procedimento bla bla bla che termina, se ne ricaverebbe che non esistono algoritmi.

Penso che alla base della tua frase ci sia un fraintendimento di qualche tipo, sono convinto che c'e' qualcosa di simile da qualche parte ma sono troppo arrugginito per ricordarmi!

MC

2° round modifica

Ciao, ho notato che hai eliminato la frase

  • "é possibile mostrare che per ogni algoritmo, esiste almeno un input per cui questo non termina."

Questa è una diretta derivazione del Teorema di Matiyasevich: ogni algoritmo è definibile tramite funzioni ricorsive, ogni insieme ricorsivo è diofantino, è possibile trovare in un insieme di equazioni diofantine un sistema che non ha soluzioni intere. Come mai? --BW Insultami 07:54, Set 21, 2005 (CEST)

PS: Esiste anche la corrspondente Gödelizzazione: "Corresponding to any given axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization." --BW Insultami 07:57, Set 21, 2005 (CEST)

Sei sicuro di quello che dici? Qui non si parla di algoritmi "teorici", ma algoritmi reali: si può sempre trovare un input per cui l'algorimto non termina, o perchè va in crash, o perchè esaurisce prima le risorse macchina, o perchè va in loop. Forse ti sfugge la differenza fra macchine con capacità infinita (MdT), e macchine reali. Comunque posso espandere il concetto, includendo quanto sopra. Che ne dici? --BW Insultami 11:54, Set 21, 2005 (CEST)

PS: In effetti, dato che le macchine reali non hanno capacità infinita, e la definizione di algoritmo s'intende per macchine di Turing, si, in realtà non esistono "algoritmi" nel senso ideale :) --BW Insultami 11:55, Set 21, 2005 (CEST)

Se vuoi, questo ti spiega meglio il concetto:

The conjunction of Matiyasevich's theorem with a result discovered in the 1930s implies that a solution to Hilbert's tenth problem is impossible. The result discovered in the 1930s by several logicians can be stated by saying that some recursively enumerable sets are non-recursive. In this context, a set S of integers is called "recursive" if there is an algorithm that, when given as input an integer n, returns as output a correct yes-or-no answer to the question of whether n is a member of S.

Dall'articolo su en.wiki --BW Insultami 12:06, Set 21, 2005 (CEST)

Mah, capisco la tua osservazione sulle macchine reali e teoriche, ma non concordo, viceversa, sul fatto che la voce parli di "algoritmi reali"; o meglio, questa distinzione mi pare impropria; o meglio ancora: mi pare improprio confondere l'algoritmo e la macchina. Mi spiego meglio (spero):

il motivo per cui la macchina di Turing e' a memoria infinita e' proprio perche' rappresenta il *concetto* (astratto, se vuoi) di algoritmo. Se io dico che per calcolare il MCD fra due numeri devi per prima cosa scomporli in fattori, poi prendere i fattori comuni e moltiplicarli, questo e' vero ed e' L'ALGORITMO. Va da se' che questo algoritmo richiedera' una quantita' di memoria diversa se devi calcolare l'MCD fra 4 e 8 oppure quello fra 10^10^10^10^10 e 67895^56432. Quindi, potresti non avere una macchina sufficientemente potente per applicare l'algoritmo a quei dati. Ma l'ALGORITMO, il procedimento, resta valido; si tratta di riuscire o non riuscire ad applicarlo. La Macchina di Turing ha memoria infinita proprio perche' rappresenta l'algoritmo in questa accezione "assoluta", che prescinde dai limiti fisici della macchina su cui di volta in volta esegui l'algoritmo (dopo averlo tradotto, oltretutto, in un programma).

Detto questo, e rispondendoti che si, mi sento abbastanza convinto di quello che dico, tuttavia mi sta benissimo aprire anche il discorso che tu hai in mente nella voce algoritmi, semplicemente ritengo che andrebbe contestualizzato opportunamente per far capire (se ho ben capito) che stai parlando di algoritmi in esecuzione su macchine reali e non (piu') algoritmi in senso teorico.

Allora. Il concetto che importa è questo: se tu metti come assioma che la macchina ha infinita memoria, tutto quello che ne deduci vale se, nelle ipotesi di applicazione, le macchine su cui si esegue ha memoria infinita. Se cosi non è (nè può esserlo, almeno a breve termine...), gli assiomi che (implicitamente) hai assunto non valgono: tutto il discorso è aria fritta. Per fare un parallelo, i tentativi di dimostrare il quinto postulato di euclide fallirono perchè, implicitamente, assumevano per valido un assioma equivalente: il teorema di pitagora, un criterio di uguagluianza dei triangolo, etc etc.
Gli assiomi assunti implicitamente sono brutte bestie, che invalidano il discorso senza nemmeno fartene accrogere. E applicare algoritmi validi per macchine a memoria infinita a macchine reali causa problemi.
Questo per il concetto. Veniamo a Matyiasevich. Siano A un algoritmo, ed S l'input. L'insieme dei possibili input per A sia  , ricorsivamente enumberabile per una qualche funzione f. Sia n l'ordine dell'input S in  , cioè   e dunque  . Se ora noi costruiamo f in modo che leghi ogni i risultati di ogni input S alle soluzioni di un sistema di equazioni diofantee, sappiamo che, anche se   è ricorsivamente enumerabile, non è ricorsivo: ossia che non esiste un algoritmo che possa verificare, in tempo finito, per tutti gli n, che  . Matyasevich ci dice che esiste almeno un input per cui i risultati non sono raggiungibili tramite funzioni ricorsive, ossia l'algoritmo. Convinto? --BW Insultami 13:17, Set 21, 2005 (CEST)

3° round modifica

Perdonami, ma non sono convinto. Ma siccome non riesco a seguire il tuo discorso sulle equazioni diofantee, e penso di poter spiegare le cose in modo molto + semplice, ecco un altro tentativo:

  • partiamo dal concetto che algoritmo è un termine che non ha una definizione formale. La macchina di Turing è un esempio di un modello matematico che si ritiene corrispondere al concetto di algoritmo, cosi' come il lambda-calcolo e altri.
  • una macchina di Turing ha una sua dinamica che in qualche modo puoi ricondurre anche a un computer reale, se prescindi dai dettagli (e prescindiamo!)
  • una macchina di Turing/programma funziona con un certo input, e produce un output che e' una funzione dell'input. Attenzione: proprio una funzione in senso matematico (ovviamente non tutte le funzioni possono essere realizzate da una MdT; solo quelle "ricorsive").
  • Fra le funzione ricorsive c'e' per esempio la seguente:

f(n) = 1 per qualunque n

L'algoritmo corrispondente stampa in output 1 senza neanche esaminare l'input. Come fai a trovarmi un input per cui questo programma non termina? E questo anche ammettendo (cosa che continua a sembrarmi scorretta) che vogliamo parlare di algoritmo codificato come programma in esecuzione su una macchina reale.

Se mi stai dicendo per esempio che su qualunque macchina c'e' un input che non posso dare perche' (anche in assenza di qualsiasi elaborazione) la pura e semplice lettura dell'input mette in ginocchio la macchina (ma qui secondo me il discorso diventa sempre piu' distorto e cavilloso, e inoltre non sono convinto che sia necessariamente vero che in questo caso il programma "non termina"), mi sembra che dire "per qualsiasi algoritmo esiste un input per cui l'algoritmo non termina" sia come dire "una macchina reale non e' infinita." E grazie!

Pero' voglio precisare una cosa: le cose che dici, le equazioni diofantee e tutto il resto mi sembrano molto interessanti, io mi sono permesso di cancellare quella frase perche' messa li' cosi', senza spiegazione, senza contesto, era (come minimo) tanto vera quanto falsa.

Spero che siamo d'accordo! Saluti Moongateclimber 13:37, Set 21, 2005 (CEST)

Faccio il punto: va messo che gli algoritmi sono mondi bellissimi e incantati, come i problemi di fisica: "supponiamo nullo l'attrito", e da lì in poi sono un mucchio di caz..te, perchè l'attrito c'è sempre. Sarebbe meglio e più corretto dire: "supponiamo un coefficiente di attrito inferiore a 0.01": allora sai benissimo quali sono i limiti entro cui ti puoi muovere. e su questo siamo d'accordo, credo, ossia che andrebbe detto: "Per ogni macchina con capacità di memoria e di elaborazione molto maggiori dell'input, valgono i seguenti criteri:".
Sul resto, ti rispiego la cosa,tanto le eq. diofantee sono semplici polinomi a soluzioni intere. Intanto, correggo l'affermazione in "esiste almeno un input per cui non è possibile dimostrare che termina", il che, ai fini pratici è lo stesso.
Ovviamente posso sostituire all'input lo stato della macchina, se questa non esamina l'input, il che è lo stesso: ottengo esiste uno stato della macchina per cui.....
Poichè lavoriamo su numeri interi, ossia input, è possibile associare ad ogni input un numero intero positivo, diciamo i, e quindi, detto I lo spazio dell'input,  . Giusto? È possibile fare lo stesso con l'output o, con  . Ogni possibile risultato e solo quelli sono in O. E fin qui, tutto bene. L'algoritmo, allora, non è nient'altro che una funzione ricorsiva f,  . Se I è ordinato, cosa banale, perchè basta il semplice ordine dei numeri interi positivi, allora O è ricorsivamente enumerabile, basta applicare la f, ossia l'algoritmo, agli i ordinati, per ottenere un ordine in O. Ci sei? Ora, vediamo come possiamo reinterpretare la cosa. Consideriamo dei polinomi particolari, come  , ma con qualunque numero di variabili (x,y,z) e di qualunque grado: diciamo  . Ora n, intero positivo, è soluzione di quel polinomio se g(n)=0. Queste sono le soluzioni delle equazioni diofantee. Ora, siccome prendo O è ricorsivamente enumerabile, come abbiamo visto prima, posso associare ogni o ad un'equazione diofantea g, la cui soluzione è appunto o. Chiaro? Ora, immaginiamo una funzione h che associa ogni f ad una g: la composizione   trasforma ogni input in un'equazione diofantea, il cui insieme G è ricorsivamente enumerabile, visto che lo è I. Di conseguenza lo è H, e h(i)=0 se e solo se g(o)=0. Bene, Matyiasevich ci dice che, in un insieme siffatto, esiste una h di cui non è possibile dimostrare che i è una soluzione. E dato che i genera o, esiste un output che non si può dimostrare raggiungibile da un input i. Fine dei giochi.
Questa è la conseguenza del teorema di Gödel applicato all'input degli algoritmi. La matematica è una brutta bestia, vero? --BW Insultami 08:39, Set 22, 2005 (CEST)

4° round modifica

Chettidevo dire... devo essere stordito!

Prendo il tuo ragionamento, e lo applico a un caso che ho in mente di algoritmo che termina sempre, e di cui e' possibile dimostrare che termina sempre. Si, ma quale scelgo? In effetti ritengo che sarebbe lecito per me scegliere un algoritmo con insieme degli input e/o insieme di output vuoti, ma temo che potresti obiettare che non e' un algoritmo legale, quindi torno al mio esempio, il seguente algoritmo:

INPUT N PRINT 1

I=N O={1}

Si puo' dire che un insieme di un elemento solo e' ricorsivamente numerabile? Immagino di si, e allora proseguiamo.

Ne deriva allora un insieme G di equazioni diofantee siffatto:

{x-1=0}

Mi sembra che questo rispetti la tua regola; il mio unico o e' soluzione dell'equazione.

Da qui in poi mi perdo col tuo discorso. Parli di una funzione h che associa ogni f a una g, cioe' a un polinomio diofanteo, giusto? E poi pero' mi dici h(i) = ...

Ma allora i adesso e' una funzione? Cioe' e' la nostra f di prima? Parrebbe di no, perche' poi ti appoggi al fatto che I e' ricorsivamente numerabile. Ma allora h non e' una funzione che associa a ogni f... ma e' una funzione che associa a ogni i...

Mi sembra di capire, anche da quanto dici dopo, che l'h in questione e' fatta cosi':

h(i) = g(f(i))

e quindi h(i)=0 sse g(f(i))=0

Ora immagino che per H intendi l'insiemi delle soluzioni di h(i)=0, che e' N stesso. Quindi M. dice che esiste un i per cui non e' possibile dimostrare che i e' una soluzione?

Se e' cosi', probabilmente no, ma attenzione! Se e' cosi' confermo che da qualche parte c'e' un errore nel tuo ragionamento, o un'applicazione un po' impropria di quello che dici. La nostra funzione h e':

h(i)=0 per ogni i

Dei molti modi equivalenti in cui potresti esprimere questa funzione, c'e':

i*0+1

Sei davvero convinto che esista un i per cui non puoi dimostrare che i*0+1 fa 1?

In aritmetica avresti perfettamente ragione. In una macchina di turing, purtroppo, le cose non sono così semplici.
Chiariamo subito due miei errori nella spiegazione: h = f ° g, e dunque h(i) = g(f(i)) come dici tu. l'o associato è, ovviamente, o = g(i), la cui g è appunto il polinomio.
Poi, visto che tu con l'input non fai nulla, si ricade nello stato, o se vuoi possiamo metterla così, spezzando l'algoritmo in due:
N appartiene ai numeri interi. INPUT è una funzione f tale che dato l'N d'ingresso (= i), l'output o è uno stato interno della macchina, che corrisponde alla scrittura, in memoria, del numero N. Applica a questo punto tutta la solfa, e ottieni niente altro che esiste almeno un'output, ossia uno stato interno della macchina, che non è possibile dimostrare che si raggiunga dall'input di un certo numero N. Ovviamente PRINT 1 viene dopo tutto questo, e già siamo fritti dall'INPUT. Peggio: anche PRINT è una funzione, a partire da un determinato stato della macchina di turing, quello in cui ci ha messi INPUT, quindi anche PRINT ha un suo input, lo stato, e a partire da questo scrive sul nastro l'equivalente di 1. Ora, è vero che l'unico elemento di O è 1, ma esistono infiniti input. Il teorema ci dice allora che esiste un determinato stato della macchina per cui non si può dimostrare che questa stampi 1. Chiaro?

--BW Insultami 12:37, Set 22, 2005 (CEST)


A latere rispetto a tutto questo. A mio parere la voce algoritmo dovrebbe essere incentrata sul trattamento piu' classico del tema, il che vuol dire macchine di Turing e lambda calcolo. Il famoso teorema dell'arresto di Turing dice che esiste almeno una MdT di cui non puoi essere certo che termini sempre; il teorema che citi tu e' molto piu' forte (dice che questo non si puo' dimostrare per nessuna MdT) e anche senza entrare nei dettagli sono convinto che non vale per le MdT. Significherebbe, infatti, anche che non esistono problemi decidibili, e allora andrebbe a ramengo anche tutta la teoria della complessita', addio al famoso dilemma P=NP?, perche' P e NP sarebbero entrambi insiemi vuoti, ecc ecc.

Fermo lì: il teorema dice che, anche se l'algoritmo appartiene alla classe P, esiste almeno un output che non si può dimostrare raggiungibile dagli input. Lo stesso teorema di Godel dice che esistono dei teoremi palesemente veri, ma che non possono essere dimostarti all'interno degli assiomi scelti, per qualunque numero di assiomi che comprenda almeno l'aritmetica. Non per questo non esiste l'aritmetica, non esiste più la certezza che ogni affermazione può essere dimostrata essere vera o falsa. --BW Insultami 12:37, Set 22, 2005 (CEST)

    • Ecco: per me

"é possibile mostrare che per ogni algoritmo, esiste almeno un input per cui questo non termina." è cosa assolutamente diversa da "esiste almeno un output che non si può dimostrare raggiungibile dagli input"

Con la seconda frase, anzi, penso che tu intenda: esiste almeno una coppia (i,o) di input e corrispondente output, tale che non si puo' dimostrare che l'output o e' raggiungibile da i.

Proprio "perche' l'aritmetica esiste", sono 2 cose completamente diverse. Cioe' tu vuoi dire che, sebbene sia (ovviamente) vero che l'algoritmo PRINT 1 stampa sempre 1, c'e' almeno un caso in cui non lo puoi dimostrare (a partire da un sistema di assiomi che, incidentalmente, bisognerebbe precisare; oppure il teorema potrebbe voler dire "a partire da un qualunque sistema di assiomi", qualcosa del genere, fa lo stesso). Questo e' credibilissimo, anzi mi pare molto godeliano e tutto il resto, mi va benissimo. E' pero', in un certo senso, un risultato che riguarda la logica matematica e non la teoria degli algoritmi: cioe' ha a che vedere col problema del "dimostrare", non con quello che gli algoritmi possono o non possono fare.

A maggior ragione, pero', lo vedrei allora da includere come nota di approfondimento in una voce algoritmi, e non da buttar li' al terzo capoverso. Ma anche volendo (mi raccomando, modifica la voce in tal senso), forse sarebbe opportuno mettere la frase completa e non quella originale che ho cancellato!

Moongateclimber 13:43, Set 22, 2005 (CEST)


Dunque e' assolutamente certo che quanto dici non vale per le MdT.

Assolutamente si, invece. È un teorema ce vale anche per gli insiemi numerabili ricorsivamente, che sono molti di più di quelli generabili dalle MDT. Non vale, però, nel calcolo quantistico, o per gli ipercomputer, questi ultimi puramente teorici. --BW Insultami 12:37, Set 22, 2005 (CEST)

Allora bisogna scegliere di cosa parla l'articolo. Nella mia visione, dovrebbe parlare innanzitutto di MdT, e fare una carrellata della teoria classica degli algoritmi, della complessita' ecc. ecc., ed eventualmente riportare in termini di approfondimento o link ad altre pagine teorie come quella di cui parli, correlate ma che evidentemente partono da qualche presupposto diverso (anche se non sono io a sapere quale!)

Pero' non vorrei neanche intasare wikipedia con una diatriba chilometrica. Nel caso, puoi anche scrivermi a moongateclimber@hotmail.com.

Ciao e buon lavoro (e grazie delle spiegazioni)Moongateclimber 09:37, Set 22, 2005 (CEST) MC

Figurati. Comunque quello di cui parlo io è la "moderna" teoria degli algoritmi, che ha almeno 20 anni e che nessuno si perita di insegnare in Italia. Cerca la voce hypercomputation su google... Per non parlare poi del calcolo quantistico e relativi algoritmi... Vabbè fine delle lagnanze. Fammi sapere. --BW Insultami 12:37, Set 22, 2005 (CEST)

Ogg Vorbis modifica

Ciao, ho dato una ravanata a Ogg Vorbis, rinominandolo Vorbis ed estendendolo. Sono al lavoro su un articolo su Ogg. Se ti va dai un'occhiata/revisione al tutto. Ciao. --Nosferatu 17:17, 31 dic 2005 (CET)Rispondi


file audio modifica

ciao Blackwolf :) nella voce Diete vegetariane hai scritto: "Il fabbisogno raccomandato per diete contenenti esclusivamente ferro non ematico (quello non legato all'emoglobina), essendo assorbito in maniera minore dall'organismo, è di 17mg/die per l'uomo e 33 per le donne in età fertile, e 46mg per le donne incinta". Essendo citata la fonte, ed essendo la fonte 4 file audio e piuttosto lunghi (solo il primo dura 20 minuti, accidenti!) potresti indicarmi il file esatto e il minuto esatto per verificare la citazione? Grazieee :)--AlanAdler (msg) 23:25, 17 set 2008 (CEST)Rispondi

Ritorna alla pagina utente di "Blakwolf/Info".