• Non ci sono risultati.

Se non diversamente detto, tutte le funzioni sono dai naturali nei naturali.

N/A
N/A
Protected

Academic year: 2021

Condividi "Se non diversamente detto, tutte le funzioni sono dai naturali nei naturali."

Copied!
2
0
0

Testo completo

(1)

Corso di Logica Matematica

Anno accademico 2008/2009

Teoria della computabilit` a (I parte)

Esercizi

Se non diversamente detto, tutte le funzioni sono dai naturali nei naturali.

1. Dimostrare che, fissato k, la funzione f (x) = k `e ricorsiva primitiva.

2. Dimostrare che funzione f (x) = p(x), dove p `e un polinomio fissato, `e ricorsiva primitiva.

3. Sia f una funzione primitiva ricorsiva. Dimostrare in maniera formale che la funzione g, definita mediante

g(0, x) = x

g(n, x) = f ◦ f ◦ . . . ◦ f (x) ,

dove la composizione `e fatta n volte, `e anch’essa ricorsiva primitiva . 4. Dimostare in maniera formale che la funzione f (x) = 2

x

`e ricorsiva

primitiva.

5. Dimostrare in maniera formale che la funzione che calcola il fattoriale

`e ricorsiva primitiva.

6. Dimostrare in maniera formale che la funzione f (x) =

Pxy=0

y `e ricorsiva primitiva.

1

(2)

7. Si dimostri che non pu`o esistere una enumerazione f

0

, f

1

, f

2

, . . . di tutte le funzioni totali.

8. Si dimostri che, per ogni i, esistono infiniti indici j tali che φ

i

= φ

j

. 9. Dimostrare che esiste una funzione f : N

2

−→ N ricorsiva (totale) tale

che

φ

f (i,j)

(x) = φ

i

(x) + φ

j

(x)

dove la somma `e definita su x solo se sia φ

i

(x) che φ

j

(x) sono definite.

10. Sia A = {i | φ

i

`e totale}. Si dimostri che non esiste alcuna funzione ricorsiva (totale) il cui codominio coincide con A.

11. Sia A = codf , dove f `e definita da f (0) = n

0

f (n + 1) = 2f (n) , con n

0

valore fissato. Dire se A `e ricorsivo o r.e. .

2

Riferimenti

Documenti correlati

“ Sei nomi di animali Classe 1C 17/18 ” La lunghezza dei rettangoli indica quante volte gli animali di una cate- goria sono stati scelti dagli alunni. Le categorie considerate

I simboli con si identificano con 0 ed indicano lo zero di. Dati due numeri si ha a<b se b-a è positivo, dove si ricorda che un numero razionale è positivo se pq è positivo.

•Le trasformazioni fatte dall’uomo. Chi è lo scienziato

E' il tritone di maggiori dimensioni presente nel territorio italiano, la lunghezza degli adulti è in media di 10 – 15 cm con un massimo di 21 cm, le femmine come nella maggior

Per ciascuna delle seguenti relazioni stabilire se si tratta di una funzione e, incaso aermativo, se sono iniettive, suriettive, bigettive.. Ad ogni persona vivente corrisponde

 A differenza dell’analisi morfologica che studia le componenti significative di una parola, l’analisi del lessico studia il significato delle parole e delle relazioni

Se non diversamente detto, tutte le funzioni sono dai naturali nei naturali5. Dimostrare che l’insieme delle funzioni ricorsive

Si parla infatti dei numeri interi, dei numeri decimali che ci aiutano a fare i conti con la spesa, delle unità di misura che ci permettono di misurare le diverse grandezze con le