Un conjunto es recursivamente enumerable de la fib es el rango de un total de función recursiva

Question

Un conjunto se llama recursivamente enumerable si es que el dominio de una parte recursiva de la función.

¿Cómo puedo demostrar que esta definición es equivalente a "Un conjunto es recursivamente enumerable de la fib es el rango de un total de función recursiva"?

Yo sólo podía mostrar una dirección: si un conjunto es el rango de un total de función recursiva $f$, entonces es el dominio de una función recursiva parcial, mediante la definición de una función de $g$, en la entrada de $y$, busque una $x$ tal que $f(x)=y$.

Answer 1

Parece que usted está teniendo dificultad en algún lugar con la conversión de la reunión informal de ensayo breve en un completo y detallado croquis.

Así que vamos a ver en detalle cómo una (no vacío) conjunto de r.e. (recursivamente enumerable) implica que es el rango de algunos total de la función recursiva.

Deje $A\subseteq \mathbb{N}$ ser no vacío de r.e. conjunto. Entonces, por definición, existe una función recursiva parcial $f_A:\mathbb{N} \rightarrow \mathbb{N}$ tal forma que: $$f_A(x)=1 \quad if \, x\in A$$ $$f_A(x)=\,\uparrow \qquad if \, x\notin A$$

Queremos construir una (total) función recursiva $g:\mathbb{N} \rightarrow \mathbb{N}$ tal forma que: $$range(g)=A$$ Vamos a dividir en dos casos:

(1) tiene Un número infinito de elementos

En ese caso, es posible definir una función como $step:\mathbb{N}^3\rightarrow\mathbb{N}$ tal que $step(i,t,x)$ vuelve $1$ si se trata de un programa correspondiente al índice $i$ detiene(cuando se le da la entrada de $x$) exactamente en el paso $t$ - y $0$ lo contrario.

Observe que puesto que la función de $f_A$ descrito anteriormente es parcial recursiva, existe algún programa que calcula. La variable $x$ a continuación se supone que para ser dado como entrada para la función de $g$. Aquí es cómo vamos a proceder con la construcción de la función de $g(x)$:

$i:=índice de\;\; algunos\;programa\;\; calcula\;f_A \\ n:=0 \\ m:=0 \\ while(n\neq x+1) \,\,\{ \\ a:=primero(m) \\ b:=segundo(m) \\ \qquad si(paso(i,a,b)=1) \,\,\{ \\ \qquad \,\, n:=n+1\\ \qquad \,\,y:=b \\ \qquad \} \\ m:=m+1 \\ \} \\ retorno \;\; y$

Para las funciones de la $first:\mathbb{N} \rightarrow \mathbb{N}$$second:\mathbb{N} \rightarrow \mathbb{N}$, véase, por ejemplo, https://en.wikipedia.org/wiki/Pairing_function. Para definir rigurosamente considerar cualquier computable bijective función de $pair:\mathbb{N}^2 \rightarrow \mathbb{N}$. Definir: $$first(x)=\{\,a\in\mathbb{N} : \exists b\in \mathbb{N} \, (pair(a,b)=x) \}$$ $$second(x)=\{\,b\in\mathbb{N} : \exists a\in \mathbb{N} \, (pair(a,b)=x) \}$$ Creo que estas definiciones deben estar bien (pero no estoy completamente seguro). De todos modos, tenga en cuenta que las principales propiedades de estas funciones se que para todos los $a,b \in \mathbb{N}$ tenemos: $$first(pair(a,b))=a$$ $$second(pair(a,b))=b$$

(2) tiene Un número finito de elementos

Supongamos que el número de elementos de Una se $N$. Entonces podemos escribir (sin repetición) como: $$A=\{a_0,\,a_1,....,a_{N-1}\}$$

Ahora definir:

$g(x)=a_{x} \qquad \; 0\leq x \leq N-1 \\ g(x)=a_{N-1} \qquad \; x \geq N$

P. S.

El método anterior, en caso de que(1) no repetir los elementos de A (en el rango de g) cuando es infinito.

El método que se describe en los comentarios debajo de la pregunta es un poco diferente, y elimina la necesidad de tener un caso para el número finito de elementos. Supongamos $e\in A$. Aquí es un boceto para el cálculo de $g(x)$ el uso de ese método:

$i:=índice de\;\; algunos\;programa\;\; calcula\;f_A \\ e:=algunos\;elemento\;\; pertenece\;\;\\:=primero(x) \\ b:=segundo(x) \\ si(paso(i,a,b)=1) \,\,\{ \\ y:=b \\ \} \\ si(paso(i,a,b)=0) \,\,\{ \\ \\ y:=e\\\ \} \ \ retorno \;\; y$