[computabilità] Macchine di Turing
Dalla definizione "formale" che mi trovo, tale macchina è definita come una $7-upla$ del tipo
$MT := < Q , \xi, \nabla , \delta, q_0, B, F>$.
Ove per $Q$ si intende i possibili stati della macchina, $\xi$ l'alfabeto della macchina, $\nabla$ l'alfabeto dell'imput , $\delta $ la funzione di transizione, $q_0$ stato iniziale, $B$ spazio vuoto ed $F $ l'insieme degli stati finali della MT.
Se ho ben capito, questa macchina ideale, in un certo senso imita il processo mentale di un uomo nell'eseguire un calcolo, giusto?!
Come nell'operare su di un nastro infinito che può essere associato al nostro cervello, e quello di compiere un'azione elementare per volta , per giungere ad un risultato. In particolare una $MT$ è fatta solo per eseguire un ben specifico compito.
Domanda, perché $Q$ deve essere necessariamente non vuoto?. Se non gli do istruzioni la macchina sta ferma e quindi non compie "lavoro", e quindi non c'è passaggio di stato. Ma quel non compiere lavoro è da intendersi che la macchina sta ferma nello stato di "stop", giusto? Quindi per questo motivo , anche se la macchina fosse ferma , $Q$ sarebbe non vuota.
Consideriamo $\nabla$ e $\xi$. Questi alfabeti in una MT possono essere infiniti o sono sempre prefissati in precedenza?.
Consideriamo una $MT $ che calcola il successore di un numero, $n$.
Se ho ben capito, l'algoritmo è il seguente :
1) se $n<9$ la macchina aggiunge 1.
2) se $n>9$ si sostituisce l'ultima cifra con 0 ed esaminare la precedente. Ripeterla finché non si determina $n+1$.
Quindi , per esempio, se la $MT$ di Turing vuole calcolare il successore di $2$
parte da un $q_0$ iniziale, che sarebbe , la testina ferma nella cella dove è posto il 2 , lo esamina, dopo che lo ha esaminato, decide se $<9$ , dopo di che somma 1 a 2, si sposta nella cella affianco, e "stampa " 3. Giusto?
Grazie per i vostri eventuali chiarimenti!
$MT := < Q , \xi, \nabla , \delta, q_0, B, F>$.
Ove per $Q$ si intende i possibili stati della macchina, $\xi$ l'alfabeto della macchina, $\nabla$ l'alfabeto dell'imput , $\delta $ la funzione di transizione, $q_0$ stato iniziale, $B$ spazio vuoto ed $F $ l'insieme degli stati finali della MT.
Se ho ben capito, questa macchina ideale, in un certo senso imita il processo mentale di un uomo nell'eseguire un calcolo, giusto?!
Come nell'operare su di un nastro infinito che può essere associato al nostro cervello, e quello di compiere un'azione elementare per volta , per giungere ad un risultato. In particolare una $MT$ è fatta solo per eseguire un ben specifico compito.
Domanda, perché $Q$ deve essere necessariamente non vuoto?. Se non gli do istruzioni la macchina sta ferma e quindi non compie "lavoro", e quindi non c'è passaggio di stato. Ma quel non compiere lavoro è da intendersi che la macchina sta ferma nello stato di "stop", giusto? Quindi per questo motivo , anche se la macchina fosse ferma , $Q$ sarebbe non vuota.
Consideriamo $\nabla$ e $\xi$. Questi alfabeti in una MT possono essere infiniti o sono sempre prefissati in precedenza?.
Consideriamo una $MT $ che calcola il successore di un numero, $n$.
Se ho ben capito, l'algoritmo è il seguente :
1) se $n<9$ la macchina aggiunge 1.
2) se $n>9$ si sostituisce l'ultima cifra con 0 ed esaminare la precedente. Ripeterla finché non si determina $n+1$.
Quindi , per esempio, se la $MT$ di Turing vuole calcolare il successore di $2$
parte da un $q_0$ iniziale, che sarebbe , la testina ferma nella cella dove è posto il 2 , lo esamina, dopo che lo ha esaminato, decide se $<9$ , dopo di che somma 1 a 2, si sposta nella cella affianco, e "stampa " 3. Giusto?
Grazie per i vostri eventuali chiarimenti!
Risposte
up
"Kashaman":
Domanda, perché $Q$ deve essere necessariamente non vuoto?
$Q$ non è vuoto perché contiene almeno un elemento, lo stato iniziale.
"Kashaman":
Consideriamo $\nabla$ e $\xi$. Questi alfabeti in una MT possono essere infiniti o sono sempre prefissati in precedenza?
Non possono essere infiniti, sono necessariamente finiti.
PS. Dove hai trovato questa definizione di MdT? Non capisco a cosa serva $B$...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo