tesi di Church-Turing
L'affermazione che ogni procedura effettiva sia eseguibile da una macchina di Turing. Non è dimostrabile, perché lega una nozione informale a una formale; è sostenuta dall'equivalenza di tre definizioni indipendenti.
Compare in volume VI
Come la richiudono le mappe di fine capitolo
- Volume VI · 7. La macchina che decide
-
L'affermazione che ogni procedura effettiva sia eseguibile da una macchina di Turing. Non è dimostrabile, perché lega una nozione informale a una formale; è sostenuta dall'equivalenza di tre definizioni indipendenti.