\input mace
\onlinetrue
\phantom.
\bigskip

\centerline{\bigrm Infinito completato vs.~incompleto}
\smallskip

\centerline{\bigrm in aritmetica}
\medskip

\centerline{Edward Nelson}
\medskip

\centerline{Dipartimento di matematica, Universit\`a di Princeton}
\bigskip

I \ii numeri.\/ sono 0, 1, 2, 3, \dots. I numeri costituiscono
l'infinito
pi\`u semplice, e dunque se vogliamo capire l'infinito ci conviene di
tentare di capire i numeri.

Invece di usare i simboli 1, 2, ecc.~di origine indiana, usiamo
la notazione della logica matematica: i numeri sono 0, S0, SS0,
SSS0,~\dots\ dove si pu\`o leggere S come ``successore''.
Questa notazione esprime chiaramente l'idea che i
numeri si ottengono da un processo di contare, l'uno dopo l'altro.

Ci sono almeno due modi diversi da pensare ai numeri: come un infinito
completato oppure come
un infinito incompleto. Non faremo un er\-rore grave
se chiamiamo questi il modo \ii platonico.\/~(P) e il modo \ii
aristotelico.\/~(A).

Ora, ho gi\`a fatto un grande errore in questa conferenza a causa di
una trappola di linguaggio. Ho parlato di P e A come due modi di
pensare a ``i numeri''. Ma vedremo che P e A danno due sistemi di
numeri \ii diversi., non due modi di pensare allo stesso sistema.

Cominciamo con P, che \`e
il punto di vista della matematica contemporanea.
I numeri costituiscono un infinito completato notato~\N.
S'intende che i variabili $x$, $y$, e cos\`\i\ via, sono elementi di~\N.
La propriet\`a fondamentale di~\N\ \`e \ii l'induzione.\/:

\medskip

{\narrower
{\it Ipotesi}\/:

\quad 0 ha la propriet\`a $p\,$;

\quad se $x$ ha la propriet\`a $p$, allora $\ro Sx$ ha la propriet\`a $p$.

{\it Conclusione}\/:

\quad per ogni $x$, $x$ ha  la propriet\`a $p$.

}
\medskip

La prima ipotesi \`e la \ii base.\/ e la seconda \`e il 
\ii passo induttivo.. Per un numero specifico, ad esempio SSS0,
non \`e necessario assumere l'induzione per dimostrare la conclusione
dalle ipotesi. Infatti, supponiamo $p(0)$. Allora, usando 
successivamente il passo induttivo, otteniamo 
$p(\ro S0)$, $p(\rm SS0)$, e infine $p(\rm SSS0)$.
Cionondimeno, l'induzione \`e un assioma potente e molte propriet\`a
dei numeri sono dimostrabili soltanto tramite l'induzi\-o\-ne.
Ecco un esempio.

Sia $p$ la propriet\`a di $x$ seguente: esiste un numero $y$ non zero
divisibile da ogni numero $z$ non zero tale che $z\le x$.
Sostengo che ogni numero~$x$ ha la propriet\`a~$p$.
Certo che 0 ha la propriet\`a~$p$ (sia $y=\ro S0$).
Supponiamo che $x$ abbia la propriet\`a~$p$, e dunque che esiste un 
numero~$y'$ non zero divisibile da ogni numero~$z$ non zero tale che
$z\le x$. Per induzione, ci resta soltanto di dimostrare il passo
induttivo, che $\ro Sx$ ha la propriet\`a~$p$; cio\`e, che esiste un
numero~$y$ non zero divisibile da ogni numero~$z$ non zero tale che
$z\le\ro Sx$. Ma \`e vero:
sia $y=y'\.\ro Sx$ e consideriamo qualunque numero~$z$ non zero con 
$z\le\ro Sx$. Allora o $z\le x$, nel qual caso esso divide~$y'$
e dunque divide~$y=y'\.\ro Sx$, oppure $z=\ro Sx$, nel qual caso pure
esso divide~$y$, ci\`o che conclude la dimostrazione.

Nei primi anni del novecento, Bertrand Russell e Henri Poincar\'e
scambiarono polemiche sopra la natura dell'induzione. Secondo
Poinca\-r\'e, l'induzione \`e un principio logico, una specie di 
sillogismo infinito. Russell sostenne che l'induzione \`e soltanto
una definizione verbale---i~numeri sono \ii definiti.\/ come
quegli oggetti che ubbidiscono all'induzione. N\'e l'uno n\'e l'altro
chiam\`o in questione la legitimit\`a dell'induzione.

Nella matematica contemporanea, il punto di vista di Russell 
pre\-va\-le.
Oggi il solito fondamento della matematica \`e la teoria degli insiemi,
teoria di Zermelo-Fraenkel con l'assioma di scelta (ZFC).
Le propriet\`a sono reificate e diventano insiemi.
Il numero~0 \`e definito come l'insieme vuoto, senza elementi.
Per ogni insieme~$x$, si definisce il suo successore~$\ro Sx$ come
l'insieme i cui elementi sono gli elementi di~$x$ pure che l'insieme~$x$
stesso. Si dice che un insieme~$X$ \`e \ii induttivo.\/ se 0~\`e
un elemento di~$X$ e se ogni volta che $x$ \`e un elemento di~$X$,
allora anche il suo successore~$\ro Sx$ \`e elemento di~$X$.
\ii L'assioma dell'infinito.\/ di ZFC asserisce che esiste un insieme
induttivo. Poi si dimostra che esiste un unico insieme induttivo
minimale e si definisce~\N, l'insieme di tutti i numeri, come
questo insieme.

Detto verbalmente, tutto ci\`o riviene a questo: una propriet\`a \`e
\ii induttiva.\/ se e solo se sodisfa alla base e al passo induttivo;
un oggetto \`e un \ii numero.\/ se e solo se ha ogni propriet\`a 
induttiva. Cos\`\i\ una propriet\`a che gli oggetti possono avere,
quella di essere un numero, \`e definita tramite la collezione di
tutte le propriet\`a che possono avere gli oggetti. Questa \`e una
definizione impredicativa. L'impredicativit\`a disturba profondamente
alcuni pensatori; altri non vedono nessun problema.
La matematica contemporanea \`e completamente impredicativa.

Quale fondamento per l'aritmetica, questa definizione non sodisfa.
Certo che l'aritmetica, la teoria dei numeri, \`e la teoria matematica
la pi\`u primitiva. Ma la si basa sulla teoria, ben pi\`u sofisticata,
degli insiemi. Inoltre, il procedimento di reificare le propriet\`a
come insiemi---rimpiazzando una propriet\`a, concetto intensionale,
con l'insieme estensionale di tutti gli oggetti che hanno la 
propriet\`a---conduce a contradiz\-zioni ben note se non si prende cura,
come Russell stesso scopr\`\i\ nel suo paradosso famoso dell'insieme
di tutti gli insiemi che non sono elementi di se stessi.

Strettamente legata all'induzione \`e la costruzione di numeri
per mezzo della \ii ricorsione primitiva.. Questa si fa specificando
prima
il valore quando $y=0$ (la \ii base.\/) e poi il valore per $\ro Sy$
per mezzo del valore per~$y$ (il \ii passo ricorsivo.\/). Allora,
per esempio, il valore per $y=\rm SSS0$ \`e determinato: il valore per
$y=0$ ci \`e dato, da questo otteniamo il valore per $y=\ro S0$,
poi il valore per $y={\rm SS}0$, e infine il valore per $y=\rm SSS0$.
Introduciamo l'addizione~$+$, la moltiplicazione~$\.$, 
l'esponenziazione~$\uparrow$, e la super-esponenziazione~$\Uparrow$,
e cos\`\i\ via, come segue:
\medskip

\halign{\quad\qquad\hfil$#$\ =\ &$#$,\hfil\quad&\hfil$#$\ =\ &$#$;\hfil\cr
x\Pl0&x&x\Pl\ro Sy&\ro S(x+y)\cr
x\Ti0&0&x\Ti\ro Sy&x+(x\Ti y)\cr
x\Ex0&\ro S0&x\Ex\ro S y&x\Ti(x\Ex y)\cr
x\Se0&\ro S0&x\Se\ro S y&x\Ex(x\Se y)\cr
}
\medskip

\noindent e cos\`\i\ via. Allora
\medskip

\halign{\quad\qquad\hfil$#$\ =&\ $#$\hfil&\quad#\hfil&\ \hfil#\hfil\cr
x\Pl y&\ro S\ldots\ro Sx &con $y$ occorrenze di&S,\cr
x\Ti y&x\Pl\ldots\Pl x &con $y$ occorrenze di&$x$,\cr
x\Ex y&x\Ti\ldots\Ti x&con $y$ occorrenze di&$x$,\cr
x\Se y&x\Ex\ldots\Ex x&con $y$ occorrenze di&$x$,\cr
}
\medskip

\noindent e cos\`\i\ via. Queste sono ricorsioni primitive.
Ackermann dimostr\`o come andare inoltre alle ricorsioni primitive.
Notiamo $\ro F_0$, $\ro F_1$, $\ro F_2$, $\ro F_3$, e cos\`\i\ via,
le funzioni $+$, $\.$, $\uparrow$, $\Uparrow$, e cos\`\i\ via.
Allora, una versione della funzione Ackermann \`e la funzione~$A$
il cui valore su~$y$ \`e $A(y)=y\,\ro F_y\,y$.
Questa funzione \`e ricorsiva---per qualsiasi~$y$ abbiamo un
procedimento meccanico per calcolare il valore~$A(y)$---ma la funzione
cresce ben pi\`u rapidamente di ogni funzione ricorsiva primitiva.
Questa costruzione \`e un altro esempio del metodo diagonale di Cantor,
metodo che Cantor us\`o per dimostrare che il continuo (i numeri reali)
non \`e numerabile, un infinito pi\`u grande di~\N,
metodo che anche \`e alla base del paradosso di Russell e dei teoremi
d'incompletezza di G\"odel.

Si vuole che l'idea generale di funzione ricorsiva esprima il concetto
di algoritmo. La parola \ii algoritmo.\/ viene dal nome,
al'Khwarizmi, dell'autore del trattato altamente influente
{\it Al-Jabr wa-al-Muqabilah}\break
scritto circa nel 820 (e la parola
\ii algebra.\/ stessa proviene dal titolo del libro!). Ma passarono
pi\`u di undici secoli prima che fosse ricercato il problema di definire
il significato di algoritmo, di definire il concetto di
funzione ricorsiva.
Il procedimento di Ackermann dimostra l'impossibilit\`a di fare
una definizione sintattica esplicita del concetto di funzione ricorsiva,
perch\`e ci\`o permet\-terebbe di elencarle e poi la costruzione
diagonale darebbe una nuova funzione ricorsiva.

Il problema \`e stato risolto in tre modi apparentemente diversi da
Church, G\"odel, e Turing (rispettivamente professore all'Universit\`a
di Princeton, socio permanente dell'Istituto per lo Studio Avvanzato a
Princeton, e studente all'Universit\`a di Princeton, noto con orgoglio
di paese), e queste tre definizioni si rivellarono equivalenti.
G\"odel stesso ha detto che la definizione di Turing \`e la migliore.
Il lavoro di Turing costru\`\i\ i fondamenti dell'informatica e il suo
\pdfKlink{articolo}{http://www.abelard.org/turpap2/tp2-ie.asp}
[6] del 1936 \`e interessante ancora oggi, ma bisgona stare
attenti al fatto che in questo articolo ``computer'' significa
``persona che calcola''.

Si pu\`o descrivere la definizione di Turing come segue. Consideriamo
un programma computer (questo \`e un oggetto sintattico concreto)
che prende i numeri come argomenti. 
Allora \`e un \ii algoritmo.\/ se e solo se per ogni argomento, prima o poi il calcolo termina con un numero come
valore (questo \`e un concetto semantico astratto). Il problema di decidere
se o no un programma termina per ogni argomento non \`e risolvibile
algoritmicamente; ci\`o significa che per un programma generale non c'\`e
nessun modo per determinare se sia un algoritmo oltre che cercare fra
tutti gli infiniti argomenti possibili e per ognuno di essi aspettare
pazientemente---per sempre, se necessario---a vedere se il calcolo termina con
un valore. Ecco l'infinito completato senza scherzi!
(In uno dei libri del paese di Oz, lo Spaventapasseri dice,
``Pu\`o darsi che resteremo intrappolati qu\`\i\ per sempre!'' La Ragazza Mosaica
chiede, ``Quanto dura il `per sempre'?'' e lo Spaventapasseri risponde,
``\`E proprio questo che scopriremo subito.'')
\medskip

\centerline{$*$\qquad$*$\qquad$*$}
\medskip

Ora facciamo una critica aristotelica (come la chiamo) di queste idee,
considerando i numeri come un infinito incompleto. Si pu\`o notare che
etimologicamente
l'aggettivo nella locuzione ``infinito incompleto'' \`e superfluo, dato
che la parola \ii infinito.\/ significa non finito (nel senso di
``no ho finito'').

Come abbiamo visto, l'induzione e la ricorsione primitiva si basano sul concetto
dei numeri come un infinito completato. Introduciamo il concetto di un
\ii numero da contare.. Questo \`e un concetto primitivo dell'aritmetica-A,
e piuttosto che tentare di definirlo, enumciamo gli assiomi che postuliamo
per questo concetto. Questi assiomi sono la base dell'induzione e il
passo induttivo, cio\`e

\break

\halign{\quad\qquad#\hfill\cr
0 \`e un numero da contare;\cr
se $y$ \`e un numero da contare, lo \`e anche $\ro Sy$.\cr
}
\medskip

\noindent
Ecco tutto quello
che supponiamo riguardante questo concetto, e in particolare
non postuliamo che tutti i numeri siano numeri da contare.

Usando le cifre arabiche (cos\`\i\ chiamate bench\`e siano d'origine indiana
e fossero trasmesse all'ovest principalmente dal persiano al'Khwariz\-mi), 
chiediamo se, dato un numero specifico~$y$ definito per mezzo di una ricorsione
primitiva, ad esempio $y=2\Uparrow5$ oppure $y=2\Uparrow2\Uparrow5$,
si pu\`o dimostrare che \`e un numero da contare. Ora, dire che c'\`e una
dimostrazon ovvia di $y$~passi \`e un ragionamento circolare, perch\`e i passi
sono cose che si contano, e dunque i passi si possono contare solo se
infatti $y$~\`e un numero da contare.
Si nota che $2\Uparrow5=\hbox{$2\uparrow2\uparrow2\uparrow2\uparrow2$}=
2\uparrow65536$ \`e un numero super-astronomicamente grande, e che
$2\Uparrow2\Uparrow5$ \`e uguale a
$2\uparrow\ldots\uparrow2$ con quel numero,
$2\Uparrow5$, di occorrenze di~2.

Facciamo le due definizioni seguenti:
\medskip

{\narrower
1.~$x$ \`e un \ii numero additivo.\/ se e solo se per ogni numero da contare $y$,
anche $x+y$ \`e un numero da contare;

2.~$x$ \`e un \ii numero moltiplicativo.\/ se e solo se per ogni numero additivo
$y$, anche $x\.y$ \`e un numero additivo.

}
\medskip

Allora abbiamo i teoremi seguenti:
\medskip

{\narrower

\leavevmode\hbox{3.~Se} $x$ \`e un numero additivo, $x$ \`e un numero da contare.

\leavevmode\hbox{4.~Se} $x$ \`e un numero moltiplicativo, $x$ \`e un numero additivo.

\leavevmode\hbox{5.~Se} $x$ \`e un numero moltiplicativo, $x$ \`e un numero da contare.

\leavevmode\hbox{6.~Se} $x$ e $z$ sono numeri additivi, lo \`e anche $x+z$.

\leavevmode\hbox{7.~Se} $x$ e $z$ sono numeri moltiplicativi, lo \`e anche $x+z$.

\leavevmode\hbox{8.~Se} $x$ e $z$ sono numeri moltiplicativi, lo \`e anche $x\.z$.

}
\medskip

Le dimostrazioni sono facili. Per 3, sia $x$ un numero additivo.
Applichiamo la definizione~1 a $y=0$, che \`e un numero da contare. Allora 
$x+0$ \`e un numero da contare, ma $x+0=x$.

Per 4, sia $x$ un numero moltiplicativo. Applichiamo la definizione~2
a $y=1$, che \`e un numero additivo, come facilmente si vede. 
Allora $x\.1$ \`e un numero additivo, ma $x\.1=x$.

Notiamo che 5 \`e conseguenza di 3 e 4.

Per 6, siano $x$ e $y$ numeri additivi, e sia $y$ un numero da contare
qualunque. Secondo la definizione~1, dobbiamo dimostrare che
$(x+z)+y$ \`e un numero da contare. Notiamo che $z+y$ \`e un numero da
contare, secondo la definizione~1, e dunque $x+(z+y)$ \`e un numero da contare,
sempre secondo la definizione~1. Ma $x+(z+y)=(x+z)+y$.

Per 7, siano $x$ e $z$ numeri moltiplicativi, e sia $y$ un numero additivo
qualunque. Secondo la definizione~2, dobbiamo dimostrare che
$(x+z)\.y$ \`e un numero additivo. Notiamo che $z+y$ \`e un numero additivo,
secondo la definizione~2, e che $x+y$ \`e un numero additivo, sempre
secondo la definizione~2. Dunque
$(x\.y)+(z\.y)$ \`e un numero additivo secondo il teorema~6. Ma
$(x\.y)+(z\.y)=(x+z)\.y$.

Per 8, siano $x$ e $z$ numeri moltiplicativi, e sia $y$ un numero
additivo qualunque. Secondo la definizione~2, dobbiamo dimostrare che
$(x\.z)\.y$ \`e un numero additivo. Notiamo che $z\.y$ \`e un numero additivo,
secondo la definizione~2, e dunque $x\.(z\.y)$ \`e un numero additivo,
sempre secondo la definizione~2. Ma $x\.(z\.y)=(x\.z)\.y$.

Ora possiamo dimostrare che $2\Uparrow5$ \`e un numero da contare. 
Poniamo
$$\rm a_0=2,\ a_1=a_0\.a_0,\ a_2=a_1\.a_1,\ \ldots,\ a_{16}=a_{15}\.
a_{15}.$$
Allora $a_{16}=2\Uparrow5$.
Si vede facilmente che 2 \`e un numero moltiplicativo. Applicando il teorema~8
seidici volte, vediamo che $\ro a_1$,
$\ro a_2$, \dots, e $\ro a_{16}=2\Uparrow5$ sono numeri moltiplicativi, e dunque
$2\Uparrow5$ \`e un numero da contare secondo il teorema~5, ci\`o che conclude
la dimostrazione. Ma nessuno mai dimostrer\`a che $2\Uparrow2\Uparrow5$
\`e un numero da contare.

Perch\`e non si pu\`o continuare la serie di definizioni e teoremi?
Supponiamo di definire
\medskip

{\narrower
9. $x$ \`e un \ii numero esponenziabile.\/ se e solo se per ogni numero
moltiplicativo~$y$, $x\uparrow y$ \`e un numero moltiplicativo.

}
\medskip

Ma allora non possiamo dimostrare
\medskip

{\narrower
10. Se $x$ e $z$ sono numeri esponenziabili, lo \`e anche $x\uparrow z$.

}
\medskip

\noindent
La difficolt\`a \`e che l'esponenziazione non \`e associativa; cio\`e, in genere
$x\uparrow(z\uparrow y)\ne(x\uparrow z)\uparrow y$, e abbiamo usato 
l'associativit\`a dell'addizione e della moltiplicazione nei teoremi~6 e~8.
Infatti, si pu\`o dimostrare il seguente: non esiste una propriet\`a~$p$ tale
che si pu\`o dimostrare che se $p(x)$ allora $x$ \`e un numero da contare
e che se $p(x)$ e $p(z)$ allora \hbox{$p(x\uparrow z)$}. Questo teorema
non \`e facile; la dimostrazione impiega il teorema profondo di Hilbert e
Ackermann sull'eliminazione dei quantificatori.
Vedi il capitolo~18 del libro dell'autore
\yy
\pdfKlink{\it Predicative Arithmetic}{http://www.math.princeton.edu/~nelson/books/pa.pdf}
\zz
[4].

Insomma, da un punto di vista A, l'esponenziazione dei numeri non \`e un concetto
ben definito. Per conseguenza, la matematica-A \`e {\it molto}\/ pi\`u debole
della matematica-P. Per esempio, il teorema sulla divisibilit\`a che abbiamo
dimostrato per l'induzione non pu\`o essere stabilito. Ciononostante,
per alcune ragioni vale la pena di perseguire la matematica-A. Una ragione \`e
che una quantit\`a veramente sorprendente della matematica avvanzata pu\`o
essere sviluppata da questo punto di vista con grande simplificazione dei
mezzi tecnici; vedi il libro dell'autore
\yy
\pdfKlink{\it Radically Elementary Probability Theory}{http://www.math.princeton.edu/~nelson/books/rept.pdf}
\zz [5].

Un'altra ragione per sviluppare la matematica-A \`e il suo legame coi problemi
della complessit\`a computazionale, campo molto attivo della
matematica e dell'informatica teorica. Ora esaminiamo questo legame.

Turing, Church, e G\"odel hanno risolto---a condizione che si accetti \N\
come infinito completato---il problema ``cos'\`e un algoritmo?''.
Con l'avvento dei computer si pone il problema, ``cos'\`e un algoritmo
\ii fattibile.\/?''. \`E emerso un consenso fra gli studenti della complessit\`a 
computazionale che la definizione giusta \`e una \ii funzione di tempo
polinomiale..
Queste sono le funzioni tali che esistono una macchina di Turing 
(programma computer) e un polinomio~$\pi$ tali che per ogni numero~$y$
il calcolo termina e d\`a un valore dopo al massimo $\pi(\log y)$ passi.
Questa \`e una definizione complicata che a prima vista sembra piuttosto
arbitraria. Ma Bellantoni e Cook [1]
\pdfKlink{[2]}{ftp://ftp.cs.toronto.edu/pub/reports/theory/cs-92-264.ps.Z},
e anche Leivant [3], hanno dato una definizione equivalente che si pu\`o
descrivere come segue.

Consideriamo di nuovo la ricorsione primitiva. Vogliamo definire $F(x,y)$,
e a questo scopo specifichiamo un valore quando $y=0$ e poi specifichiamo un valore
per $F(x,\ro Sy)$ in termini di~$x$ e del valore per $F(x,y)$:
$$F(x,0)=G(x),\quad F(x,\ro Sy)=H\big(x,F(x,y)\big).$$
Qu\`\i\ $G$ e $H$ sono date in termini di 0, S, e funzioni gi\`a definite.
Allora abbiamo
$$\eqalign{
F(x,0)&=G(x),\cr
F(x,\ro S0)&=H\big(x,F(x,0)\big)=H\big(x,G(x)\big),\cr
F(x,{\rm SS}0)&=H\big(x,F(x,\ro S0)\big)=H\big(x,H\big(x,G(x)\big)\big),\cr
F(x,{\rm SSS}0)&=H\big(x,F(x,{\rm SS}0)\big)=H\big(x,H\big(x,H\big(x,G(x)\big)\big)\big),\cr
}$$
e cos\`\i\ via fino al valore di $F(x,y)$.

Affinch\`e questo abbia senso, bisogna che $y$ sia un numero da contare,
perch\`e la definizione \`e una costruzione passo-a-passo da 0 a S0,
a SS0, \dots, e infine a~$y$, ma anche se $y$ \`e un numero da contare
{\it non sappiamo che il valore $F(x,y)$ \`e un numero da contare}\/
(a meno che non facciamo il postulato platonico che tutti i numeri sono
numeri da contare).
Una \ii ricorsione predicativa.\/ \`e una ricorsione primitiva tale che tutte
le ricursioni sono solamente sopra i numeri da contare.

Vediamo come funziona questo. Non c'\`e problema per l'addizione:
$$x+0=x,\quad x+\ro Sy=\ro S(x+y).$$
Questo ha senso per ogni numero $x$ e ogni numero da contare $y$.
Adesso supponiamo che ambo i numeri $x$ e $y$ sono numeri da contare.
Allora non c'\`e problema con la moltiplicazione:
$$x\.0=0,\quad x\.\ro Sy=(x\.y)+x$$
dato che abbiamo definito predicativamente la somma di un numero qualunque,
come $x\.y$, con un numero da contare, come~$x$. Questi sono esempi della
ricorsione predicativa. Ma l'esponenziazione \`e impredicativa.
Nella costruzione
$$x\uparrow0=\ro S0,\quad x\uparrow\ro Sy=x\.(x\uparrow y)$$
non si sa che il numero $x\uparrow y$ \`e un numero da contare---ma la
ricorsione predicativa per la moltiplicazione \`e predicativamente definita 
soltanto se il secondo argomento \`e un numero da contare. E infatti,
l'esponenziazione \`e infattibile.

Bellantoni e Cook, e Leivant, hanno dimostrato che una funzione \`e una
funzione di tempo polinomiale (algoritmo fattibile) se e solo se \`e
costruita da una ricorsione predicativa. Questa \`e una caratterizzazione
semplice e bella: non c'\`e niente che riguardi le macchine di Turing o i
polinomi in questa descrizione, ma \`e equivalente alla definizione complicata
gi\`a data.
\medskip

\centerline{$*$\qquad$*$\qquad$*$}
\medskip

Per concludere, il pensare ai numeri come un infinito incompleto \`e un
alternativo viabile e interessante al pensare ai numeri come un infinito
completato, alternativo che conduce a grandi simplificazioni in alcune aree
della matematica e che ha legami forti con la teoria della complessit\`a
computazionale.

I due modi, P e A, di pensare ai numeri conducono a sistemi di numeri
diversi. Quello che \`e un numero finito per P non \`e necessariamente
numero finito per A. Nella matematica contemporanea, il concetto del finito
viene definito tramite l'infinito completato~\N.
Non esiste un concetto chiaro del finito in termini del quale si pu\`o
definire l'infinito come il non-finito. Nella matematica contemporanea,
platonica, si va nel senso opposto e si definisce il finito come il
non-infinito.

Forse dovremmo avere un congresso interdisciplinare sul finito. Co\-me ha detto
Orazio, ``Ci sono meno cose in cielo e in terra, Amleto, di quante la tua
filosofia abbia sognato.''
\bigbreak

\centerline{\bf Bibliografia}\medskip

\frenchspacing \parindent=0pt

[1] Stephen Bellantoni and Stephen Cook, ``A new recursion-theoret\-ic
characterization of the poly-time functions'', {\it Computational
Complexity}, 2:97--110, 1992.
\medskip

[2] Stephen Bellantoni, {\it Predicative Recursion and Computational 
Complexity}, Ph.D. Thesis, University of Toronto, 1992. 

\pdflink{ftp://ftp.cs.toronto.edu/pub/reports/theory/cs-92-264.ps.Z}
\medskip

[3] Daniel Leivant, ``Ramified recurrence and computational
complexity I: Word recurrence and poly-time'', in Peter Cole and
Jeffrey Remmel, editors, {\it Feasible Mathematics II}, 
Perspectives in Computer Science, pages 320-343, 
Birkhauser-Boston, New York, 1994.
\medskip

[4] Edward Nelson, {\it Predicative Arithmetic}, Mathematical Notes 
\#32, Princeton University Press, Princeton, New Jersey, 1986.

\yy
\pdflink{http://www.math.princeton.edu/~nelson/books/pa.pdf}
\zz
\medskip

[5]~ ---, {\it Radically Elementary Probability Theory},
Annals of Mathematics Studies, Number 117,
Princeton University Press, Princeton, New Jersey, 1987.

\yy
\pdflink{http://www.math.princeton.edu/~nelson/books/rept.pdf}
\zz
\medskip

[6] A. M. Turing, ``On computable numbers, with an application to the
Entscheidungsproblem'', Proceedings of the London Mathematical Society,
Series 2, 42, pp. 230--265, 1936. Errata in 43, pp. 544--546, 1937.

\pdflink{http://www.abelard.org/turpap2/tp2-ie.asp}
\medskip


\bye
