Escribir función recursiva universal [cerrado]

9

¿Existe una breve construcción explícita de una función recursiva universal ? Todas las definiciones que he visto involucran la numeración de máquinas de Turing de alguna manera, lo que es posible pero parece difícil e inmanejable escribir en un lenguaje de programación de nivel superior (como Python, Haskell, etc.)

lo.logic computability pl.programming-languages sdcvvc
fuente
La pregunta se hizo originalmente en SO , parece más apropiada aquí.
sdcvvc
1
Según tengo entendido, lo que hace una función recursiva universal es dar una cierta numeración de las funciones recursivas (o, de manera equivalente, las máquinas de Turing) para que el resultado pueda calcularse a partir del índice de una función recursiva y la entrada. Por lo tanto, "una función recursiva universal sin numerar máquinas de Turing" no me parece plausible.
Tsuyoshi Ito
3
No nivel de investigación. Cualquier intérprete para un lenguaje completo de Turing es una función recursiva universal.
Warren Schudy

Respuestas:

13

Por supuesto. Escriba rutinas que calculen cada una de las funciones recursivas primitivas de Godel , y escriba una rutina para un operador de búsqueda ilimitado. El conjunto de funciones que puede calcular de esta manera es equivalente al conjunto de funciones que las máquinas de Turing pueden calcular. Más información aquí .

La desventaja es que cualquier entrada a su programa universal necesitaría enmarcarse en términos de esas operaciones simples. Por supuesto, para eso están los compiladores.

Aaron Sterling
fuente
10

Cualquier intérprete para cualquier idioma que sea Turing completo es una función recursiva universal. Hay intérpretes para lenguajes de alto nivel como C ++ o Python.

solsol

Kaveh
fuente
Un intérprete para máquinas de Turing (o máquinas de registro, o funciones recursivas) también es una función recursiva universal, y no es difícil implementarlas. Los implementé en C ++ hace algunos años, y estoy bastante seguro de que sería aún más simple en Python. Use Google, hay muchos simuladores gratuitos en Internet, y algunos de ellos son incluso de código abierto.
Kaveh
8

Una función universal use puede escribir con bastante facilidad en un lenguaje similar a Haskell (sin efectos secundarios, funciones de orden superior), a saber:

u f x = f x

La función ues universal ya que acepta (la descripción de) un programa fy una cinta de entrada x, y le dice que el resultado de la ejecución fde x.

Si bien esta respuesta no es del todo seria, muestra que un compilador o un intérprete para un lenguaje similar a Haskell ya contiene todas las partes de construcción necesarias para una función universal. La moraleja de la historia es que es mejor dedicar tiempo a estudiar cómo funcionan los compiladores e intérpretes que preocuparse por implementar una función universal en términos de máquinas Turing.

Andrej Bauer
fuente
Sin embargo, utoma una función: la llamaría una función de orden superior. Me gustaría utomar un número entero, o un tipo de datos algebraico regular. No fuerzo ningún modelo específico de cálculo, siempre que el argumento usea ​​tangible; por ejemplo, se puede serializar desde / a una cadena.
sdcvvc
En una máquina real (una vez que se compila el código) use cierra, que es una secuencia finita de bytes. Incluso en el teorema de utm habitual, el entero que utoma representa una función.
Andrej Bauer el
5

Consulte también este artículo de John Tromp, utilizando lógica combinatoria. Un informe anterior, aparentemente ya no disponible, era aún más ordenado.

Yuval Filmus
fuente