Come scrivere un'enumerazione di tutte le funzioni computabili?

Question

Motivazione: Mi piacerebbe essere in grado di utilizzare la programmazione funzionale del giocattolo in lingue senza funzioni di primo ordine, utilizzando numeri naturali invece di funzioni.

Una funzione universale è una funzione f: N -> (N -> N), equivalentemente f: N * N -> N che enumera tutte le possibili funzioni computabili. In altre parole, c'è un numero k tale che f (k) è la funzione di squadratura, c'è un numero j tale che f (j) è l'n-esima funzione ecc.

Per scrivere tale funzione, si può prendere qualsiasi linguaggio completo di Turing (compilatore di linguaggio di programmazione, calcolo lambda, macchine di Turing ...) ed enumerare tutti i programmi. Mi piacerebbe consentire non solo la valutazione, ma anche le operazioni su funzioni come addizione, composizione, curry. Ad esempio, dati gli indici di due funzioni f, g mi piacerebbe sapere qual è l'indice della funzione f + g o f composto da g. Ciò consentirebbe la "programmazione funzionale dei giocattoli".

Qual è un buon modo per scrivere tale libreria di codici? Non sto cercando un tarpit minimalista di Turing che fatica a calcolare fattoriale di 10, né io non voglio scrivere un compilatore avanzato. Dovrebbe avere alcune funzioni di base come aggiunta e possibilità di scrivere loop, ma non molto di più.

Soluzioni in tutte le lingue di alto livello sono le benvenute. Pseudocodice, Haskell e Python sono preferiti. Puoi assumere aritmetica di precisione arbitraria. Non è consentito utilizzare eval o simili.

Chiarimento: le funzioni elencate saranno costituite da tutte le partial recursive (computable), incluse le funzioni che non si arrestano su alcuni input. La funzione universale si bloccherà in quei casi; ovviamente questo è inevitabile. Vedi anche: funzioni m-ricorsive - http://en.wikipedia.org/wiki/Μ-recursive_function.

Answer 1

non è una domanda facile. Immagino che tu debba iniziare con un generatore di funzioni in grado di generare tutte le funzioni una per una. Ciò comporterà un'enumerazione.

Dal momento che si devono gestire più dimensioni infinite ... pensiamoci.

Riduciamo il problema alle funzioni con n parametri e le operazioni di base +, -, *, /.
Costruiamo tutte le funzioni con una sola operazione:

a + a
a + b
a - a
a - b
a * a
a * b
un/a
a/b

Immagino sia facile vedere che alcune di queste funzioni hanno più senso in quanto altre e alcune potrebbero essere uguali, ma almeno è una mappatura che può essere generata un giro approssimativo.

Ora nella successiva iterazione, si potrebbe facilmente aggiungere a ciascuna di queste funzioni

• uno dei parametri già esistenti con tutte le operazioni
• un terzo parametro con tutte le operazioni

Successivamente hai un enorme elenco di funzioni per le quali puoi ripetere il passaggio due.

Dato che è una funzione che stima tutte le funzioni più complesse come sin e log (serie taylor), queste dovrebbero essere coperte anche in questo spazio di funzioni.

Questo aiuto? Sentiti libero di modificare questo post!

Basta rileggere il tuo post. Se si desidera enumerare tutte le funzioni programmatiche e non solo numeriche una volta, suppongo che sarà più complesso. Immagino quindi che avrebbe senso lavorare con una funzione di mappatura "< -> numero" zippando l'origine della tua funzione e trattando il file zip come un numero elevato. Al contrario, puoi provare a decomprimere qualsiasi numero e vedere se crea una funzione utile :-) Ma immagino che avrai un sacco di numeri che non sono nemmeno file zip.

Ma sarebbe fullfill vostra esigenza che per ogni funzione c'è un numero che rappresenta esso :-)

Answer 2

quello che vuoi è chiamato un interprete.

In primo luogo, qualsiasi enumerazione con le proprietà desiderate non si adatta alle funzioni interessanti che si desidera manipolare nei primi 2^32 o anche nei primi 2^64, numeri interi. Quindi avrete bisogno di numeri interi più grandi, allocati da qualche parte nella memoria e referenziati tramite un puntatore.

Perché non utilizzare matrici di caratteri (stringhe) che rappresentano il programma in qualsiasi sintassi esistente, quindi? Considera una stringa come un numero intero se questo ti rende felice. Il numero della funzione da calcolare f1()+f2() è la stringa composta da (rappresentazione di f1), "+" e (rappresentazione di f2). Ti viene l'idea ...

