Newsgroup: it.scienza.informatica
Titolo: Ha senso parlare del programma piu' "corto" con un output assegnato?

Ciao a tutti,
scusate se la domanda e' scritta male, ma sono un matematico...
Dato un linguaggio di programmazione "codificato"
(per esempio C o Fortran), ha senso chiedersi qual e'
il programma piu' "corto" che produce come output
le prime 10000 cifre di pi greco? Se si', ci sono
dei metodi che permettono effettivamente di trovarli?
Grazie,
Ale
--
Alessandro Russo, IAN-CNR Pavia
-------------------------------
"- Domando scusa - replico' Pinocchio -
sono un malandrino anch'io."

 wrote:
: Dato un linguaggio di programmazione "codificato"
: (per esempio C o Fortran), ha senso chiedersi qual e'
: il programma piu' "corto" che produce come output
: le prime 10000 cifre di pi greco? 
Dipende da cosa intendi per "avere senso".
Visto che esiste un programma che produce come output le prime 1000
cifre di \pi (basta prendere uno sviluppo in serie di cui sai stimare
l'errore, in modo di sapere quando fermarti) e visto che e` possibile dare
un ordinamento totale dei programmi in base alla loro lunghezza in byte,
non vedo problemi.
: Se si', ci sono
: dei metodi che permettono effettivamente di trovarli?
Non credo.
stammi bene, .mau.

 dei metodi che permettono effettivamente di trovarli?
Mi pare che vi sia qualche cosa chiamata "complessità di kolmogorow" o
qualche cosa del genere...
A quest'ora non posso ricordare i nomi assurdi. :-)
Comunque resta valido l'assunto che il programma fatto così:
void main (void){
printf ("3.14.....");    /* Metti tu le prime mille cifre tra apici */
}
Può essere un buon candidato come "programma più corto".
Il mio piccolissimo contributo l'ho dato?
--
Alessandro Monti

Alessandro Monti wrote:

Certo hai ragione, pero' esistera' un N critico per cui se n>N e' piu'
"corto"
il programma che genera le n cifre con un algoritmo del programma
che le stampa direttamente. Mi chiedo: c'e' un modo di trovare questo n
o e' una domanda assurda?


 o e' una domanda assurda?
Cioè vuoi sapere se dipende dal problema o se vi è un modo (semi)-automatico
per trovare questo N?
Mi vuoi davvero fare andare a guardare come si chiama quel tizio...
Ho un'idea migliore, se vuoi: questo è un tema da it.comp.ia
Ne vuoi discutere lì? In quel NG vi è gente più preparata di me, senza
dubbio.
Però tieni presente che vi sono degli aspetti di cui discutere. Prendi il
seguente programma:
void main(void){
char a;
while (a = getch() != EOF)
    putch (a);
}
(perdona eventuali errori)
Il programma è cortissimo, eppure "genera" ogni possibile stringa: basta
passargliela tramite lo standard input!!!
Ovvero: tu vorresti (credo) astrarre dalle dimensioni di tempo e di dati, in
modo da avere una "complessità algoritmica" di un qualche tipo astratto,
dipendente da una astratta "complessità del risultato cercato".
Ora, penso concorderai che qualunque problema, una volta nota la soluzione,
diventa banale. O no?
Di conseguenza, qualunque problema, una volta risolto, dovrebbe avere una
complessità pressochè nulla!
Se invece non l'hai risolto, devi scontrarti anche con le complessità in
termini di spazio (dei dati) e di tempo (per l'elaborazione). Ricorda un po'
le macchine di Turing, vero?
Allora potresti contare il numero di stati necessari ad una MdT che risolva
il problema. Meglio ancora: il numero di stati della MdT più piccola che
risolva il problema. Concordi?
Beh, ancora una volta, la MdT con il minor numero di stati che produce in
output una stringa arbitraria, è probabilmente quella MdT che deve solo
copiare l'input sull'output! :-)
Forse il punto è sul capire cosa vuole dire "produrre un output" e
"risolvere un problema", altrimenti per quanto ci giri intorno, torni sempre
al punto di partenza...
Al momento potrei darti la mia opinione, ma dato che sei un matematico,
immagino che questa non potrebbe soddisfarti, meglio parlare di teoremi.
Purtroppo l'argomento è stato solo sfiorato dal mio piano di studi, il che
vuole dire che ho delle dispense, sfogliate ma non lette, sull'argomento. In
parole povere: ho letto quelle dispense quel tanto che bastava per:
- ricordare un nome "strano", ma non sono sicuro di come si scriva
- capire che non mi serviva studiarmele per il lavoro che avevo in corso (la
tesi)
- metterle da qualche parte per improbabili usi futuri
....
Spiacente del poco aiuto, ma resto a disposizione. Se insisti, finirò per
farmi convincere a leggere quei fogli... :-)
Ciao
--
Alessandro Monti

dei metodi che permettono effettivamente di trovarli?
Si', data un'opportuna definizione di "corto". 
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun

Salve
non credo abbia molto senso parlare di lunghezza di un programma
anche stabilendo una misura. E poi a che scopo? Per confrontare due
programmi e in che senso?
Un modo puo' essere quello di dire che i programmi sono stringhe e
confrontare la loro lunghezza ma poi? Programmi molto corti possono
non terminare mai (ad esmpio while true do <nop> done) e programmi
rappresentati da stringhe molto lunghe possono non eseguire nemmeno
una volta (ad esempio while false do <tutto il codice che vuoi> done).
Hope it helps
Cheers
Yuri