E 'possibile creare un Quine in tutte le lingue Turing-complete?

Question

Volevo solo sapere se è possibile al 100%, se la mia lingua è Turing-complete, per scrivere un programma in modo che le stampe si out (ovviamente non si utilizza una funzione di lettura di file)

Quindi, se la lingua ha solo le cose veramente necessarie al fine di renderlo turing completa (I proverebbe che traducendo Brainf * Codice ck ad esso), come output, le variabili, le condizioni e goto (hell yes, goto), posso provare a scrivere un Quine in esso?

Sono anche chiedendo questo perché non sono sicuro che un Quine si inserisce direttamente nel diritto di Turing che la macchina di Turing è capace di qualsiasi compito computazionale. Voglio solo sapere in modo da non provare per anni senza sapere che può essere impossibile.

Answer 1

  

Ogni linguaggio di programmazione che è   Turing completa, e che è in grado di   uscita qualsiasi stringa (da un computabile   la funzione della stringa come da programma -   questa è una condizione che è tecnico   soddisfatto in ogni programmazione   lingua in esistenza) ha un Quine   programma (e, in effetti, infiniti   Quine programmi, e molti simili   curiosità) come segue dalla   -Punto fisso teorema.

Vedi qui

Answer 2

mi sono imbattuto in questo problema un paio di mesi fa.

Mentre si scrive un Quine non prova necessariamente che una lingua è Turing completa, si tratta di una suggestione forte;) Per quanto riguarda Turing completezza va, se è possibile (come hai detto) fornire una traduzione valida dal lingua all'altra Turing-complete lingua, quindi la lingua è Turing completo.

Detto questo, qualsiasi linguaggio che è Turing che l'output può una stringa dovrebbe essere in grado di generare un Quine. Inoltre, da Wikipedia:

  

Un quine è un punto fisso di un ambiente di esecuzione, quando l'ambiente di esecuzione è visto come una funzione. Quines sono possibili in qualsiasi linguaggio di programmazione che ha la capacità di uscita qualsiasi stringa computabile, come diretta conseguenza di Kleene di ricorsione teorema . Per il divertimento, i programmatori a volte tentano di sviluppare il più breve Quine possibile in qualsiasi linguaggio di programmazione.

Answer 3

E 'possibile avere un linguaggio di programmazione che non può stampare tutti i simboli nella sua rappresentazione. Ad esempio, l'I / O può essere limitata ai caratteri ASCII a 7 bit con parole chiave del linguaggio in arabo. Questa è l'unica eccezione che posso pensare.

Answer 4

Beh, tecnicamente, non sempre. Secondo il prova su Wikipedia , il linguaggio di programmazione deve essere una numerazione ammissibile. linguaggi di programmazione Turing-complate pratici e sane di mente sono tutti numerazioni ammissibili. E un linguaggio di programmazione Turing-complate è una numerazione ammissibile se è possibile tradurre tra questo e un altro numerazione ammissibile.

Un esempio Turing-completo linguaggio di programmazione che non è una numerazione ammessa:

Il codice sorgente contiene sempre una o due stringhe fuggiti doublequoted. Se l'ingresso è vuoto, uscita la prima stringa se ci sono due stringhe o loop infinito se presente. In caso contrario, valutare l'ultima stringa in Python, utilizzando l'ingresso originale come input.

Non è una numerazione ammissibile in quanto, dato un programma Python, dobbiamo sapere il suo comportamento quando l'ingresso è vuoto, di tradurla in questa lingua. Ma possiamo mai sapere se si tratta di un ciclo infinito, in quanto non siamo in grado di risolvere il problema della terminazione. Sappiamo che la traduzione esiste sempre, però.

E 'impossibile quines di scrittura in questa lingua.