Los lenguajes universales son recursivos primitivos.

Question

En primer lugar, estas son las definiciones con las que estoy trabajando.

Definiciones:

Un idioma $L$ es $universal$ si es contable, tiene infinitas constantes, y para cada $n$ , $1 \leq n$ tiene infinitas $n$ -y un número infinito de símbolos de función $n$ símbolos de relación -aria.

Un idioma $L$ es (primitiva) recursiva, si existe una aritmetización (primitiva) recursiva de $L$ . Una aritmetización recursiva de $L$ es una correspondencia unívoca $\pi$ , $\pi: L \rightarrow \mathbb{N}$

{ $\pi (c) | c \in L$ es una constante}

{ $\pi (F) | F \in L $ es un símbolo de función}

{ $\pi (R) | R \in L $ es un símbolo de relación}

{ $\langle \pi(s),n\rangle | s \in L $ es un an $n$ -símbolo de función primaria o símbolo de relación}

Necesito probarlo:

1. Los lenguajes universales son recursivos primitivos.

2. $L$ es recursivo $\Leftrightarrow$ existe un lenguaje universal $L' \supseteq L$ admitiendo una aritmetización recursiva $\pi$ tal que ${\pi(s) \ | \ s \in L}$ es recursivo.

Entonces, para la primera, si entiendo bien las cosas, necesito encontrar un mapa recursivo primitivo que aritmetice el lenguaje. Creo que para las constantes puedo utilizar la función constante, pero todavía tengo que encontrar una manera de mapear también todos los símbolos de función y símbolos de relación. Creo que puedo hacer algo como esto: en lugar de enviar cada constante a sí misma, la envío a 3*C, dejando espacio para los símbolos de función y relación, pero tengo infinitamente muchos de cada aridad, así que... incluso si es contable, la cardinalidad de eso es tan grande que me estoy perdiendo en cómo manejarlo. Te agradecería mucho cualquier ayuda que me puedas dar sobre cómo abordar este problema.

Para la segunda, creo que lo que tengo que demostrar es que soy capaz de añadir cualquier cosa que falte en $L$ para hacerlo recursivo, pero no estoy del todo seguro de cómo hacerlo a nivel formal. Me gustaría conocer tu opinión sobre este problema, y también saber si tienes sugerencias de fuentes donde pueda encontrar más información al respecto. La mayoría de lo que encuentro es sobre máquinas de Turing, y yo necesito un enfoque totalmente diferente.

Answer 1

Hay una salvedad importante en la definición, y es que el mapa $\pi$ hace no deben ser recursivas (primitivas). (De hecho, no tendría sentido exigirlo, porque nadie dice que los símbolos de $L$ son números pares).

Lo único que hace falta es que encuentres un $\pi$ que es cualquier función impar $L\to\mathbb N$ que puedes producir por métodos teóricos de conjuntos libres de forma que los predicados definidos sean recursivos primitivos.

Por ejemplo, puede elegir asignar las constantes de a números de la forma $3n$ los símbolos de función a números de la forma $3n+1$ y las relaciones con los números de la forma $3n+2$ tal que $n$ codifica de algún modo la aridad de un símbolo de función o relación.