Calcolabilità, programma C che prende in input se stesso

[Vitalluni]

Abbiamo visto a lezione che non può esistere una macchina di Turing che rifiuta se stessa (concetto che trovo filosoficamente intrigante), di qui però la curiosità:

come scrivo un programma C che ritorni "true" (0) $<=>$ se riceve in input esattamente il codice sorgente che lo ha generato e "false" (1) altrimenti? (auto-accettazione, teoricamente possibile.. come?)

int main(int argc, char** argv ){
    if(riconosciInput(argc,argv[1]) == 0) //con == 1 avrei un paradosso
        return 0;
    else
        return 1;
}

Così funzionerebbe, però è troppo facile, e noi siamo masochisti, lo scopo è realizzare suddetto programma C senza utilizzare librerie esterne (nemmeno quelle di sistema come stdio.h), deve stare tutto nel "main.c" (la stringa che contiene il sorgente del programma è passata da argv)

Qualcuno ha qualche idea? Ci ho pensato un pochino e non è così banale.

Una prima idea sarebbe che il programma abbia una "C-stringa" che contenga il suo stesso codice, ma questo diventerebbe ricorsivo e quindi una stringa infinita, allora ho pensato che si può alterare leggermente il programma per vedere se una stringa in input è la composizione doppia (non la definisco, capitemi XD) di una stringa che ho in memoria, a questo punto sembra funzionare (tranne forse i caratteri di escape che sono ancora da sistemare)

[apatriarca]

Ma quella funzione che hai scritto nel codice cosa dovrebbe fare? Leggere il codice da file e confrontarlo con la stringa?

[Vitalluni]

L'unico input ammesso è una stringa (stile C) che viene passata al main (nessun file di "lookup" quindi, sennò è banalissimo). Il main deve ritornare 0 $<=>$ la stringa è il codice sorgente del main.c

Una possibile implementazione di

int riconosciInput(int argc, char * argv){
   char my_string[] = "int main(int argc, char** argv ){\n"
"    if(riconosciInput(argc,argv[1]) == 0) ////con == 1 avrei un paradosso\n" //escape di "/"
"        return 0;\n"
"    else\n"
"        return 1;\n"
"}\n";
   return strcmp(argv,my_string)==0?0:1;
}

Che però non va bene perchè anche la funzione "riconosciInput" deve stare nel main.

Qui lo scopo è trovare un programma che riconosce se stesso, quindi un file "main.c" che se compilato diventa un eseguibile che ritorna 0 $<=>$ riceve come input il codice sorgente di "main.c" (senza usare headers di nessun tipo, e senza quindi la possibilità di andare a leggere un file)

[apatriarca]

Un'idea potrebbe essere qualcosa come il seguente. Spero sia chiaro, non l'ho testato ma è l'idea che conta (in pratica sarebbe più facile usare uno script esterno per scriverlo per bene). Quella alla fine è un'unica riga..

extern char *source;
int main(int argc, char *argv[]) {
    int i = 0;
    while (source[i] && argv[1][i]) {
        if (source[i] != argv[1][i]) { return 0; }
    }
    if (argv[1][i++] || argv[1][i++] != '\"') { return 0; }
    for (int j = 0; source[j] && argv[1][i]; ++i, ++j) {
        if (argv[1][i] == '\\') {
            if (argv[1][++i] == '\"' && source[j] != '\"' 
              || argv[1][i] != 'n' && source[j] != '\n'
              || argv[1][i] != '\\' && source [j] != '\\') {
                return 0; 
            }
        }
        if (source[j] != argv[1][i]) { return 0; }
    }
    if (argv[1][i++] != '\"' || argv[1][i++] != ';' || !argv[1][i]) { return 0; }
    return 1;
}
char *source = "extern char *source;\nint main(int argc, char *argv[]) {\n    int i = 0;\n    while (source[i] && argv[1][i]) {\n        if (source[i] != argv[1][i]) { return 0; }\n    }\n    if (argv[1][i++] || argv[1][i++] != '\\\"') { return 0; }\n    for (int j = 0; source[j] && argv[1][i]; ++i, ++j) {\n        if (argv[1][i] == '\\\\') {\n            if (argv[1][++i] == '\\\"' && source[j] != '\\\"'\n              || argv[1][i] != 'n' && source[j] != '\\n'\n              || argv[1][i] != '\\\\' && source [j] != '\\\\') {\n                return 0;\n            }\n        }\n        if (source[j] != argv[1][i]) { return 0; }\n    }\n    if (argv[1][i++] != '\\\"' || argv[1][i++] != ';' || !argv[1][i]) { return 0; }\n    return 1;\n}\nchar *source = ";

