Macchina di turing

di il
6 risposte

Macchina di turing

Salve a tutti,
qualcuno sa come risolvere il seguente esercizio?
Realizzare una macchina di turing che avendo in input una stringa di zero e uno dopo ogni zero inserisca il simbolo A e dopo ogni uno il simbolo B.
Es.
INPUT: 0010
OUTPUT: 0A0A1B0A

Grazie

6 Risposte

  • Re: Macchina di turing

    Il forum non fornisce soluzioni agli esercizi altrui. Se ti interessa ottenere aiuto, mostra innanzi tutto lo pseudocodice o altro prodotto nel tuo tentativo di soluzione.
  • Re: Macchina di turing

    Grazie,
    ma se lo avessi saputo risolvere non avrei chiesto aiuto!
  • Re: Macchina di turing

    Chi ha assegnato un simile esercizio necessariamente ha anche spiegato la teoria necessaria per risolverlo, o quantomeno fornito un riferimento su dove trovare le necessarie spiegazioni (visti i tempi che corrono).

    Dubito comunque che il docente si aspetti che tu scopra autonomamente la tesi di Church-Turing ripartendo da zero o cose del genere. Lo scopo è quindi quello di costringerti a studiare la teoria, e nessuno lo farà al posto tuo, anche perché noi abbiamo già dato abbondantemente, negli ultimi trent'anni.
  • Re: Macchina di turing

    Scusami,
    non voglio fare nessuna polemica con te.
    Certo che ci hanno spiegato la teoria e anche mostrato qualche esempio, ma sapere la teoria non significa saper risolvere l'esercizio.
    Sapere che la macchina è composta da un nastro infinito su cui è possibile scrivere e leggere tramite una testina e che ad ogni istante la macchina si trova in uno stato interno e che il successivo stato dipende da una funzione di transizione etc etc non mi aiuta a risolvere l'esercizio che avevo postato!
  • Re: Macchina di turing

    Devi provare a ragionare sulla logica dell'esercizio. Che cosa si chiede? Supponendo di avere la più semplice MdT a disposizione, dotata di una sola testina e di un singolo nastro (semi)infinito, sostanzialmente si chiede di copiare in output la sequenza di input, e questa è la versione base dell'esercizio. Quindi si tratta di un loop entro il quale si legge la prossima locazione in input, opportunamente inizializzata, si sposta la testina sulla prossima locazione di output libera e vi si scrive il carattere appena letto.
    Il programma termina quando non vi sono più caratteri in input.

    Una volta risolta questa versione, si può fare un ulteriore passo e aggiungere all'output i caratteri extra richiesti, sempre tenendo conto delle istruzioni atomiche che la MdT può eseguire.

    Un modello computazionale che può facilitare l'esercizio è la MdT a due testine, una di lettura e l'altra di scrittura, alle quali afferiscono due diversi nastri... ci si può sbizzarrire come si vuole (anche con una terza testina che legge solo le istruzioni, in readonly, con una vera topologia Harvard). Ma per il momento pensa solo alla versione più elementare.
  • Re: Macchina di turing

    Grazie per la risposta e la comprensione.

    Ho provato a ragionare partendo dai tuoi suggerimenti, ho prodotto questo, secondo te va bene?

    (S0, 0, S1, -) se nello stato S0 leggo 0 passo nello stato S1 e lo cancello(lo andrò a copiare alla fine e quando torno indietro parto dal secondo bit)
    (S1, -, S2, >) se nello stato S1 leggo vuoto passo nello stato S2 e sposto la testina a destra
    (S2, 0, S2, >) mi sposto alla prima cella vuota sia se leggo 0
    (S2, 1, S2, >) sia se leggo 1
    (S2, -, S3, >) se sono alla prima cella vuota vado avanti ancora di una
    (S3, -, S4, 0) se anche questa cella è vuota scrivo il simbolo letto inizialmente(che era uno zero)
    (S3, 0, S3, >) altrimenti significa che non è il primo simbolo che sto copiando e devo trovare una nuova cella vuota sia che leggo 0
    (S3, 1, S3, >) sia se leggo 1
    (S3, A, S3, >) sia se leggo A
    (S3, B, S3, >) sia se leggo B
    (S4, 0, S4, >) Se ho scritto 0 mi sposto di una cella avanti e
    (S4, -, S4, A) scrivo la A dopo lo zero che avevo scritto
    (S4, A, S5, <) torno indietro
    (S5, 0, S5, <) torno indietro
    (S5, 1, S5, <) torno indietro
    (S5, A, S5, <) torno indietro
    (S5, B, S5, <) torno indietro
    (S5, -, S6, <) ho trovato la cella vuota che mi delimita la stringa di input da quella di output
    (S6, 0, S6, <) torno ancora indietro fino ad arrivare nuovamente all'inizio della stringa di input che adesso è mutilata della prima cifra
    (S6, 1, S6, <)
    (S6, -, S0, >) riparto da S0 con la testina sul primo simbolo dell'input

    Tutto questo solo se avessi trovato,stando nello stato S0, come primo simbolo lo zero, se invece avessi trovato 1 da S0 mi spostavo in S7.
    (S0, 1, S7, -) Come la prima quadrupla solo che vado in S7 per ricordarmi che ho letto un 1 e cancello
    (S7, -, S8, >) se nello stato S1 leggo vuoto passo nello stato S2 e sposto la testina a destra
    (S8, 0, S8, >) mi sposto alla prima cella vuota sia se leggo 0
    (S8, 1, S8, >) sia se leggo 1
    (S8, -, S9, >) se sono alla prima cella vuota vado avanti ancora di una
    (S9, -, S10, 1) se anche questa cella è vuota scrivo il simbolo letto inizialmente(che era un 1)
    (S9, 0, S9, >) altrimenti significa che non è il primo simbolo che sto copiando e devo trovare una nuova cella vuota sia che leggo 0
    (S9, 1, S9, >) sia se leggo 1
    (S9, A, S9, >) sia se leggo A
    (S9, B, S9, >) sia se leggo B
    (S10,1,S10,>) Se ho scritto 1 mi sposto di una cella in avanti e
    (S10, -,S10,B) scrivo la B
    (S10, B,S5,<) torno indietro

    Lo vedo lungo e complesso, ma sembra funzioni, se puoi dammi un tuo parere.
    Grazie
Devi accedere o registrarti per scrivere nel forum
6 risposte