1) Descrivere il concetto di macchina di Turing :

Si tratta di una astrazione concettuale basata sull´osservazione di come l´uomo risolve i problemi.

 

2) Descrivere il modello fisico della macchina di Turing :

Essa è costituita da :

a) un organo di controllo nel quale è presente un programma da eseguire e l´organo esecutore che si occupa degli   spostamenti.

b) un nastro illimitato avente funzione di memoria suddiviso in tante caselle ognuna delle quali può contenere un simbolo,    sul nastro possono trovar posto un n° finito di simboli non blank ed un restante infinito di simboli blank.

 

3) Quali operazioni sono concesse alla macchina di Turing :

Sono concesse 4 operazioni di cui tutte implementate dalla T.L.S. cioè dalla testina di lettura e scrittura :

a) leggere il simbolo presente nella cella attuale del nastro

b) Scrivere un simbolo nella cella attuale cancellando automaticamente il simbolo che vi era precedentemente scritto.

c) Spostarsi sulla prossima cella a sinistra del nastro.

d) Spostarsi sulla prossima cella a destra del nastro.

 

4) Come si estrinseca il funzionamento di una macchina di Turing :

Tramite una matrice siffatta :

Righe     Þ           sono tutti i possibili stati in cui la m.d.T. può trovarsi.

Colonne Þ           sono tutti i possibili simboli che la m.d.T. può incontrare.

" combinazione d´ingresso costituita dal prodotto cartesiano stato attuale ^X  simbolo incontrato , si ha nella intersezione della matrice una terna che rappresenta l´output della attuale passo di elaborazione, costituita da :

a)            simbolo da sostituire al simbolo letto.

b)            nuovo stato che la macchina deve assumere.

c)            posizione del prossimo simbolo da analizzare.

 

5) Descrivere il modello algebrico della macchina di Turing :

Secondo questo modello la m.d.T. non è che una terna costituita da :

a) Q        Þ           Insieme finito degli stati

b) S        Þ           Insieme finito dei simboli

c) P         Þ           Sottoinsieme della insieme delle quintuple formate da :

                                               c,a)         Þ           stato attuale

                                               c,b)         Þ           simbolo attuale

                                               c,c)         Þ           simbolo da sostituire al simbolo attuale

                                               c,d)         Þ           nuovo stato

                                               c,e)         Þ           spostamento da effettuare per leggere il successivo simbolo.

 

6) Cosa si intende per configurazione istantanea di una macchina di Turing:

È una stringa in grado di estrinsecare la condizione della macchina di Turing in un dato istante. A partire da una configurazione istantanea di partenza si può giungere alla configurazione finale tramite l´utilizzo della matrice funzionale ed il conseguente aggiornamento della configurazione istantanea.

Una configurazione istantanea è una stringa siffatta :                                h q_I s_K x            dove :

h             Þ           è la stringa significativa di nastro che precede la cella letta attualmente

q_I            Þ           è lo stato in cui attualmente si trova la macchina di Turing

s_K                  Þ           è il simbolo attualmente letto

x              Þ           è la stringa significativa di nastro che segue la cella letta attualmente. 

7) Cosa si intende per computazione di una macchina di Turing:

È una sequela di descrizioni istantanee che a partire dalla descrizione istantanea iniziale porta ad uno stato finale.

 

8) Schema per la progettazione di un algoritmo con la macchina di Turing :

a) Trovare la più semplice configurazione iniziale tale che applicandole la algoritmo siamo in grado di dire che funziona.

b) Progettare un algoritmo che risolva il problema semplicemente lavorando sulla stringa.

                * Individuare chiaramente la condizione di chiusura della algoritmo e di eventuali cicli interni.

c) Provare la algoritmo sulla stringa campione.

 

9) Enunciare la tesi di Church :

Se un problema ammette una risoluzione algoritmica, allora ne ammette una espressa da una macchina di Turing (previa codifica dei dati).

 

10) Esistono problemi insolubili:

Si, un esempio è la algoritmo della fermata

 

11) Quali sono le caratteristiche di un algoritmo:

a)            deve essere descrivibile con un n° finito di istruzioni.

b)            non ci deve essere un limite ne al n° di dati in ingresso ne al n° di dati in uscita.

c)            le istruzioni non debbono essere ambigue.

d)            la complessità delle istruzioni deve avere un limite finito.

e)            l´esecutore deve avere a disposizione una memoria illimitata per memorizzare i dati.

f)             la algoritmo deve terminare dopo un n° finito di passi.

 

12) Quando un algoritmo è più complesso di un altro:

Un algoritmo è più complesso se è meno efficiente dove l´efficienza viene quantificata prendendo in considerazione la quantità di risorse (memoria + tempo di esecuzione) che vengono impegnate.

 

13) Quando un problema è trattabile:

Quando esiste un algoritmo che lo risolva in termini polinomiali.