Fondamenti
Ciao a tutti, posto un esercizio di fondamenti sperando di ricevere una piccola dritta.
Classificare nella teoria matematica della ricorsione il seguente insieme ed il suo complemento:
$H = {x in NN | Wx = (5NN+10) nn (15NN+20)}$
Quindi, diciamo che un elemento x appartiene all'insieme se il programma x preso in input i valori descritti dall'insieme sopra converge, ma questi insiemi sono infiniti e per rispondere dovrei provare su tutti gli input.
Questa cosa mi porta a dire che l'insieme non è ricorsivamente enumerabile, e a dimostrare che è produttivo.
E' vero o sbaglio tutto??
Ho un pò di casino sugli appunti, ad esempio riguardo l'utilizzo dell'algoritmo dovetail...
Qualcuno sarebbe in grado di illuminarmi?
Grazie!
Classificare nella teoria matematica della ricorsione il seguente insieme ed il suo complemento:
$H = {x in NN | Wx = (5NN+10) nn (15NN+20)}$
Quindi, diciamo che un elemento x appartiene all'insieme se il programma x preso in input i valori descritti dall'insieme sopra converge, ma questi insiemi sono infiniti e per rispondere dovrei provare su tutti gli input.
Questa cosa mi porta a dire che l'insieme non è ricorsivamente enumerabile, e a dimostrare che è produttivo.
E' vero o sbaglio tutto??
Ho un pò di casino sugli appunti, ad esempio riguardo l'utilizzo dell'algoritmo dovetail...
Qualcuno sarebbe in grado di illuminarmi?
Grazie!
Risposte
Sarei interessato anch'io all'argomento se qualcuno sa rispondere.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo