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.Come scrivere un'enumerazione di tutte le funzioni computabili?
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.
Dal momento che sembra avere bisogno di qualche aiuto e spingendo ad accettare una risposta. Il meglio è http://stackoverflow.com/questions/1797457/how-to-write-an-enumeration-of-all-computable-functions/1797575#1797575 di Pascal Cuoq. Anche l'ultimo di Hirschhornsalz non è male. Posso capire che è difficile per te accettarlo. – babou