|
Categorie
Winzipedia Uso dell'wiki |
ComputabilitàInformatica3.Computabilità VersioniNascondi le modifiche minori - Mostra le modifiche Modificate le linee 2-3: da:
'''Autore:''' [[Profiles.Andrea|Andrea Rota]] a:
'''Autore:''' [[Profiles.Andrea|Andrea Rota]] Modificate le linee 15-20: da:
La non dipende da quale linguaggio viene usato per scrivere il programma P: visto che alcuni linguaggi forniscono meno costrutti di altri, si decide che per testare la di un algoritmo generico lo scrive nel linguaggio della '''macchina di Il '''Teorema di Church''' afferma che non esistono strumenti automatici di calcolo potenti della macchina di !! Macchina di La macchina di a:
La non dipende da quale linguaggio viene usato per scrivere il programma P: visto che alcuni linguaggi forniscono meno costrutti di altri, si decide che per testare la di un algoritmo generico lo scrive nel linguaggio della '''macchina di Turing''', che il risolutore potente e generico disponibile. Il '''Teorema di Church''' afferma che non esistono strumenti automatici di calcolo potenti della macchina di Turing, che risolvere i problemi risolti da qualsiasi algoritmo. !! Macchina di Turing La macchina di Turing rappresenta un modello di che un elaboratore fare e si basa sulle FSM (''Finite State Machine''). Le sue caratteristiche sono: Modificate le linee 25-27: da:
L'input e l'output vengono letti e scritti su di un nastro che scorrere avanti e indietro. Nella macchina di Gli elementi tipici di una macchina di a:
L'input e l'output vengono letti e scritti su di un nastro che scorrere avanti e indietro. Nella macchina di Turing da noi trattata avremo un nastro unico, anche se esistono varianti multinastro. Gli elementi tipici di una macchina di Turing sono sette (la macchina identificabile con una 7-upla): Modificate le linee 3-4: da:
'''Hanno contribuito:''' a:
'''Hanno contribuito:''' Modificata la linea 6: da:
->[-Questa pagina un riassunto del capitolo 2 del libro consigliato dal docente e tratta dell' di scrivere algoritmi che risolvano alcune classi di problemi. Sono riassunti i contenuti dei pdf ''touringm.pdf'' e ''.pdf'' disponibili sul sito del corso. a:
->[-Questa pagina un riassunto del capitolo 2 del libro consigliato dal docente e tratta dell' di scrivere algoritmi che risolvano alcune classi di problemi. Sono riassunti i contenuti dei pdf ''touringm.pdf'' e ''.pdf'' disponibili sul sito del corso.-] Modificata la linea 6: da:
->Questa pagina un riassunto del capitolo 2 del libro consigliato dal docente e tratta dell' di scrivere algoritmi che risolvano alcune classi di problemi. Sono riassunti i contenuti dei pdf ''touringm.pdf'' e ''.pdf'' disponibili sul sito del corso. a:
->[-Questa pagina un riassunto del capitolo 2 del libro consigliato dal docente e tratta dell' di scrivere algoritmi che risolvano alcune classi di problemi. Sono riassunti i contenuti dei pdf ''touringm.pdf'' e ''.pdf'' disponibili sul sito del corso.]- Modificate le linee 3-4: da:
''' a:
'''Hanno contribuito:''' - Aggiunte le linee 2-3:
'''Autore:''' [[Profiles.Andrea|Andrea Rota]]\\ '''Contributori:''' - 23/05/2006 ore 20:30 CEST
di - Sistemato Sommario
Modificata la linea 3: da:
->Questa pagina un riassunto del capitolo 2 del libro consigliato dal docente e tratta dell' di scrivere algoritmi che risolvano alcune classi di problemi. a:
->Questa pagina un riassunto del capitolo 2 del libro consigliato dal docente e tratta dell' di scrivere algoritmi che risolvano alcune classi di problemi. Sono riassunti i contenuti dei pdf ''touringm.pdf'' e ''.pdf'' disponibili sul sito del corso. 23/05/2006 ore 16:33 CEST
di - Uniformato al secondo pacco di slide sulle macchine di Touring
Modificate le linee 24-27: da:
Gli elementi tipici di una macchina di Touring sono # Un insieme Q di stati # Un insieme T che l'alfabeto a:
Gli elementi tipici di una macchina di Touring sono sette (la macchina identificabile con una 7-upla): # Un insieme finito di stati Q # Un alfabeto di input Σ (che non contiene il carattere ''blank'') # Un alfabeto Γ di simboli del nastro, con Σ sottoinsieme di Γ. (Γ contiene il carattere ''blank'') Modificate le linee 29-30: da:
# a:
# Uno stato qr di rifiuto # Uno stato qa d'accettazione Modificate le linee 45-46: da:
'''1. Costruiamo una funzione D''' a:
'''1. Costruiamo una funzione D'''\\ Modificate le linee 55-57: da:
'''2. Passiamo a D se stessa''' Se invochiamo a:
'''2. Passiamo a D se stessa'''\\ Se invochiamo D passando come argomento se stessa, otteniamo una contraddizione: se ''halt(D,D)'' valuta come terminante D, allora D entra nel ciclo infinito e quindi non termina. Viceversa se ''halt(D,D)'' valuta la funzione D come non terminante, la funzione D termina. '''3. Conclusione'''\\ Come si intuire, la dimostrazione totalmente indipendente da come scritta la funzione ''halt''. Per quanto possiamo sforzarci di scriverne una, questa non mai in tutti i possibili casi. Modificate le linee 40-55: da:
} a:
} !!!Dimostrazione della non dell'halt Per dimostrare che l'halt non computabile, supporremo per che sia p che x siano stringhe e che disponiamo per assurdo di una funzione ''halt'' che sia effettivamente in grado di discriminare un programma p terminante o non terminante. '''1. Costruiamo una funzione D''' Scriviamo una funzione D che accetti come input il programma P definita in modo tale che se P con input P termina (''halt(P,P)==true'') allora D entra in un ciclo infinito, altrimenti D termina. void D(program P){ if halt(P,P)==true then while(true); // D will run forever else return; } '''2. Passiamo a D se stessa''' Se invochiamo D Modificate le linee 30-40: da:
# Una funzione di movimento δ che associa ad uno stato q di Q e ad un simbolo t di T uno stato finale q' di Q, la scrittura di un simbolo t' di T sul nastro e uno spostamento del nastro a destra (R) o a sinistra (S). Solitamente la funzione viene scritta come transizione sull'arco che collega i due stati q e q' con la sintassi, "@@t simbolo letto / t' simbolo scritto, spostamento@@", leggibile come "''se trovi t, allora scrivi t' al posto di t e spostati a destra (o a sinistra)''". Se t' e t coincidono ( non viene effettuata una modifica, ma solo una sovrascrittura), possibile scrivere la forma compatta "@@t simbolo letto, spostamento@@". a:
# Una funzione di movimento δ che associa ad uno stato q di Q e ad un simbolo t di T uno stato finale q' di Q, la scrittura di un simbolo t' di T sul nastro e uno spostamento del nastro a destra (R) o a sinistra (S). Solitamente la funzione viene scritta come transizione sull'arco che collega i due stati q e q' con la sintassi, "@@t simbolo letto / t' simbolo scritto, spostamento@@", leggibile come "''se trovi t, allora scrivi t' al posto di t e spostati a destra (o a sinistra)''". Se t' e t coincidono ( non viene effettuata una modifica, ma solo una sovrascrittura), possibile scrivere la forma compatta "@@t simbolo letto, spostamento@@". !!Il problema dell'halt Un classico esempio di funzione non computabile quello dell'halt. Con la funzione halt indicheremo l'implementazione di un ipotetico algoritmo in grado di stabilire se un programma ''p'', forniti un input ''x'', termina la sua elaborazione in tempo finito. bool halt(program p, input x){ if(p(x) halts) then return true; else return false; } 23/05/2006 ore 14:57 CEST
di - MAcchina di touring 2 23/05/2006 ore 14:57 CEST
di - MAcchina di touring 2
Modificata la linea 30: da:
# Una funzione di movimento δ che a:
# Una funzione di movimento δ che associa ad uno stato q di Q e ad un simbolo t di T uno stato finale q' di Q, la scrittura di un simbolo t' di T sul nastro e uno spostamento del nastro a destra (R) o a sinistra (S). Solitamente la funzione viene scritta come transizione sull'arco che collega i due stati q e q' con la sintassi, "@@t simbolo letto / t' simbolo scritto, spostamento@@", leggibile come "''se trovi t, allora scrivi t' al posto di t e spostati a destra (o a sinistra)''". Se t' e t coincidono ( non viene effettuata una modifica, ma solo una sovrascrittura), possibile scrivere la forma compatta "@@t simbolo letto, spostamento@@". Modificate le linee 29-30: da:
# Una successione F di simboli, tutti presi da T, che il risultato dell'elaborazione. a:
# Una successione F di simboli, tutti presi da T, che il risultato dell'elaborazione. # Una funzione di movimento δ che associa 23/05/2006 ore 14:45 CEST
di - MAcchina di touring
Modificate le linee 27-29: da:
# Una successione S di simboli, tutti presi da T, che il nastro di input. La successione con un simbolo ''b''. a:
# Una successione S di simboli, tutti presi da T, che il nastro di input. La successione con un simbolo ''b''. # Uno stato q0 di partenza # Una successione F di simboli, tutti presi da T, che il risultato dell'elaborazione. Modificate le linee 7-8: da:
!!! Contenuto della sottosezione a:
!!!Esempi *Una funzione computabile @@bool dispari(int n)@@ in quanto la funzione dispari perfettamente definita nell'insieme dei numeri interi. *Una funzione computabile, ma parzialmente calcolabile, @@double inverso(double n)@@ in quanto la funzione inverso definita nell'insieme dei numeri reali ad esclusione di 0. *Una funzione non computabile @@bool halt(programma p)@@ che dice se un programma p fornito in input la sua esecuzione in tempo finito. La non dipende da quale linguaggio viene usato per scrivere il programma P: visto che alcuni linguaggi forniscono meno costrutti di altri, si decide che per testare la di un algoritmo generico lo scrive nel linguaggio della '''macchina di Touring''', che il risolutore potente e generico disponibile. Il '''Teorema di Church''' afferma che non esistono strumenti automatici di calcolo potenti della macchina di Touring, che risolvere i problemi risolti da qualsiasi algoritmo. !! Macchina di Touring La macchina di Touring rappresenta un modello di che un elaboratore fare e si basa sulle FSM (''Finite State Machine''). Le sue caratteristiche sono: * Opera su un numero finito di stati (programma di controllo) * eseguire semplici operazioni meccaniche * Non presenta vincoli sulla lunghezza dell'input * Non presenta vincoli sulla lunghezza dell'output L'input e l'output vengono letti e scritti su di un nastro che scorrere avanti e indietro. Nella macchina di Touring da noi trattata avremo un nastro unico, anche se esistono varianti multinastro. Gli elementi tipici di una macchina di Touring sono: # Un insieme Q di stati # Un insieme T che l'alfabeto di simboli del nastro. In particolare avremo un simbolo ''b'' appartenente a T che definito come ''blank'' # Una successione S di simboli, tutti presi da T, che il nastro di input. La successione con un simbolo ''b''. Aggiunte le linee 1-8:
!La ->'''Sommario''' ->Questa pagina un riassunto del capitolo 2 del libro consigliato dal docente e tratta dell' di scrivere algoritmi che risolvano alcune classi di problemi. !!Cosa vuol dire che una funzione computabile Diciamo che una funzione computabile se esiste un programma P che in grado di calcolarla. Occorre fare una distinzione fra funzioni non computabili e funzioni parzialmente calcolabili: per le prime non esiste un programma in grado di calcolarle, per le seconde l'algoritmo esiste ma non funziona con determinati input (la funzione detta ''parziale''). !!!Sottosezione Contenuto della sottosezione. |