Macchine di Turing: dubbio sulla calcolabilità sull'accettazione di stringhe in input

Messaggioda the-informatematica » 05/02/2020, 21:27

Salve a tutti, scusate se posto qui è la prima volta. Sono uno studente di ingegneria informatica e sto studiando il mondo della calcolabilità. In pratica mi mancano delle informazioni essenziali sulle macchine di turing e di conseguenza sull'appartenenza dei linguaggi al mondo RE e Co-RE. Allora il caso più "funzionante" passatemi il termine è quello quando un linguaggio appartiene ad R e cioè posso definire una macchina di turing M che decide L cioè decidere è inteso che la macchina accetta in input le istanze appartenenti al linguaggio in tempo finito (su questo ci sono) e rifiuta le istanze che non appartengono al linguaggio sempre in tempo finito (quindi posso assumere per scopo didattico che le istanze in generale sul linguaggio di tutti gli alfabeti si dividono in istanze che le accetto e istanze che non le accetto, lo dico solo temporaneamente nel senso che lo assumo per costruire poi il pensiero). Quindi il mio problema è se in R so rifiutare ed accettare in tempo finito cosa succede esattamente a RE quando passo un'stanza non del suo linguaggio? Se io dico che posso costruire una macchina che mi accetta in tempo finito le istanze che sono del mio linguaggio e non posso dire in tempo finito che non le accetto (e questo ci sta per definizione di RE) la mia domanda viene dalla costruzione della macchina di turing stessa. La mia funzione di transizione se non è in uno stato accettante cosa devo assumere? Facendo un esempio stupido con un automa se esso è composto da tre stati e la mia funzione dice che se ricevo lo zero vado nel secondo stato e se ricevo poi 1 vado nello stato finale (assumete che il primo stato è l'iniziale e il terzo è il finale perché riconosce 01, è proprio banale ma serve per capire) in questo caso dico che accetto ma se rimanessi fermo nello stato numero due cioè l'intermediario che per come ho detto io non è accettante (ma nemmeno di rifiuto lo specifico, è uno stato appunto intermedio cioè di passaggio o per caso è sbagliato pensarlo?) la macchina è arrestata? oppure devo specificare che se sono nello stato diciamo intermedio (parlo di stringhe date in input appositamente per farlo fermare nello stato intermedio tipo una stringa uguale al bit 0 che fa passare l'automa allo stato intermedio non accettante) la macchina sta ferma per dire che è arrestata (intendo tra le tre scelte che può fare la testina scelgo quello che sta fermo)? Il mio ragionamento è che se un linguaggio di programmazione come ad esempio java (riduco la sintassi all'osso perché al momento è zucchero sintattico) proponesse il seguente algoritmo:
Codice:
x=scanner.readInt();
y=scanner.readInt();
if(x<y)return x;else {return y;}

diciamo che lo stato iniziale è quando sono in x che sto leggendo, poi leggo y e faccio la verifica. Se io passo solo x mi fermo in y che è l'implementazione dello stato intermedio che io dicevo e se non metto che la macchina si ferma come dicevo prima l'algoritmo è li che mi aspetta. Cioè è in uno stato di non accettazione e non sa cosa fare (nè accetta nè rifiuta). Quindi cosa succede alla macchina se si trova in uno stato non finale causato ad esempio da una stringa apposita?
the-informatematica
Starting Member
Starting Member
 
Messaggio: 1 di 5
Iscritto il: 05/02/2020, 20:57

Re: Macchine di Turing: dubbio sulla calcolabilità sull'accettazione di stringhe in input

Messaggioda the-informatematica » 11/02/2020, 21:04

Diciamo che ho parzialmente risolto definendo che se io cado in uno stato non accettante rifiuto la mia istanza in un certo senso mettendo la mia macchina ferma quindi arrestata. Ora il mio dubbio è un altro, lo posto in un altra domanda apposita.
the-informatematica
Starting Member
Starting Member
 
Messaggio: 2 di 5
Iscritto il: 05/02/2020, 20:57


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 10 ospiti