¿Cómo escribir una enumeración de todas las funciones computables?

Question

Motivación: Me gustaría poder utilizar la programación funcional de juguetes en idiomas sin funciones de primer orden, mediante el uso de números naturales en lugar de funciones.

Una función universal es una función f: N -> (N -> N), equivalentemente f: N * N -> N que enumera todas las posibles funciones computables. En otras palabras, hay un número k tal que f (k) es la función de cuadratura, hay un número j tal que f (j) es la función primo n-ésima, etc.

Para escribir tal función, se puede tome cualquier lenguaje completo de Turing (compilador de lenguaje de programación, cálculo lambda, máquinas de Turing ...) y enumere todos los programas. Me gustaría permitir no solo la evaluación, sino también las operaciones en funciones como la adición, la composición y el currying. Por ejemplo, dados los índices de dos funciones f, g Me gustaría saber cuál es el índice de la función f + g, o f compuesto con g. Esto permitiría la "programación funcional de juguetes".

¿Cuál es una buena manera de escribir dicha biblioteca de códigos? No estoy buscando un tarpit minimalista de Turing que tenga dificultades para calcular el factorial de 10, ni tampoco quiero escribir un compilador avanzado. Debe tener algunas funciones básicas como la adición y la posibilidad de escribir bucle, pero no mucho más.

Se aceptan soluciones en todos los idiomas de alto nivel. El seudocódigo, Haskell y Python son preferidos. Puede asumir una aritmética de precisión arbitraria. No se permite el uso de eval o similar.

Aclaración: Las funciones enumeradas consistirán en todas las partial recursive (computable), esto incluye funciones que no se detienen en algunas entradas. La función universal se colgará en esos casos; por supuesto esto es inevitable. Ver también: funciones recursivas m - http://en.wikipedia.org/wiki/Μ-recursive_function.

Answer 1

no es una pregunta fácil. Supongo que debes comenzar con un generador de funciones que pueda generar todas las funciones una a una. Esto dará como resultado una enumeración.

Ya que tiene que lidiar con múltiples dimensiones infinitas ... pensemos en ello.

Reduzcamos el problema a las funciones con n parámetros y las operaciones básicas +, -, *, /.
Vamos a construir todas las funciones con una sola operación:

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

Supongo que es fácil ver que algunas de estas funciones tienen más sentido ya que otras y algunas pueden ser iguales, pero al menos es una asignación que se puede generar áspero un bucle.

Ahora en la siguiente iteración, uno podría fácilmente añadir a cada una de estas funciones

• uno de los parámetros ya existentes con todas las operaciones
• un tercer parámetro con todas las operaciones

Después tiene una gran lista de funciones para las que puede repetir el paso dos.

Dado que se trata de una función que estima todas las funciones más complejas, como sin y log (serie taylor), estas también deben cubrirse en este espacio de funciones.

¿Le sirve de ayuda? ¡Siéntete libre de editar esta publicación!

Acabo de volver a leer su publicación. Si desea enumerar todas las funciones programáticas y no solo numéricas una vez, supongo que será más complejo. Supongo que entonces tendría sentido trabajar con una "función de asignación < -> number" al comprimir el origen de su función y tratar el archivo zip como un número grande. A la inversa, puedes intentar descomprimir cualquier número y ver si crea una función útil :-) Pero supongo que tendrás muchos números que ni siquiera son archivos zip.

Pero sería fullfill su exigencia de que para cada función hay un número que lo representa :-)

Answer 2

Lo que se quiere que se llama un intérprete.

En primer lugar, cualquier enumeración con las propiedades que desee no se ajustará a las funciones interesantes que desea manipular en los primeros 2^32, o incluso los primeros 2^64, enteros. Por lo tanto, necesitará números enteros más grandes, asignados en algún lugar de la memoria y referenciados a través de un puntero.

¿Por qué no utilizar matrices de caracteres (cadenas) que representan el programa en cualquier sintaxis existente, entonces? Considere una cadena como un entero si eso lo hace feliz. El número de la función para calcular f1()+f2() es la cadena hecha de (representación de f1), "+" y (representación de f2). Obtienes la idea ...

Lo que este enfoque no tiene es la unicidad de la representación de una función, que tal vez haya quedado implícita en tu pregunta (no estoy seguro). De lo que estoy seguro es de que la unicidad de la representación es incompatible con operaciones de composición simples, o incluso computables, en las representaciones de funciones. Por ejemplo, si no fuera el caso, habría una solución fácil al problema de Detención.

