Insieme dei numeri primi

[*missdreamer*12]

Come potrei fare per dimostrare che l'insieme dei numeri primi è ricorsivo?

Da qui mi nasce anche un'altra domanda... io conosco definizioni di ricorsività per funzioni e predicati, da queste dovrei ricavarmi la definizione di ricorsività di un insieme? Oppure per dimostrare che l'insieme dei numeri primi è ricorsivo dovrei considerare un predicato o una funziona che lo caratterizzi e quindi dimostrare la sua ricorsività?

Grazie

[carlo232]

"*missdreamer*":Come potrei fare per dimostrare che l'insieme dei numeri primi è ricorsivo?

Un insieme $A$ è ricorsivo se è un sottoinsieme di $NN$ per cui sia possibile costruire un algoritmo che preso in input un qualsiasi elemento di $ZZ$ in tempo finito restituisca come output se tale elemento appartiene o no ad $A$.

Quindi l'insieme dei numeri primi è banalmente ricorsivo, preso un intero $a$ possiamo verificare con facilità se sia primo calcolando $|{d in NN et d<=a: d|a}|$

[*missdreamer*12]

purtroppo temo non sia la risposta al mio quesito... nel senso che io devo dimostrare che l'insieme dei numeri primi è ricorsivo in modo formale.. dal punto di vista logico... e così non riesco a formalizzare... sapresti aiutarmi? grazie

[fields1]

Oppure per dimostrare che l'insieme dei numeri primi è ricorsivo dovrei considerare un predicato o una funziona che lo caratterizzi e quindi dimostrare la sua ricorsività?

Esatto.

Ma qual è il formalismo che usi? Quello delle funzioni primitive ricorsive che si possono definire per composizione e ricorsione primitiva?

[*missdreamer*12]

esattamente quel formalismo!

[fields1]

Ti basta definire la funzione f(x,y)=1 se y divide x, f(x,y)=0 altrimenti. Poi definisci la funzione fattoriale f(x)=x!. Poi usi il teorema di Wilson: un numero e' primo se e solo se p divide (p-1)!+1.