Macchina di Turing

di
luigibana96
il
3 risposte
L
luigibana96
Utente Attivo
Iscritto da
mar, 2013
Messaggi:
67

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

  • S
    spaccaversi7
    Pochi posts
    Iscritto da
    mar, 2013
    Messaggi:
    47

    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
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6034

    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
  • L
    luigibana96
    Utente Attivo
    Iscritto da
    mar, 2013
    Messaggi:
    67

    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