Forum Informatica Unict

LAUREA MAGISTRALE => Teoria della Computabilità, 9 CFU => Topic started by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 29-05-2013, 22:53:04



Title: Solo per amanti del pericolo! <<Quine>>
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 29-05-2013, 22:53:04
Ecco cosa ho scoperto stasera riguardo un certo concetto:
Quine (http://goo.gl/l6DSw)

Un "quine" si definisce come un programma che possa emettere, in output, e senza operazioni di I/O (a parte ovviamente la scrittura dell'output), il proprio codice sorgente.

Esibire la presenza di quine, in URM, una volta enumerati tutti i programmi associandoli tramite biiezione ai naturali, consiste nel trovare un programma (un numero) che, se eseguito, produca in output lo stesso numero che rappresenta il suo programma.

Poi, per divertirsi di più, si può cercare il "minimo" programma (numero) che è un quine, cioè il quine più piccolo secondo qualche relazione di ordinamento tra programmi (per es. la lunghezza in numero di istruzioni). :-OK

Questo problema non è per nulla banale :nono!

Divertitevi gente (studiate, va che è meglio .coolio |-O)...


Title: Re:Solo per amanti del pericolo! <<Quine>>
Post by: Giuseppe Scollo on 30-05-2013, 00:53:25
Grazie per questa bella provocazione, naturalmente mi associo alla diffida dal provarci prima di avere consolidato la preparazione per l'esame, quantomeno per la prova scritta di calcolabilità. Il problema è un classico dei corsi di Programmazione, ed è già non banale per linguaggi ad alto livello (tipicamente LISP e simili). Lì si vuole come output proprio il testo del sorgente, e questo sarebbe relativamente facile da produrre se non fosse per quelle benedette virgolette che devono racchiudere una stringa da specificare in un'istruzione di output... Per le URM, al momento meglio non pensarci, ne riparliamo ad agosto o più in là.


Title: Re:Solo per amanti del pericolo! <<Quine>>
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 30-05-2013, 01:57:19
Credo di averlo risolto in due secondi per le URM, altro che aspettare fino ad agosto...

Se esistono quine in URM, la seguente espressione (e il relativo programma, quindi), trova la minima!

\fs{3}a=\({\mu_k\({S\({{\({k}\)}_1, {\({k}\)}_2, {\({k}\)}_1, {\({k}\)}_3}\)}\)}\)_1

E, se poniamo:
\fs{3}g(y, z)=\({{\mu_k\({{\({k}\)}_1>z\;\wedge\;S\({{\({k}\)}_1, {\({k}\)}_2, {\({k}\)}_1, {\({k}\)}_3}\)}\)}\)_1
la funzione ottenuta per ricorsione primitiva da \fs{3}f e \fs{3}g dovrebbe darmi TUTTE le quine su URM... .huh

Eppure mi sembra fin troppo facile, così .penso... non vorrei che fosse la tarda ora a illudermi... .leggo

Ora bisogna dimostrare che esiste almeno una quine in URM, così che non si attenda invano... .penso

Buh... .whistling


Title: Re:Solo per amanti del pericolo! <<Quine>>
Post by: Giuseppe Scollo on 30-05-2013, 13:01:22
Dunque, non ho tempo per riflettere sull'espressione a, ma una quine URM esiste, la minima è pure facile da trovare, ma dipende (naturalmente) dalla codifica dei programmi. Ora, se si sceglie la codifica proposta nel testo di Cutland, e se si conviene che il programma vuoto non è un programma (convenzione necessaria perché quella codifica sia una biiezione) allora la quine in questione è il programma Z(1). Se invece si modifica in modo ovvio la codifica in modo da ammettere anche il programma vuoto nel novero dei programmi URM (ovvero, si toglie il "-1" finale nell'espressione della funzione τ, e si assegna il codice 0 alla k-pla vuota, aka k=0), allora il programma vuoto è la quine in questione
(estremamente minima, direi).


Title: Re:Solo per amanti del pericolo! <<Quine>>
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 19-06-2013, 23:19:23
Mi ha tolto tutto il piacere di cercarle  .poverinoi .poverinoi .poverinoi ...

Complimenti |-O!