Ciò che questo approccio non ha è l'unicità della rappresentazione di una funzione, che era forse implicita nella tua domanda (non sono sicuro). Ciò di cui sono sicuro è che l'unicità della rappresentazione è incompatibile con operazioni di composizione semplici o anche computabili sulle rappresentazioni di funzioni - Ad esempio, se non fosse il caso, ci sarebbe una soluzione facile al problema di Halting.

Answer 3

È possibile utilizzare qualsiasi linguaggio di programmazione in modo da poter determinare se qualcosa è un programma oppure no ed elencare tutti i programmi in ordine lessicografico. Per evitare almeno un po 'dell'esplosione combinatoria, è possibile assegnare nomi definiti dall'utente (variabili, funzioni, ecc.) In una forma normalizzata. Ovviamente, questo si tradurrà in un numero immenso di funzioni, e non sarà facile individuare quali siano effettivamente utili. Qualsiasi metodo di trimming automatico escluderà alcune funzioni che in realtà vorrai, o non riuscirà a tagliare l'esplosione combinatoria abbastanza da essere utile, o entrambe le cose.

L'altro svantaggio di questo è che sarà molto difficile passare dal numero alla funzione: è difficile trovare un modo migliore per trovare la funzione 433,457,175,432,167,463 che enumerare circa quattrocento quadrilioni di funzioni.

L'altro modo è quello di codificare una funzione in un numero associando i simboli ai numeri e concatenandoli in modo efficace.

Si supponga che i simboli siano +, -,: =, ==, <, se, quindi, endif, do, end_do_condition, enddo e un delimitatore di istruzione. Sono 11 simboli proprio lì, senza variabili, per un insieme piuttosto minimale che non include nulla come una chiamata di funzione, e richiede che tu ti moltiplichi e divida te stesso. (Non sono sicuro che ciò funzionerebbe senza un operatore logico o due.) Aggiungi cinque nomi di variabili e hai un linguaggio di programmazione con caratteri a 4 bit. Ciò significa che un massimo di sedici caratteri si inserirà in un numero intero senza segno a 64 bit.

Una volta ottenuto questo, tutte le possibili relazioni tra le funzioni saranno rappresentabili come una relazione aritmetica, ma estremamente complicata che sarà di gran lunga troppo complessa per avere ragione nella pratica.

In breve, mentre ciò è teoricamente possibile, nella pratica sarà troppo maldestro. Probabilmente sarebbe più facile scrivere un interprete per una lingua funzionale nel tuo linguaggio di scelta non funzionale.

Answer 4

Per scrivere tale funzione, si può prendere qualsiasi linguaggio di programmazione in linguaggio (compilatore, lambda calcolo , macchine di Turing ...) e enumerare tutti i programmi di Turing-complete

I' Non sono molto sicuro che tutto ciò possa essere fatto ... Sembra che vada contro la tesi della Turing-Church. Per enumerare tutti i programmi, prima è necessario un algoritmo che determini quali programmi sono validi e quali no, e questo è impossibile ... A meno che non ti interessi e autorizzi programmi sbagliati nella tua lingua.

Ma forse il Godelization di un sistema formale potrebbe aiutarti ... Vorrei provare con Lisp, avere il codice come dati potrebbe aiutare molto.

Answer 5

Non capisco. Una cosa però - non è possibile enumerare tutte le possibili funzioni computabili. Risposta breve: perché altrimenti ci sarà un antivirus universale. Risposta lunga: perché se ci fosse una tale enumerazione, avresti in quel set anche la funzione che calcola l'enumerazione stessa. Come il paradosso di Russel.

Una risposta diversa alla tua domanda sarebbe: vuoi "elencare" tutte le possibili funzioni computabili; per fare ciò, potresti volerli rappresentare come numeri primi e usare la loro composizione come moltiplicazione. Questo garantirebbe unicità. Fattorizzazione ti darà la funzione inversa.

Answer 6

Anche se non è troppo difficile enumerare tutte le possibili espressioni in una certa lingua, non sarà in grado di limitare le protezioni per le espressioni che denotano funzioni di terminazione.

Ma se non si è interessati alla terminazione, utilizzare i combinatori (con alcune primitive aritmetiche lanciate per l'utilità) potrebbe essere il modo migliore, poiché si evita di introdurre nomi di variabili in questo modo.

Answer 7

Come ha detto Pascal, ciò che si desidera è un interprete, ma si può fare anche meglio: utilizzare il processore come interprete direttamente.

Immettere il numero N (ad esempio, come un array grande int) direttamente su un buffer ed eseguire questo buffer come codice macchina.

Per ogni possibile funzione che il computer è in grado di eseguire esiste un N. sfortunatamente. non ogni N è un programma valido (questo non richiesto) o il programma di chiusura (che non è possibile).

D'altra parte, questa funzione produrrà gemme come World of Warcraft, Microsoft Office 17, tra cui Service Pack 6 e Windows 9.