<<<<< Su che cosa è

Note

[1] Come suggerisce E. Casari in "Rivista di filosofia", n. 21, ottobre 1981, p. 368.

<<<<< Su che cosa è

Note

[2] Si consideri la seguente funzione:

[L'ultimo teorema di Fermat: non ha soluzione nei numeri interi per n maggiore di 2]

Si tratta di una funzione effettivamente computabile: sia la funzione costante 1, sia la funzione costante 0,

sono entrambe effettivamente computabili.

Si noti che, allo stato attuale, non si conosce alcun modo per computare i valori di f (x).

D'altra parte, la tesi di Church fu in origine proposta e discussa da un punto di vista classico, nonintuizionista.

(Elliott Mendelson, Second Thoughts about Church's Thesis and Mathematical Proofs, "The Journal of Philosophy", vol. LXXXVII, 1990, p. 226 e n.).

<<<<< Su che cosa è

Note

[3] Church: "An Unsolvable Problem of Elementary Number Theory", Amer. J. Of Mathematics, LVIII (1936), 345-363. Post: "Finite Combinatory Processes. Formulation I", Journal of Symbolic Logic, I (1936), 103-5. Turing: "On Computable Numbers with Applications to the Entscheidungsproblem", Proceedings of the London Mathematical Society, XLII (1936), 230.265.

<<<<< Su che cosa è

Note

[4]Una macchina di Turing è costituita, innanzitutto, da un nastro diviso in riquadri (il nastro consiste, in ogni dato momento, di un numero finito di riquadri, benché, quando risulti necessario, ulteriori riquadri possano sempre essere aggiunti a destra o a sinistra del nastro), in cui sono stampati dei simboli (in un riquadro può trovarsi al massimo un simbolo), scelti da un insieme finito di simboli costituenti l'alfabeto della macchina, e uno scanner che le consente di osservare il contenuto di un solo riquadro alla volta. Ad ogni istante, lo scanner può trovarsi in uno qualsiasi dei suoi stati interni, anch'essi costituenti una collezione finita.
La macchina di Turing ha inoltre un programma, ossia una lista finita di istruzioni che le dicono cosa fare a seconda dei casi. Essa può compiere, a partire da uno stato iniziale e secondo le istruzioni del suo programma, le seguenti azioni : (1) sostituire il simbolo, che in quell'istante sta osservando, con un altro simbolo, che può essere anche lo stesso; (2) spostarsi di un riquadro a destra; (3) spostarsi di un riquadro a sinistra; (4) fermarsi. Una volta compiuta l'azione appropriata, il programma determina il nuovo stato interno dello scanner.
All'inizio del processo di computazione di una funzione di n argomenti, gli n argomenti si trovano scritti sul nastro separati da un riquadro vuoto: poiché ciascuno di questi n argomenti è un numero naturale, ciascun numero naturale m si trova sul nastro sotto forma di una sequenza di m+1 tratti, | | | …|, stampati su riquadri consecutivi.
Quando, dopo aver eseguito il programma, la macchina si ferma e sul nastro rimane la rappresentazione di un dato numero naturale k, k è allora considerato il valore della funzione computata.

<<<<< Su che cosa è

Note

[5]La tesi di Church è solitamente formulata in termini di funzioni parziali ricorsive (definite da S. C. Kleene), di cui è stata dimostrata l'equivalenza rispetto alle funzioni Turing-computabili, in quanto le prime risultano più facili da trattare da un punto di vista tecnico.

<<<<< Su che cosa è

Note

[6]Una discussione su questo punto si trova in Elliott Mendelson, cit., p. 225 e sgg.

<<<<< Su che cosa è

Note

[7]L' explicatum, ci viene detto allora (cfr. Mendelson, cit., p. 229) non ha lo stesso effetto psicologico dell' explicandum, della nozione originale.

<<<<< Su che cosa è

Note

[8]Two dogmas of empiricism, trad. it. Il problema del significato, Roma, cfr. p.194.