¿Existe una función recursiva parcial que asigne $e$ al menor elemento de $W_e$ ?

Question

¿Existe una función recursiva parcial $f$ que mapea $e$ al menor elemento de $W_e$ si $W_e\neq \varnothing$ ?

¿Podemos aplicar el $\mu$ -(minimización) a un predicado parcialmente decidible para obtener una función recursiva parcial (como al definir $f(x)=\mu z(z\in W_e)$ si $W_e\neq\varnothing$ e indefinido en caso contrario, ya que $z\in W_e$ es parcialmente decidible)?

Mi suposición era que no existe tal $f$ pero no sabía cómo mostrarlo. Gracias en adavnce.

Answer 1

Tu intuición es correcta: no existe tal función.

Podemos verlo de dos maneras diferentes:

• Contradicción : Supongamos que existiera un $f$ . Entonces - dado un conjunto c.e. arbitrario (infinito) $A$ - podríamos calcular la secuencia $$\min(A), \min(A\setminus\{\min(A)\}), \min(A\setminus\{\min(A), \min(A\setminus\{\min(A)\})\}), ...$$ aplicando iterativamente $f$ . Pero esto precisamente enumera $A$ en orden, y así hace $A$ computable. Como hay conjuntos no computables, esto no puede ocurrir.

• Diagonalización directa : Dada una función computable $f$ podemos encontrar un $e$ tal que $(i)$ $2$ entra en $W_e$ en el escenario $0$ , $(ii)$ $1$ entra en $W_e$ en el escenario $n+1$ si $f(e)$ se detiene y emite " $2$ " en la etapa exactamente $n$ y $(iii)$ no entrar otros números $W_e$ en cualquier otra circunstancia. Entonces obtenemos $\min(W_e)=2$ si $f(e)\not=2$ Así que $f$ no hace lo que queremos.

  • Esto encaja en la "imagen de juego" de los conjuntos c.e: Elijo un $f$ y empiezas a construir mi $W_e$ . Pones $2$ en ella, lo que me obliga a decidir finalmente qué $f(e)$ es; en cuanto lo haga, si digo " $2$ " y luego pones $1$ en mi set, y si digo otra cosa que no sea " $2$ "no haces nada. De cualquier manera, has derrotado a mi pretendido $f$ .

No he dado todos los detalles de ninguno de los dos casos, pero la idea debe quedar clara. Completar los detalles (del primero, sobre todo) es un buen ejercicio.