Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Step 5 - Computabilità (Bortolussi, Beorchia, Romano)

No description
by

Riccardo Bortolussi

on 4 June 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Step 5 - Computabilità (Bortolussi, Beorchia, Romano)

TEORIA DELLA CALCOLABILITÀ E DELLA COMPUTABILITÀ Step riassuntivo La Calcolabilità La Tesi di Church La Computabilità Alan Turing Esempio di simulazione (con Lego) Alonzo Church LA Macchina di Turing Universale La Calcolabilità ha lo scopo di classificare i problemi risolvibili e non, mentre Complessità in facili e difficili. La tesi di Church postula che tutte le funzioni effettivamente calcolabili siano esprimibili con una Macchina di Turing.
Non esiste meccanismo di calcolo automatico superiore alla MDT.

Nessun algoritmo, indipendentemente dallo strumento utilizzato per implementarlo, può risolvere problemi che non siano risolvibili dalla MDTU (è il calcolatore più potente che potremo mai avere). Alonzo Church (Washington, 14 giugno 1903 – Hudson, 11 agosto 1995) è stato un matematico e logico statunitense che fu in parte responsabile della fondazione dell'informatica (o computer science).
Conosciuto per lo sviluppo del Lambda Calcolo, in cui mostra l'esistenza di un problema indecidibile, ancora prima di Alan Turing (Halting Problem). Alan Mathison Turing (Londra, 23 giugno 1912 – Wilmslow, 7 giugno 1954) è stato un matematico, logico e crittografo britannico, considerato uno dei padri dell'informatica e uno dei più grandi matematici del XX secolo. Data una Macchina di Turing che calcola una funzione f, è possibile specificare un dato in ingresso ed ottenere, al termine della computazione, un certo dato in uscita. La classificazione: Problemi Non decidibili;
Problemi decidibili (Trattabili e Intrattabili). I problemi decidibili si posso classificare secondo le risorse a disposizione, come lo spazio di memoria e il tempo di calcolo. La teoria della Computabilità ha lo scopo di comprendere quali problemi possono essere calcolati tramite un Algoritmo. L'Algoritmo Un Algoritmo è una sequenza ordinata di passi (operazioni o istruzioni) elementari, che conduce ad un determinato risultato in un tempo finito. Teorema di Bohm - Jacopini Qualunque Algoritmo può essere implementato utilizzando tre sole strutture:
la Sequenza;
la Selezione;
il Ciclo (Iterazione).
Da applicare ricorsivamente alla composizione di istruzioni elementari. Teorema Alan Turing ha dimostrato che riuscire a dimostrare se un programma arbitrario, si arresta e termina la sua esecuzione, è IMPOSSIBILE. Il Problema dell'Arresto Consiste nel chiedersi se un generico programma termina la sua esecuzione, oppure entra in un ciclo (Senza limiti di tempo e di memoria). È composta da: Un nastro
Una testina
Uno stato interno
Un programma
Uno stato iniziale Il Nastro Infinito
Suddiviso in celle In una cella può essere contenuto un simbolo preso da un alfabeto opportuno (insieme di simboli). Lo Stato interno e la Testina La testina e in grado di leggere e scrivere il contenuto della cella del nastro su cui si trova.
Lo stato è un elemento appartenente all’insieme degli stati. Il Programma di una MdT Il comportamento della macchina è determinato da un insieme di regole: Una regola ha la forma seguente: (A, a, B, b, dir).
Una regola viene applicata se lo stato corrente della macchina è "A" e il simbolo letto dalla testina è "a".
L’applicazione della regola cambia lo stato in B, scrive sul nastro b ed eventualmente sposta la testina di una cella a sinistra o a destra (dir). Il funzionamento di una MdT Operazioni:

Determina la regola da applicare in base allo stato interno e al simbolo corrente (quello letto dalla testina).
Se esiste una tale regola cambia lo stato, scrive il simbolo sulla cella corrente e si sposta come indicato dalla regola.
Se non esiste la regola l’esecuzione termina. Per risolvere un problema è necessario trovare l’algoritmo e codificarlo come programma. La scomposizione di problemi in sottoproblemi aiuta a riutilizzare algoritmi già conosciuti. Documentario su Alan Turing The End PREZI created by Riccardo Bortolussi, Massimo Romano, Andrea Beorchia. La Macchina di Turing (MDT) La Macchina di Turing è la formalizzazione astratta di un dispositivo meccanico (Algoritmo). E' paragonabile ad un software attuale. Da non confondersi con La Macchina di Turing Universale (MDTU), che permette l'esecuzione della MDT. Kurt Gödel (Brno, 28 aprile 1906 – Princeton, 14 gennaio 1978) è stato un matematico, logico e filosofo austriaco naturalizzato statunitense, noto soprattutto per i suoi lavori sull'incompletezza delle teorie matematiche. Kurt Gödel La Godelizzazione afferma che tutte le MDT devono essere numerate con numeri primi.
Full transcript