Macchina di turing

6 Risposte

• 

  M.A.W. 1968

  Utente Attivo

  Iscritto da

  ott, 2011

  Messaggi:

  321

  Re: Macchina di turing

  20 gen 2017, 17:06

  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.
• A

  antcru

  Pochi posts

  Iscritto da

  mar, 2008

  Messaggi:

  38

  Re: Macchina di turing

  22 gen 2017, 14:57

  Grazie,
  ma se lo avessi saputo risolvere non avrei chiesto aiuto!
• 

  M.A.W. 1968

  Utente Attivo

  Iscritto da

  ott, 2011

  Messaggi:

  321

  Re: Macchina di turing

  22 gen 2017, 15:09

  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.
• A

  antcru

  Pochi posts

  Iscritto da

  mar, 2008

  Messaggi:

  38

  Re: Macchina di turing

  22 gen 2017, 15:21

  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!
• 

  M.A.W. 1968

  Utente Attivo

  Iscritto da

  ott, 2011

  Messaggi:

  321

  Re: Macchina di turing

  22 gen 2017, 15:44

  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.
• A

  antcru

  Pochi posts

  Iscritto da

  mar, 2008

  Messaggi:

  38

  Re: Macchina di turing

  22 gen 2017, 23:05

  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