Il computer che vinse la guerra / Alan Turing.

« Older   Newer »
 
  Share  
.
  1. maia
     
    .

    User deleted


    Condividi

    Video

    Video

    La macchina può agire sopra un nastro che si presenta come una sequenza di caselle nelle quali possono essere registrati simboli di un ben determinato alfabeto finito; essa è dotata di una testina di lettura e scrittura (I/O) con cui è in grado di effettuare operazioni di lettura e scrittura su una casella del nastro. La macchina si evolve nel tempo e ad ogni istante si può trovare in uno stato interno ben determinato facente parte di un insieme finito di stati. Inizialmente sul nastro viene posta una stringa che rappresenta i dati che caratterizzano il problema che viene sottoposto alla macchina. La macchina è dotata anche di un repertorio finito di istruzioni che determinano la sua evoluzione in conseguenza dei dati iniziali. L'evoluzione si sviluppa per passi successivi che corrispondono a una sequenza discreta di istanti successivi. Le proprietà precedenti sono comuni a molte macchine formali (automa a stati finiti, automa a pila, ...). Caratteristica delle MdT è quella di disporre di un nastro potenzialmente infinito, cioè estendibile quanto si vuole qualora questo si renda necessario.

    Ogni passo dell'evoluzione viene determinato dallo stato attuale s nel quale la macchina si trova e dal carattere c che la testina di I/O trova sulla casella del nastro su cui è posizionata e si concretizza nell'eventuale modifica del contenuto della casella, nell'eventuale spostamento della testina di una posizione verso destra o verso sinistra e nell'eventuale cambiamento dello stato. Quali azioni vengono effettuate ad ogni passo viene determinato dalla istruzione, che supponiamo unica, che ha come prime due componenti s e c; le altre tre componenti dell'istruzione forniscono nell'ordine il nuovo stato, il nuovo carattere e una richiesta di spostamento verso sinistra, nullo o verso destra.

    Una evoluzione della macchina consiste in una sequenza di sue possibili "configurazioni", ogni configurazione essendo costituita dallo stato interno attuale, dal contenuto del nastro (una stringa di lunghezza finita) e dalla posizione sul nastro della testina di I/O. Nei casi più semplici l'evoluzione ad un certo punto si arresta in quanto non si trova nessuna istruzione in grado di farla proseguire. Si può avere un arresto in una configurazione "utile" dal punto di vista del problema che si vuole risolvere; in tal caso quello che si trova registrato sul nastro all'atto dell'arresto rappresenta il risultato dell'elaborazione. Si può avere però anche un arresto "inutile" che va considerato come una conclusione erronea dell'elaborazione. Va subito detto che può anche accadere che un'evoluzione non abbia mai fine (Vedi la successiva sezione e Problema della fermata).

    Impostazione formale[modifica | modifica wikitesto]
    Si definisce macchina di Turing deterministica a un nastro e istruzioni a cinque campi, termine che abbreviamo con MdT1n5i, una macchina formale della seguente forma:

    T = \langle S,s_0,F,A,\beta,\delta \rangle \quad \mbox{dove}
    S è un insieme finito detto insieme degli stati della macchina;

    s_0 è un elemento di S detto stato iniziale della T;

    F è un sottoinsieme di S detto insieme degli stati finali della T;

    A è un alfabeto finito detto alfabeto del nastro della T

    \beta è un carattere dell'alfabeto A detto segno di casella vuota del nastro della T

    \delta ~:~ S \times A \to S \times A \times \{-1,0,+1\} è detta funzione di transizione della macchina.

    Se \delta(s,a)=\langle t,b,m\rangle, la corrispondente quintupla \langle s,a,t,b,m\rangle può considerarsi come l'istruzione che viene eseguita quando la macchina si trova nello stato s e la testina di I/O legge a sulla casella sulla quale è posizionata; essa comporta la transizione allo stato t, la scrittura del carattere b e:

    quando m = -1 lo spostamento della testina di una posizione a sinistra,
    quando m = 0 nessuno spostamento della testina,
    quando m = +1 lo spostamento della testina di una posizione a destra.

    http://it.wikipedia.org/wiki/Macchina_di_Turing
     
    .
0 replies since 13/2/2015, 12:36   77 views
  Share  
.