Pagina 1 di 1
Discussione esercizio 1 compito 4/11/2016
Inviato: 15/08/2019, 12:26
da frabert
Testo dell'esercizio:
Si determini una funzione [math]<math><mi>f</mi></math> calcolabile totale tale che [math]
<math>
<mrow>
<mi>I</mi>
<mo>=</mo>
<mrow>
<mo form="prefix">{</mo>
<mi>i</mi>
<mo>|</mo>
<msub>
<mi>φ</mi>
<mi>i</mi>
</msub>
<mo>=</mo>
<msub>
<mi>φ</mi>
<mrow>
<mi>f</mi>
<mrow>
<mo form="prefix">(</mo>
<mi>i</mi>
<mo form="postfix">)</mo>
</mrow>
</mrow>
</msub>
<mo form="postfix">}</mo>
</mrow>
</mrow></math> sia ricorsivo
L'unica funzione che mi viene in mente che possa soddisfare la condizione è l'identità, che renderebbe
[math]<math><mi>I</mi><mo>=</mo><mi>ℕ</mi></math>. Mi verrebbe da dire che qualsiasi altra funzioni renderebbe
[math]<math><mi>I</mi></math> un i.i.r.f. quindi non ricorsivo. Il mio ragionamento è corretto?
Re: Discussione esercizio 1 compito 4/11/2016
Inviato: 29/08/2019, 19:43
da michelezoncheddu
Il ragionamento mi sembra corretto, ma non saprei come formalizzare il fatto che diventi un i.i.r.f.
Re: Discussione esercizio 1 compito 4/11/2016
Inviato: 09/01/2020, 10:58
da andrea.tosti
frabert ha scritto: ↑15/08/2019, 12:26
Testo dell'esercizio:
Si determini una funzione [math]<math><mi>f</mi></math> calcolabile totale tale che [math]
<math>
<mrow>
<mi>I</mi>
<mo>=</mo>
<mrow>
<mo form="prefix">{</mo>
<mi>i</mi>
<mo>|</mo>
<msub>
<mi>φ</mi>
<mi>i</mi>
</msub>
<mo>=</mo>
<msub>
<mi>φ</mi>
<mrow>
<mi>f</mi>
<mrow>
<mo form="prefix">(</mo>
<mi>i</mi>
<mo form="postfix">)</mo>
</mrow>
</mrow>
</msub>
<mo form="postfix">}</mo>
</mrow>
</mrow></math> sia ricorsivo
L'unica funzione che mi viene in mente che possa soddisfare la condizione è l'identità, che renderebbe
[math]<math><mi>I</mi><mo>=</mo><mi>ℕ</mi></math>. Mi verrebbe da dire che qualsiasi altra funzioni renderebbe
[math]<math><mi>I</mi></math> un i.i.r.f. quindi non ricorsivo. Il mio ragionamento è corretto?
Io invece credo che prendendo una qualsiasi altra funzione, ad esempio
[math]f(i) = 2i, questa non appartenga a
[math]I e quindi
[math]I non è un
[math]I.I.R.F. (se prendo l'indice
[math]i_0 = 2 e l'indice
[math]i_1 = 3, l'indice
[math]i_0 è in
[math]I, l'indice
[math]i_1 non è in
[math]I, e magari entrambi gli indici calcolano la stessa funzione).