Problemi con Fondamenti dell'Informatica

[KuWa]

Salve, devo dare un esame di Fondamenti dell'Informatica per un corso di laurea in Informatica.
Volevo chiedere se qualcuno qui può darmi un consiglio su come risolvere il problema di determinare se un insieme dato è Ricorsivamente Enumerabile o Ricorsivo.

Ad esempio...

{x | phi ( x ) è definita su esattamente x argomenti}

o

{x | phi ( x ) è definita su almeno x argomenti }

o

{x | phi ( x ) vale 10 su esattamente x argomenti distinti}

Ecco, come dimostrare se uno di questi insiemi è o meno RE?

Spero che qualcuno sia in grado di aiutarmi.

[Ziosilvio]

Originariamente inviato da KuWa

Volevo chiedere se qualcuno qui può darmi un consiglio su come risolvere il problema di determinare se un insieme dato è Ricorsivamente Enumerabile o Ricorsivo.

Un sottoinsieme X dell'insieme dei numeri naturali è ricorsivo se esiste un algoritmo che, preso in input un numero naturale n, restituisce entro un tempo finito il valore 1 se n appartiene a X, e il valore 0 se n non appartiene a X.
Equivalentemente: X è ricorsivo se e solo se è ricorsiva la sue funzione caratteristica.
Qualche regola:
- il complementare di un insieme ricorsivo è ricorsivo;
- l'unione e l'intersezione di un numero finito di insiemi ricorsivi sono ricorsive;
- l'unione e l'intersezione di un numero infinito di insiemi ricorsivi non sono necessariamente ricorsive.

Un sottoinsieme X dell'insieme dei numeri naturali è ricorsivamente enumerabile, brevemente r.e., se esiste un semialgoritmo --- ossia: una procedura che può non terminare su certi input --- che, preso in input un numero naturale n, restituisce entro un tempo finito il valore 1 se n appartiene a X, e restituisce il valore 0, oppure non termina, se n non appartiene a X.
Le seguenti sono equivalenti:
- X è r.e.;
- X è vuoto, oppure è il dominio di una funzione ricorsiva parziale;
- X è vuoto, oppure è l'immagine di N mediante una funzione ricorsiva totale.
Qualche regola:
- l'unione e l'intersezione di un numero finito di insiemi r.e. sono r.e.;
- se il complementare di un insieme r.e. è a sua volta r.e., allora l'insieme è ricorsivo;
- l'unione di una quantità numerabile di insiemi r.e. è r.e..

Ad esempio...

{x | phi ( x ) è definita su esattamente x argomenti}

o

{x | phi ( x ) è definita su almeno x argomenti }

o

{x | phi ( x ) vale 10 su esattamente x argomenti distinti}

Che cos'è phi?

[KuWa]

Originariamente inviato da Ziosilvio

Un sottoinsieme X dell'insieme dei numeri naturali è ricorsivo se esiste un algoritmo che, preso in input un numero naturale n, restituisce entro un tempo finito il valore 1 se n appartiene a X, e il valore 0 se n non appartiene a X.
Equivalentemente: X è ricorsivo se e solo se è ricorsiva la sue funzione caratteristica.
Qualche regola:
- il complementare di un insieme ricorsivo è ricorsivo;
- l'unione e l'intersezione di un numero finito di insiemi ricorsivi sono ricorsive;
- l'unione e l'intersezione di un numero infinito di insiemi ricorsivi non sono necessariamente ricorsive.

Un sottoinsieme X dell'insieme dei numeri naturali è ricorsivamente enumerabile, brevemente r.e., se esiste un semialgoritmo --- ossia: una procedura che può non terminare su certi input --- che, preso in input un numero naturale n, restituisce entro un tempo finito il valore 1 se n appartiene a X, e restituisce il valore 0, oppure non termina, se n non appartiene a X.
Le seguenti sono equivalenti:
- X è r.e.;
- X è vuoto, oppure è il dominio di una funzione ricorsiva parziale;
- X è vuoto, oppure è l'immagine di N mediante una funzione ricorsiva totale.
Qualche regola:
- l'unione e l'intersezione di un numero finito di insiemi r.e. sono r.e.;
- se il complementare di un insieme r.e. è a sua volta r.e., allora l'insieme è ricorsivo;
- l'unione di una quantità numerabile di insiemi r.e. è r.e..

Che cos'è phi?

phi (x) è una funzione totale di indice x... cmq quelle cose le so già ma risolvere esercizi è un altro paio di maniche.. nel libro non c'è un esempio e il mio prof è furio honsell che non sa niente...

[Ziosilvio]

Originariamente inviato da KuWa

phi (x) è una funzione totale di indice x

Ossia: è la x-esima funzione ricorsiva totale in una opportuna enumerazione di Goedel? Dico bene?
Oppure è la x-esima funzione ricorsiva parziale?

(In questo caso, forse ti conviene scrivere phi{x}(n), in modo da far capire che x è l'indice ed n l'argomento.)

[KuWa]

Originariamente inviato da Ziosilvio

Ossia: è la x-esima funzione ricorsiva totale in una opportuna enumerazione di Goedel? Dico bene?
Oppure è la x-esima funzione ricorsiva parziale?

(In questo caso, forse ti conviene scrivere phi{x}(n), in modo da far capire che x è l'indice ed n l'argomento.)

è la prima

[Ziosilvio]

Originariamente inviato da KuWa

è la prima

Quand'è così:

{x | phi ( x ) è definita su esattamente x argomenti}

x è finito e phi{x} è totale, quindi...

{x | phi ( x ) è definita su almeno x argomenti}

Si ragiona in modo simile a prima.

{x | phi ( x ) vale 10 su esattamente x argomenti distinti}

A naso, direi che dal Teorema di Rice segue che l'insieme è non ricorsivo.
Ma ci vorrei riflettere un po'.