...

Esercizi sulla Computabilità

by user

on
Category: Documents
0

views

Report

Comments

Transcript

Esercizi sulla Computabilità
Università di Udine, Facoltà di Scienze della Formazione
Corso di Informatica Applicata alla Didattica
(Giorgio T. Bagni)
Esercizi sulla Computabilità
1. Esercizio risolto. Si dica con quante operazioni aritmetiche può essere
calcolata la funzione f: N→N che ad ogni naturale n fa corrispondere il numero
naturale:
f(n) =
n
n
i =1
i =1
∑ i + ∑ i 2 = 1+2+3+...+n+1²+2²+3²+...+n²
In base a ciò, si dica se la funzione f è computabile.
Risoluzione. Assegnati il naturale n, f(n) può essere calcolata con:
•
•
•
•
n−1 addizioni;
n−1 moltiplicazioni (per calcolare le seconde potenze di ogni i, 2 ≤ i ≤
n) – eventualmente una di più se si vuole calcolare il quadrato di 1…;
n−1 addizioni;
un'addizione, per addizionare finalmente le due sommatorie.
Pertanto f(n) può essere calcolata con 3n−2 operazioni.
Ricordiamo che una funzione N→N, n→f(n) viene detta computabile se
esiste, per ogni naturale n, un procedimento mediante il quale calcolare f(n) in
un numero finito di passaggi: pertanto l'assegnata funzione f è computabile. „
2. Si dica con quante operazioni aritmetiche può essere calcolata la funzione f:
N→N che ad ogni naturale n fa corrispondere il numero naturale:
f(n) = 5⋅(n²+5n+7)+1
In base a ciò, si dica se la f è computabile.
[6 operazioni; è computabile]
1
3. Si dica con quante operazioni aritmetiche può essere calcolata la funzione f:
N→N che ad ogni naturale n fa corrispondere il numero naturale:
f(n) =
∑ (i 2 + i + 1)
n
i =1
In base a ciò, si dica se la funzione f è computabile.
4. Si dica con quante operazioni aritmetiche può essere calcolata la funzione f:
N→N che ad ogni naturale n fa corrispondere il numero naturale:
f(n) =
∑ (2i 2 + 5)
n
i =1
In base a ciò, si dica se la funzione f è computabile.
6. Si dica con quante operazioni aritmetiche può essere calcolata la funzione f:
N→N che ad ogni naturale n fa corrispondere il numero naturale:
n
n+1
i =1
i =1
f(n) = ∏ i + ∏ (2i + 7 )
In base a ciò, si dica se la funzione f è computabile.
7. Esercizio risolto. Si considerino le seguenti istruzioni:
istruzione D
istruzione S
istruzione N
istruzione α
istruzione Sk
istruzione Sαk
istruzione A
la testina si sposta verso destra;
la testina si sposta verso sinistra;
la testina non si sposta;
la testina cancella il simbolo attualmente nella
cella di lettura e sostituisce ad esso il simbolo α;
il programma prosegue con la k-esima istruzione;
il programma prosegue con la k-esima istruzione
se e solo se il simbolo attualmente nella cella di
lettura è α;
arresto.
Consideriamo una macchina di Turing e scriviamo un programma tale che:
2
•
•
la macchina si sposti a sinistra cancellando, di volta in volta, tutti i
simboli presenti nelle celle e scrivendo, in ogni cella, il simbolo δ;
tutto ciò dovrà accadere finché la testina non leggerà, in una cella, il
simbolo γ: a questo punto il funzionamento della macchina di Turing
dovrà arrestarsi.
Risoluzione
Il programma richiesto è il seguente:
(istruzione 1)
(istruzione 2)
(istruzione 3)
(istruzione 4)
(istruzione 5)
δ
S
Sγ5
S1
A „
8. Con riferimento alla lista di istruzioni riportata nel testo dell'esercizio risolto
7, si consideri una macchina di Turing e si scriva un programma tale che:
•
•
la macchina si sposti a destra occupando sei celle (compresa l'iniziale),
cancellando, di volta in volta, tutti i simboli presenti nelle celle e
scrivendo uno dopo l'altro, nelle sei celle sequenzialmente occupate, i
simboli: T, U, R, I, N, G;
fatto ciò, la macchina dovrà arrestarsi.
[(istruzione 1) T; (istruzione 2) D;
(istruzione 3) U; (istruzione 4) D;
(istruzione 5) R; (istruzione 6) D;
(istruzione 7) I; (istruzione 8) D;
(istruzione 9) N; (istruzione 10) D;
(istruzione 11) G; (istruzione 12) A]
9. Con riferimento alla lista di istruzioni riportata nel testo dell'esercizio risolto
7, si consideri una macchina di Turing e si scriva un programma tale che:
•
la macchina si sposti a destra cancellando, di volta in volta, tutti i
simboli presenti nelle celle e scrivendo, in ogni cella, alternativamente i
simboli α e β;
3
•
tutto ciò dovrà accadere finché la testina non leggerà, in una cella, il
simbolo ω: a questo punto la testina si sposterà a sinistra di una cella e
il funzionamento della macchina dovrà quindi arrestarsi.
10. Con riferimento alla lista di istruzioni riportata nel testo dell'esercizio
risolto 7, si consideri una macchina di Turing e si scriva un programma tale
che:
•
•
la macchina si sposti a destra cancellando, di volta in volta, tutti i
simboli presenti nelle celle e scrivendo, in ogni cella, alternativamente i
simboli α e β;
tutto ciò dovrà accadere finché la testina non leggerà, in una cella, il
simbolo ω: a questo punto la testina si sposterà per due volte a destra di
una cella, cancellando, entrambe le volte, i simboli presenti nelle celle e
scrivendo, in ogni cella, il simbolo λ; il funzionamento della macchina
dovrà quindi arrestarsi.
4
Fly UP