Macchine di Turing Flashcards
(21 cards)
Cos’è derivazione μ-ricorsiva?
Derivazione ricorsiva primitiva piu min. lim di funzioni regolari
Funzione μ-ricorsiva è computabile?
posso ottenere
- funzione rp (dimostrato precedentemente)
- fun reg per minimalizzazione limitata (reg = esiste y quindi scorro y fino a trovare il corretto)
Tesi di Church (μ-ricorsiva)
Le funzioni $\mu$-ricorsive sono tutte e sole le funzioni computabili
Come è definita una macchina di Turing?
stato attuale x simbolo letto x azione (scorrimento o scrittura) x nuovo stato
funzionale in (stato attuale, simbolo letto) -> una sola coppia output
Funzione τ-ricorsiva
Una funzione τ-ricorsiva è una funzione per cui esiste MdT che la calcola.
Tesi di Church (τ-ricorsiva)
Le funzioni τ-ricorsive sono tutte e sole le funzioni computabili
Definizione di stringa e linguaggio accettato, ricorsivamente enumerabile e ricorsivo
Stringa è elemento di Sigma*. Si dice accettata quando termina per stato finale
Linguaggio accettato= insieme stringhe accettate
Se Mdt accetta L, L ricorsivamente enumerabile (possono esserci stringhe che non fanno terminare)
L ricorsivo quando è Mdt accetta (o RIFIUTA) terminando
L ric. enum <-> M semidecidibilie
L ricorsivo <-> M Decidibile
Stringa accettata per arresto
Una stringa è accettata per arresto se la macchina di Turing si ferma su di essa. (altrimenti va in loop)
Definizioni di linguaggio sono equivalenti?
M arresto -> M stati finali (basta mettere tutti gli stati in finali)
M stati finali -> M arresto (in stati non finali si mette loop)
MdT multitraccia
Una macchina di Turing multitraccia utilizza più nastri per la computazione e una sola “puntina”
Linguaggio accettato da MdT standard ≡ Linguaggio accettato da MdT multitraccia
->) Mdt standard è Mdt a 1 traccia
<-) Creo alfabeto formato da tutte le stringhe
MdT limitata a sx
Il nastro è infinito solo a destra
Linguaggio accettato da MdT standard ≡ Linguaggio accettato da MdT limitata a sx
<-) ovvio perchè MdT standard che non usa destra (metto simbolo di terminazione nastro)
->) ripiego nastro standard in 2 e ottengo a due tracce (codifica informazione nastro e aggiungo insieme di stati in modo da tenerne conto)
MdT multinastro
piu nastri con testina che si muove indipendentemente
Linguaggio accettato da MdT standard ≡ Linguaggio accettato MdT
->) ovvio (a 1 nastro)
<-)creo mdt a 2k+1 tracce (es.k=2 nastro1, testina1, nastro2, testina2, simbolo di limite)
insieme di stati devono codificare (stato, fase simulazione, contenuto letto nei vari nastri, cosa bisogna fare in ogni nastro, unknown per cose che non conosciamo)
Esempio MdT multinastro
MdT che determina se è quadrato perfetto (nastro 3 k incrementale, nastro 2 genero stringhe di k^2 (aggiungo 1 + 2k, nastro 1 input)
MdT non deterministico
Una MdT non deterministica può avere più di una transizione per ogni stato e simbolo.(ovvero le quartuple non sono funzionali nei primi due argomenti)
MdT det è caso particolare di MdT NON det
Linguaggio accettato da MdT non deterministica
Accetta stringa quando ESISTE computazione che accetta)
Grado di non-determinismo
massimo numero di transizioni diverse possibili su (iniziale, letto)
Esempio per δ=3
Un esempio per δ=3 è una MdT non deterministica che ha tre transizioni possibili per uno stato.
L accettato da MdT deterministica ⇔ L accettato da MdT non deterministica
-> ovvia (det e sottocaso di Mdt non det)
<- Usiamo MdT a 3 nastri per arresto
Scriviamo computazione su nastro 3
simuliamo su nastro 2
nastro 1input
