• Non ci sono risultati.

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

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

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

Copied!
2
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 2 pagine )

Testo completo

(1)

Corso di Logica Matematica

Anno accademico 2007/2008

Teoria della computabilit` a (II parte)

Esercizi

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

1. Dimostrare che se A e B sono ricorsivi allora A ∪ B e A ∩ B sono ricorsivi.

2. Dimostrare che se A e B sono r.e. allora A ∪ B e A ∩ B sono r.e. . 3. Se A `e r.e. , dimostrare che esiste una funzione ricorsiva g t.c.

W

g(x)

=

 

 

N se x ∈ A

∅ se x 6∈ A

4. Dimostrare che l’insieme delle funzioni ricorsive `e numerabile.

5. Dimostrare che l’insieme delle funzioni r.e. `e numerabile.

6. Dimostrare che le funzioni ricorsive non possono essere enumerate.

7. Dimostrare che il range dela funzione f definita da f (0) = n

0

f (n + 1) = 2 ∗ f (n)

`e r.e. Dimostrare che `e anche ricorsivo.

1

(2)

8. L’insieme A = {c(i, x) | l’i-esima cifra dell’espansione decimale di π `e x}

`e r.e.? ` E ricorsivo?

9. Dimostrare che esiste un indice n t.c. W

n

= {n + 1, n + 2}.

10. Dimostrare che l’insieme {i | a ∈ φ

i

} , con a ∈ N fissato, `e infinito.

11. Dimostrare che l’insieme {i | a ∈ φ

i

} , con a ∈ N fissato, `e indecidibile.

12. Dimostrare che l’insieme {(i, j, k) | φ

i

= φ

j

◦ φ

k

} `e indecidibile.

13. Dimostrare che esiste una rappresentazione ricorsiva della propriet`a dotata di rappresentazione K = {i | φ

i

(i) ↓} .

14. Dimostrare che l’insieme {i | codφ

i

`e infinito} non `e r.e.

15. Dimostrare che l’insieme {i | W

i

`e finito} non `e r.e.

2

Riferimenti

Scarica adesso ( PDF - 2 pagine - 47.00 KB )

Documenti correlati

FUNZIONI COMUNI A TUTTE LE AREE

- Attività e procedimenti relativi al cerimoniale ed alla rappresentanza (es. ricevimenti di autorità, organizzazione di incontri ufficiali ed eventi di rilievo istituzionale, ecc.).

Abbiamo detto che questo `e un segno che le funzioni sono conformi, ma per il momento abbiamo solo dimostrato che le trasformazioni di M¨obius sono conformi

Mentre facciamo questo, i lati delle immagini dei trian- goli diventano sempre pi` u linee rette, mentre gli angoli, ovviamente, non cambiano.. Perci` o un triangolo infinitesimo

Sorgenti Naturali di Sorgenti Naturali di Radiazioni Radiazioni

caratterizzato dal numero atomico Z, che rappresenta il numero di protoni nel nucleo (uguale al numero degli elettroni dell'atomo neutro) e dal numero di. massa A che rappresenta

FUNZIONI LIMITATE E FUNZIONI CONTINUE

Se una funzione è continua in un intervallo chiuso [a,b], e se agli estremi dell’intervallo assume valori di segno opposto, essa si annulla in almeno un punto

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

Si dimostri che non esiste alcuna funzione ricorsiva (totale) il cui codominio coincide con

Funzioni Funzioni

● Per quelle che non restituiscono un valore si può usare “return” senza argomento, oppure ometterlo per terminare la funzione alla fine della funzione..

4) La ricorsione 4.1 Funzioni matematiche ricorsive

Analogamente, una funzione (o una procedura) viene detta ricorsiva quando all’interno del corpo della funzione vi è una chiamata alla funzione (o procedura)

Insieme di definizione di funzioni in due variabili

Tutoraggio Analisi