Razonamiento correcto?¿

[insomnio]

Buenas,

Siento ser tan pesado y mas en stas fechas, pero me estoy volviendo loco y mis conocimientos de "mates" como habeis podido comprovar son nulos....

Pues bien os comento ste razonamiento y haber q opinais

Para saber si un conunto es ER, bastaria con que un "programa" fuese almenos capaz de responder "si" en caso de q el elemento respondiese al conjunto y si encima puediese decir q "no" seria a más de ER REC

Si un "programa" con la entrada 'x' se para significa q 'x' pertenece al Dom(A), siendo 'A' un conjunto cualquiera de una funcion, pero claro, como esta funcion es calculada por un "programa" sera recursiva, por lo q un elemento q pertenezca al conjunto de salida de una funcion recursiva dicho conjunto sera ER

Son correctos estos razonamientos?¿

Gracias

[leach]

Por favor, ¿puedes reescribir el planteamiento del problema sin abreviaturas y de una manera un poquito más organizada?

No consigo entender a qué te refieres. No caigo en qué quiere decir que un conjunto sea "ER" o "ER y ERC", o el que 'A' sea un conjunto cualquiera de una función.

Si puedes replantear el problema, me gustaría echarle una mirada.

[insomnio]

Perdona, pero aun no os lo quiero plantear, pq como es logico vosotros no hareis el examen por mi y me sabe bastante mal q me lo deis todo "con cuchara" bien replanteo mi pregunta

NOTA: ER significa Enumerable Recursivamente y REC q es recursivo


Para saber si un conunto es ER, bastaria con que un "programa" fuese almenos capaz de responder "si" en caso de q el elemento respondiese al conjunto y si encima puediese decir q "no" seria a más de ER REC

Si un "programa" con la entrada 'x' se para significa q 'x' pertenece al Dom(A), siendo 'A' un conjunto cualquiera de una funcion(por ejemplo el de los naturales), pero claro, como esta funcion es calculada por un "programa" sera recursiva, por lo q un elemento q pertenezca al conjunto de salida de una funcion recursiva dicho conjunto sera ER

Son correctos estos razonamientos?¿

Os pongo un ejemplo de un problema a ver si asi me explico mejor....(pq tienes razon si lo lees no tiene ni pies ni cabeza )

1-Demostrar q las siguientes caracterizaciones son equivalentes:

a)A=0(conjunto vacio)| A es la imagen de una funcion recursiva total

2- Demostrar q todo conjunto enumerable recursivamente infinito tiene un subconjunto infinito recursivo


Espero q estos dos problemas acaben de explicar lo q yo he puesto

Saludos y gracias

[leach]

Bueno, sigo sin tener muy claro lo que quieres decir, pero entiendo que hablas de computación.

En efecto, si tenemos dos conjuntos A y B, con A\subseteq B, decimos que A es recursivamente enumerable respecto a B si podemos encontrar un procedimiento computacional \mathcal{F} tal que, dado un b\in B, se tenga que \mathcal{F}(b) termina con respuesta afirmativa si y sólo si b\in A.

En otras palabras, que sólo tenemos garantizado que el programa \mathcal{F} no se cuelga en los elementos de A, y además en esos elementos es en los únicos en los que \mathcal{F} da una respuesta afirmativa. Para otros elementos que no estén en A, el programa puede colgarse o no, y en caso de no colgarse, la respuesta será siempre negativa.

Se dirá que A es Recursivo si es posible encontrar un procedimiento \mathcal{F}, que no sólo da SI para todos los elementos de A, si no que para los elementos de B-A no se cuelga nunca y da como resultado NO. Por tanto, A y B-A pueden ser clasificados algorítmicamente dentro de B: ambos son RE, uno para \mathcal{F} y el otro para \mathrm{no-}\mathcal{F}.

******

Ahora tu pregunta, si la he entendido:

Creo que tú partes de un cierto procedimiento \mathcal{F}, cuya entrada es un conjunto B, y cuya salida, en caso de no colgarse, es SI o NO. Entonces, defines \mathrm{Dom}(B) como el conjunto de los elementos de B tales que, al aplicarles \mathcal{F}, el procedimiento termina con un SI.

¿Es este conjunto RE? Obviamente sí, por la propia definición.

¿Cuándo es además REC? Si y sólo si \mathcal{F} no se cuelga para ningún elemento de B. Es decir, que si la salida no es SI, tenemos garantizado que la salida será NO. En otras palabras, si B - \mathrm{Dom}(B) es ER pa el programa \mathrm{no-}\mathcal{F}.

No sé si es eso lo que preguntabas. La computación no es mi especialidad.

Saludos. :h:

[leach]

Bueno, llevo un par de días esperando a que respondas, y mientras tanto he pensado sobre tu pregunta. Creo que ya entiendo lo que querías decir. En realidad, te referías a: dado un conjunto B, y un procedimiento \mathcal{F} en B, definamos \mathrm{Dom}(\mathcal{F}) como el conjunto de puntos de B en los cuales el procedimiento \mathcal{F} termina.

¿Es entonces \mathrm{Dom}(\mathcal{F}) ER? : La respuesta es sí. Basta definir el procedimiento \mathcal{F}' como el que aplicado a un b\in B da respuesta afirmativa si el procedimiento \mathcal{F} aplicado a b termina en tiempo finito.

¿Es siempre \mathrm{Dom}(\mathcal{F}) REC? : No, y pueden darse los ejemplos usuales (considerar B como el conjunto de todos los procedimientos posibles, y \mathcal{F} como el procedimiento que da respuesta afirmativa si al ejecutar un elemento de B, su ejecución termina en tiempo finito).

¿Bajo qué condiciones es \mathrm{Dom}(\mathcal{F}) REC? : Tendrás que aplicar la definición, y buscar la condición sobre \mathcal{F} o B que más te convenga. No se me ocurre un teorema general, que no sea trivialmente equivalente a la definición. Pero, una vez más, yo no tengo mucha idea de computación :???: .