Macchina di Turing

di il
3 risposte

Macchina di Turing

Mi devo esercitare su problemi risolvibili con la MdT. Riesco a costruire la tabella di comportamento per vari esercizi che trovo sul libro, mi incarto sempre in situazioni in cui devo contare qualcosa, ad esempio:
programmare una MdT che scriva si sul nastro se la stringa sul nastro è composta da tante x quante y, no altrimenti
oppure:
programmare una MdT che conti quante volte compare la cifra 1 in un numero binario

Non ho idea di come contare, aspetto suggerimenti

3 Risposte

  • Re: Macchina di Turing

    Te lo scrivo in pseudocodice:
    
    int contatoreX = 0;
    int contatoreY = 0;
    
    for( int i=0; i<=numero di elementi; i++){
     SE (l'elemento == 'x') contatoreX++;
     ALTRIMENTI SE (l'elemento== 'y') contatoreY++;
    } fine for
    
    SE (contatoreX == contatoreY) scrivi si
    ALTRIMENTI scrivi no
    
  • Re: Macchina di Turing

    Scusa, ma la mdt non la programmate piu' con la tabella degli stati?

    La mitica tabella <stati>*<simboli> contenente la tripla (nuovo stato, simbolo da scrivere, direzione movimento testina)?

    ?
    Comunque, la mdt e' un automa a stati. puoi iniziare a costruire l'automa, poi lo converti.

    Certo, devi anche immaginare l'algoritmo da utilizzare.

    Ma come dice la tesi di Church:

    ogni funzione intuitivamente computabile, e' computabile
  • Re: Macchina di Turing

    Infatti io uso la tabella del comportamento o degli stati, che associa ad coppia simbolo_letto + stato_attuale, una terna nuovo_simbolo, nuovo_stato, movimento_tls
    Il problema è: è possibile salvarsi un valore oppure devo creare un tot di stati diversi per contemplare tutti i valori possibili?
Devi accedere o registrarti per scrivere nel forum
3 risposte