Una función de acuerdo con una función primitiva recursiva en todos sino finito muchos puntos es recursiva primitiva

Question

Mostrar que si $f:\mathbb{N} \rightarrow \mathbb{N}$ es primitiva recursiva, $A \subseteq \mathbb{N}$ es un conjunto finito, y $g$ total de la función de acordar con $f$ en cada punto de no $A$, $g$ es primitiva recursiva.

Este es el ejercicio 10.17 de Introducción a las Lenguas y la Teoría de la Computación (4ª Edición) por John Martin.

---

Mi tren de pensamiento:

He a $g$ se define como:

$$ g(n) = \begin{cases} f(n),&\text{if }n\notin A\\ w(n),& \text{if }n \in A \end{casos}$$ donde $w(n):A \rightarrow \mathbb{N}$ es una función desconocida, debido a que el ejercicio no me dan una definición completa de $g$, sin embargo, tengo que demostrar a $g$ es primitiva recursiva.

Necesito demostrar $w$ es primitiva recursiva con el fin de demostrar $g$ es primitiva recursiva. El hecho de que $w$ sólo se define en el conjunto finito $A$ hace primitiva recursiva? Si es así, ¿por qué?

---

EDIT1:

Si asumo $A$ como una primitiva recursiva conjunto con la característica de la función de $\chi_{A}:\mathbb{N} \rightarrow \{0,1\}$: $$ \chi_{A}(n) = \begin{cases} 1,&\text{if }n=k_{1}\\ 1,&\text{if }n=k_{2}\\ \vdots &\vdots \\ 1,&\text{if }n=k_{n}\\ 0,& \text{otherwise} \end{casos}$$ donde $\{k_{1},k_{2},...,k_{n}\} = A$.

Entonces yo podría definir $g$ $$g(n) = w(n)\chi_{A}(n)+f(n)(1-\chi_{A}(n)).$$

Pero todavía tengo el desconocido $w(n)$ que no sé si es primitiva recursiva.

---

EDIT2:

Si $A = \{k_{1},k_{2},...,k_{n}\}$, puedo definir predicados $P_1, P_2, \ldots, P_k, P_f$ por $$ P_{z}(i) = \begin{cases} \text{true},&\text{if }i=k_{z}\\ \text{false},&\text{otherwise} \end{casos}$$ para $z=1,2,...,n$, y $$ P_{f}(i) = \begin{cases} \text{true},&\text{if }\neg(P_{1}(i)\vee P_{2}(i) \vee ... \vee P_{n}(i))\\ \text{false},&\text{otherwise.} \end{casos}$$

La definición de $$ g(i) = \begin{cases} l_{1},&\text{if }P_{1}(i)\\ l_{2},&\text{if }P_{2}(i)\\ \vdots & \vdots \\ l_{n},&\text{if }P_{n}(i)\\ f(i),& \text{if }P_{f}(i) \end{casos}$$ donde $l_1, l_2 , \ldots , l_n \in \mathbb{N}$.

La constante funciones son primitivas recursivas, y $f$ es primitiva recursiva. Los predicados $P_{1},P_{2},\ldots,P_{n}$ $P_{f}$ son primitivas recursivas. Puedo aplicar el siguiente teorema del texto (p.336) a la conclusión de que la $g$ es primitiva recursiva:

Teorema 10.7 Supongamos $f_{1},f_{2},\ldots,f_{k}$ son primitivas recursivas función de $\mathbb{N}^{m}$ a $\mathbb{N}$, $P_{1},P_{2},...,P_{k}$ son primitivas recursivas $n$-lugar de los predicados, y para cada $X\in \mathbb{N}^{n}$, exactamente una de las condiciones de $P_{1}(X)\ldots,P_{k}(X)$ es cierto. A continuación, la función de $f: \mathbb{N}^{m} \rightarrow \mathbb{N}$ definido por $$ f(X)=\begin{cases} f_{1}(X),&\text{if }P_{1}(X) \text{ is true}\\ f_{2}(X),&\text{if }P_{2}(X) \text{ is true}\\ \vdots & \vdots \\ f_{k}(X),&\text{if }P_{k}(X) \text{ is true} \end{casos}$$ es primitiva recursiva.

Answer 1

En lugar de ver su función de $g$ como una extraña combinación de $f$ y una función desconocida $w$, aspecto en el conjunto de $A$$\{ k_1, \ldots , k_n \}$, y ahora mira a la función de $g$ como ser de la forma $$g(i) = \begin{cases}\ell_1, &\text{if }i = k_1 \\ \vdots \\ \ell_n, &\text{if }i = k_n \\ f(i), &\text{otherwise}\end{cases}$$ (for some natural numbers $\ell_1 , \ldots , \ell_n$).

Ahora que casi se parece a una inducción: Mostrar que una función que se diferencia a partir de una primitiva recursiva de la función en más de un lugar es primitiva recursiva.

• Si $f : \mathbb{N} \to \mathbb{N}$ es primitiva recursiva, $k \in \mathbb{N}$, e $g : \mathbb{N} \to \mathbb{N}$ es tal que $g(i) = f(i)$ todos los $i \neq k$, entonces considere el singleton set $\{ k \}$, que es primitiva recursiva, por lo que su función característica $\chi = \chi_{\{k\}}$ es primitiva recursiva. Si $g(k) = \ell$, ten en cuenta que la constante de la función $c$ definido por $c(i) = \ell$ es primitiva recursiva. A continuación, $$g(i) = \chi(i) c(i) + (1 - \chi(i)) f(i).$$ Usted debe tener teoremas que muestran que las funciones combinadas en este camino de la primitiva recursiva de la función son primitivas recursivas.

---

Después de la última edición a la pregunta, parece que el Teorema 10.7 hace todo el trabajo he sugerido anteriormente.

• Todos los conjuntos finitos son primitivas recursivas, por lo que los predicados $P_1 , \ldots , P_n$ que usted describe son primitivas recursivas.
• Primitiva recursiva de los predicados cerrado bajo las operaciones Booleanas básicas, por lo $P_f \equiv \neg ( P_1 \vee \cdots \vee P_n )$ es primitiva recursiva.
• Es fácil mostrar que exactamente uno de $P_1(i) , \ldots P_n(i)$ o $P_f(i)$ es cierto para cada una de las $i$ (suponiendo que su enumeración de $A$ listas de cada elemento exactamente una vez).
• Todas constante funciones son primitivas recursivas, y nos da ese $f$ es primitiva recursiva.

Entonces el teorema se da automáticamente que la función de $g$ descrito anteriormente es primitiva recursiva.