Esempi di diagrammi di macchine di Turing.
Uno strumento, quattro richieste. Ogni disegno qui sotto è un risultato reale.
Che cos'è un diagramma di macchina di Turing.
Un diagramma di macchina di Turing è un diagramma di stato per una macchina che legge e scrive simboli su un nastro illimitato. Un'etichetta di transizione indica normalmente lettura/scrittura/movimento, ad esempio 1/0,L: leggi 1, scrivi 0 e sposta la testina a sinistra.
Il diagramma identifica gli stati di controllo e l'operazione sul nastro che seleziona ogni stato successivo. Gli stati di arresto accettante e rifiutante rendono esplicito il risultato del calcolo.
- Standard
- OMG UML 2.5.1 §14 + Harel (1987) statechart
- Engine
- schematex-state
- Editable
- Double-click text, drag nodes
- Export
- SVG · PNG · PDF
Chi usa i diagrammi delle macchine di Turing.
Piccole macchine unarie per esercitarsi nella lettura della funzione di transizione e nelle operazioni sul nastro.
Algoritmi di marcatura che riconoscono linguaggi come a^n b^n, oltre gli automi finiti.
Scansioni del nastro in due fasi che mostrano come una macchina passa da un blocco di input all'altro.
Come creare un diagramma di macchina di Turing in tre passaggi.
Descrivilo
Basta un paragrafo per iniziare.
Guarda il disegno
Realizzato con il motore più adatto.
Indica cosa cambiare
Ogni modifica viene salvata come versione.
Domande frequenti
Che cosa mostra l'etichetta di una transizione di una macchina di Turing?
Mostra il simbolo letto sul nastro, quello scritto e la direzione in cui si muove la testina. Per esempio, 1/B,R significa: leggi 1, scrivi il bianco e spostati a destra.
Come vengono mostrati gli stati di accettazione e rifiuto?
Uno stato accettante è uno stato finale di arresto, solitamente rappresentato con un doppio cerchio. Si può includere uno stato di rifiuto separato quando la macchina deve mostrare un arresto negativo esplicito.
Come descrivo una macchina di Turing?
Indica l'alfabeto di input, il linguaggio o il compito, poi descrivi cosa fa la macchina in ogni fase: cosa legge, scrive, su cosa si sposta e quando si arresta.
Che cosa significano L, R e S?
Sono movimenti della testina: L sposta a sinistra, R sposta a destra e S lascia la testina sulla cella corrente del nastro.
Un diagramma di macchina di Turing può mostrare un algoritmo di marcatura?
Sì. Indica i simboli di marcatura e spiega quali simboli di input vengono associati o ignorati. Il diagramma di stato può mostrare le fasi di scansione, marcatura, ritorno e verifica.
Altri diagrammi per lo stesso lavoro.
Disegna subito la tua prima macchina di Turing.
Account gratuito, nessuna carta. Descrivi il calcolo e visualizza il diagramma di stato in meno di un minuto.
Apri l'editor