Pages: [1]   Go Down
Print
Author Topic: Solo per amanti del pericolo! <<Quine>>  (Read 1839 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


Più grande è la lotta, e più è glorioso il trionfo


WWW
« on: 29-05-2013, 22:53:04 »

Ecco cosa ho scoperto stasera riguardo un certo concetto:
Quine

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 univ)...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.383


« Reply #1 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à.
« Last Edit: 30-05-2013, 00:56:00 by Giuseppe Scollo » Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #2 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...

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

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

Buh...
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Giuseppe Scollo
Moderator
Forumista Esperto
*****
Offline Offline

Posts: 1.383


« Reply #3 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).
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.446


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #4 on: 19-06-2013, 23:19:23 »

Mi ha tolto tutto il piacere di cercarle  ...

Complimenti univ!
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Pages: [1]   Go Up
Print
Jump to: