4 votos

Estructura de la función recursiva parcial sobre recursivamente enumerable de la guardia

He leído que la función $$ f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if %#%#%}\\ \text{undefined} & \quad \text{otherwise} \end{array} \right. $$

es recursivo si $n \in A$ es recursiva y la guardia $g(n)$ $if$ es recursivamente enumerable (ya que el siempre $n \in A$ función es recursiva).

He leído también que si el $\text{undefined}$ parte no siempre es $else$, no podemos concluir que el $undefined$ no es recursiva.

Alguien podría por favor explicar por qué se debe utilizar siempre la función no definida en la otra parte cuando tenemos una r.e. la guardia? Y también si $f$ se define de la siguiente manera, ¿qué condiciones debería $f$ cumplir (aparte de ser siempre indefinido), de modo que $h(n)$ es recursiva.

$$ f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if %#%#%}\\ h(n) & \quad \text{otherwise} \end{array} \right. $$

1voto

universalset Puntos 6716

Parece ser que hay un par de confusiones implícita en la pregunta, así que vamos a tratar de explicarme lo que está pasando aquí antes de abordar sus preguntas explícitas.

Vamos a considerar lo que ocurre para una función de $f$ definida como en su primera expresión. Una prueba de la función de $f$ es recursivo mostrando cómo se calcula de la siguiente manera: En la entrada de $n$, comenzar a enumerar $A$ (que se puede hacer de forma recursiva porque $A$ es recursivamente enumerable). Si alguna vez $n$ aparece en la enumeración, entonces sabemos que $n \in A$: en ese caso, calcular y de salida $g(n)$ (una función recursiva). Desde $n$ finalmente será enumerado si y sólo si $n\in A$, esto significa que nuestro procedimiento de salidas $g(n)$ exactamente al $n\in A$, y de nuestro procedimiento nunca se detiene exactamente al $n\not\in A$. Por lo tanto este procedimiento, de hecho, se calcula $f(n)$, lo $f$ es un (parcial) de la función recursiva.

Tenga en cuenta que esta construcción no funciona, y por lo tanto no podemos concluir que $f$ es recursivo, si necesitamos que nuestro programa de salida algo al $n\not\in A$. Si $A$ es no recursivo (pero sólo recursivamente enumerable), nunca podemos estar satisfechos, no importa la cantidad de $A$ nos enumerar, que algunos $n\not\in A$. Así que no vamos a ser capaces de confiar en una enumeración de $A$ a decidir qué salida dependiendo de si $n\in A$, debido a que si alguna vez nos eligió para adivinar que $n\not\in A$ (visto hasta ahora) potencialmente podríamos estar equivocados. Esta es la razón por la que necesitamos $f$ a ser indefinido para $n\not\in A$ si estamos a la conclusión de que la $f$ es recursiva.

Por último, se pregunta cuáles son las condiciones para $h$ en virtud de la cual una función de $f$, que se define a ser $f(n)=g(n)$ $n\in A$ $f(n)=h(n)$ lo contrario, es recursiva. Realmente no es posible dar una respuesta general a esta que no se limita a repetir el problema. Sin duda alguna el seguro de $h$ trabajo: por ejemplo, $h=g$ (debido a que, a continuación, $f = g$ como bueno, y por lo tanto $f$ es recursivo porque $g$ es). En general, podría haber muchos tal $h$, debido a que hay muchas funciones recursivas, que coincide con las $g$ para los valores de $A$. Describir todas esas funciones es esencialmente imposible. Lo que no puede hacer (al menos si $A$ es no recursivo) es encontrar una función de $h$ tal que $g(n)\neq h(n)$ para todos (o todos, pero un número finito) $n$. Si pudiera, podría determinar (mediante el cálculo de $f(n)$, $g(n)$, y $h(n)$) si o no $n\in A$, y, por tanto, $A$ sería recursiva.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X