[Vitalluni]

"apatriarca":Un'idea potrebbe essere qualcosa come il seguente. Spero sia chiaro, non l'ho testato ma è l'idea che conta (in pratica sarebbe più facile usare uno script esterno per scriverlo per bene). Quella alla fine è un'unica riga..

extern char *source;
int main(int argc, char *argv[]) {
    int i = 0;
    while (source[i] && argv[1][i]) {
        if (source[i] != argv[1][i]) { return 0; }
    }
    if (argv[1][i++] || argv[1][i++] != '\"') { return 0; }
    for (int j = 0; source[j] && argv[1][i]; ++i, ++j) {
        if (argv[1][i] == '\\') {
            if (argv[1][++i] == '\"' && source[j] != '\"' 
              || argv[1][i] != 'n' && source[j] != '\n'
              || argv[1][i] != '\\' && source [j] != '\\') {
                return 0; 
            }
        }
        if (source[j] != argv[1][i]) { return 0; }
    }
    if (argv[1][i++] != '\"' || argv[1][i++] != ';' || !argv[1][i]) { return 0; }
    return 1;
}
char *source = "extern char *source;\nint main(int argc, char *argv[]) {\n    int i = 0;\n    while (source[i] && argv[1][i]) {\n        if (source[i] != argv[1][i]) { return 0; }\n    }\n    if (argv[1][i++] || argv[1][i++] != '\\\"') { return 0; }\n    for (int j = 0; source[j] && argv[1][i]; ++i, ++j) {\n        if (argv[1][i] == '\\\\') {\n            if (argv[1][++i] == '\\\"' && source[j] != '\\\"'\n              || argv[1][i] != 'n' && source[j] != '\\n'\n              || argv[1][i] != '\\\\' && source [j] != '\\\\') {\n                return 0;\n            }\n        }\n        if (source[j] != argv[1][i]) { return 0; }\n    }\n    if (argv[1][i++] != '\\\"' || argv[1][i++] != ';' || !argv[1][i]) { return 0; }\n    return 1;\n}\nchar *source = ";

non funziona così,

anche

char *source = "extern char *sou ...

fa parte del main.

L'idea è quella che citavo appunto nel primo post, se includessi a questo punto anche "la stringa"
diventerebbe una ricorsione infinita.

(però è un primo passo per risolvere i problemi di escape! XD GRANDE!)

EDIT:

FUNZIONA IN TEORIA

[apatriarca]

Non c'è ricorsione infinita. Se guardi bene la stringa non contiene tutto il codice, ma solo fino all'inizio della stringa. A questo punto il codice verifica che nella stringa passata ci sia un " e poi gestisce i carattere di escape necessari per poter confrontare effettivamente sorgente e stringa. Infine si aspetta la presenza di un " e di un ; per terminare il codice.

[Vitalluni]

Si! ho visto niente ricorsione infinita GRANDE:). Il pezzo mancante credo siano ancora i caratteri di escape. (ho editato, ma non in tempo sei stato troppo veloce)

visto che la stringa contiene cose come "////" che il compilatore traduce in automatico in '//', serve anche una funzione che fa l'anti-escape e trasforma "//" la in '////' (o se vogliamo "////////"). Questa funzione può essere tranquillamente dichiarata e definita nel main.c per fortuna altrimenti erano guai

Quindi una volta prende la stringa così com'è, la seconda fa l'anti-escape per trasformarla in una stringa che se compilata diventa la prima.. (che robe contorte)

però quindi la teoria si può tradurre in pratica. Il programma C che riconosce se stesso $\exists$

Grazie:)