• Non ci sono risultati.

Computabilita’ 20 Febbraio 2007

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Computabilita’ 20 Febbraio 2007"

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

Computabilita’ 20 Febbraio 2007

NOME E COGNOME:

1. Si enunci e si dimostri il teorema del parametro.

2. Sia n un numero naturale e sia In = {k : φk = φn}. Esiste n tale che dom(φn) = In?

3. Si utilizzi il secondo teorema di ricorsione per provare che l’insieme A = {n : φn e’ una funzione strettamente parziale} non e’ decidibile.

Quali teoremi di Rice sono applicabili ad A ed al suo complementare?

4. Si determini il minimo punto fisso del funzionale associato alla seguente definizione ricorsiva f (x) = 0 se x = 0; f (f (x − 1)) altrimenti.

5. Si dimostri che un insieme infinito e’ decidibile se, e solo se, esiste un algoritmo che lo enumera in ordine strettamente crescente.

1

Riferimenti

Scarica adesso ( PDF - 1 pagine - 31.32 KB )

Documenti correlati

1/2, {an}n∈N`e strettamente crescente e lim n an

SEGNARE nella tabella riportata in questa pagina, in modo incontrovertibile, la lettera corrispondente alla risposta scelta per ognuna delle domande riportate nel foglio allegato;

Dimostrare che se E

Suggerimento: L’enunciato ` e ridondante, e la sua dimostrazione si pu` o semplificare di molto; in particolare, dal punto (g) discendono direttamente molti degli

Dimostrare che: (a) esiste in G uno ed un solo sottogruppo caratteristico K7 di ordine 7

Sessione estiva anticipata — I appello prova scritta del 24

0 quindi se e solo se cosh x | sinh x − 1| &gt

a) L’integranda ` e continua ed ha segno costante in [0, +∞), per cui la convergenza pu` o essere studiata mediante il criterio del confronto asintotico... esprimendole prima in

3. Provare che un insieme C ` e chiuso se e solo se ∂C ⊂ C.

[r]

COMPITO DI Calcolabilit`a e Linguaggi Formali 10 Maggio 2016

Si provi che un insieme infinito e’ decidibile sse puo’ essere enumerato in ordine stretta- mente crescente.. Soluzione Sia I decidibile

Si provi che se f e’ crecente su A e g e’crescente su C, allora g◦ f e’ crescente su A

Usando il fatto che la funzione logaritmo in base 10 e’ strettamente crescente, si dia l’approssimazione agli interi di log 10 ( 1234

Compito di Matematica Discreta I (20 febbraio 2007) Soluzioni Esercizio 1.

Nel caso di combinazioni semplici, una combinazione di classe 5 in cui compare l’elemento c si ottiene aggiungendo c ad una qualunque combinazione semplice di classe 4 dei restanti