Answer 3

Puede tomar cualquier lenguaje de programación para que pueda determinar si algo es un programa o no, y enumerar todos los programas en orden lexicográfico. Para evitar al menos un poco de la explosión combinatoria, puede asignar nombres definidos por el usuario (variables, funciones, etc.) en una forma normalizada. Obviamente, esto resultará en un número inmenso de funciones, y no será fácil elegir cuáles son realmente útiles. Cualquier método automático de recorte excluirá algunas funciones que realmente deseará, o no reducirá la explosión combinatoria lo suficiente como para ser útil, o ambas cosas.

La otra desventaja de esto es que va a ser muy difícil pasar del número a la función: es difícil encontrar una forma mejor de encontrar la función 433,457,175,432,167,463 que enumerar unas cuatrocientas cuatrillones de funciones.

La otra forma es codificar una función en un número asignando los símbolos a los números y concatenándolos efectivamente.

Supongamos que los símbolos son +, -,: =, ==, <, si, entonces, endif, do, end_do_condition, enddo y un delimitador de instrucción. Eso es 11 símbolos allí mismo, sin variables, para un conjunto bastante mínimo que no incluye nada como una llamada a función, y requiere que se multiplique y se divida. (No estoy seguro de si esto funcionaría sin un operador lógico o dos). Agregue cinco nombres de variables, y obtendrá un lenguaje de programación con caracteres de 4 bits. Esto significa que un máximo de dieciséis caracteres encajarán en un entero sin signo de 64 bits.

Una vez que tenga esto, todas las relaciones posibles entre las funciones se podrán representar como una relación aritmética, pero una relación inmensamente complicada que será muy compleja en la práctica.

En resumen, aunque esto es teóricamente posible, en la práctica va a ser demasiado torpe. Probablemente sería más fácil escribir un intérprete para un lenguaje funcional en su idioma de elección no funcional.

Answer 4

Para escribir una función de este tipo, se puede tomar cualquier lenguaje de programación (lenguaje compilador, lambda de cálculo, máquinas de Turing ...) y enumerar todos los programas de Turing-completo

I' No estoy muy seguro de si eso puede hacerse ... Parece que va en contra de la tesis de la Iglesia de Turing. Para enumerar todos los programas, primero necesita un algoritmo que determine qué programas son válidos y cuáles no, y eso es imposible ... A menos que eso no le importe y permita programas incorrectos en su idioma.

Pero quizás el Godelization de un sistema formal podría ayudarlo ... Intentaría con Lisp, tener el código como datos podría ayudar mucho.

Answer 5

No estoy seguro Entiendo. Sin embargo, una cosa: no se pueden enumerar todas las posibles funciones computables. Respuesta corta: porque de lo contrario habrá un antivirus universal. Respuesta larga: porque si hubiera tal enumeración, tendrías en ese conjunto también la función que calcula la enumeración en sí misma. Como la paradoja de Russel.

Una respuesta diferente a su pregunta sería: desea `` enumerar '' todas las funciones computables posibles; para hacer eso, es posible que desee representarlos como números primos y usar su composición como multiplicación. Esto garantizaría la singularidad. La factorización le dará la función inversa.

Answer 6

Si bien no es demasiado difícil enumerar todas las posibles expresiones en algún lenguaje, usted no será capaz de restringirlo a esas expresiones que denotan funciones de terminación.

Pero si no está interesado en la terminación, el uso de combinadores (con algunas primitivas aritméticas para su utilidad) podría ser la mejor manera, ya que evita introducir nombres de variables de esa manera.

Answer 7

Como dijo Pascal, lo que quiere es un intérprete, pero uno puede hacerlo aún mejor: use el procesador como intérprete directamente.

Introduzca el número N (por ejemplo, como una gran matriz int) directamente en un búfer y ejecute este búfer como código de máquina.

Para cada función posible que su computadora puede ejecutar, existe una N. Desafortunadamente. no cada N es un programa válido (esto no fue solicitado) o el programa de terminación (que no es posible).

Por otro lado, esta función será producir gemas tales como World of Warcraft, incluyendo Microsoft Office 17 Service Pack 6 y Windows 9.