Please enable JavaScript.
Coggle requires JavaScript to display documents.
LA MACCHINA DI TURING - Coggle Diagram
LA MACCHINA DI TURING
caratteristiche
è un CALCOLATORE (macchina) IDEALE: non è soggetta ad alcuna delle limitazioni proprie dei calcolatori fisicamente realizzati
è definita da un INSIEME DI REGOLE (=QUADRUPLE) che descrivono il comportamento della macchina, la quale legge e opera su un nastro di input-output (lettura e scrittura). Ed esegue tali regole:
Ha una testina che si sposta lungo il nastro leggendo, scrivendo o cancellando simboli nelle celle del nastro. La macchina poi analizza il nastro, una cella alla volta, iniziando da quella che contiene il simbolo più a sx del nastro
-
-
-
-
deve seguire un ALGORITMO: eseguire una det. azione in modo univoco in base a ciò che si osserva sul nastro di calcolo e da ciò che si ricorda; quindi è una procedura costituita da una lista di istruzioni che devono essere seguite necessariamente affinché si ottenga il risultato previsto
TESI DI CHURCH-TURING (TEORIA DELLA CALCOLABILITA'): se un problema è umanamente calcolabile, allora esisterà una MdT in grado di risolverlo (in modo più efficace e veloce) = la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing