Newsgroup: it.scienza.informatica
Titolo: Tesi di Church

Salve a tutti.
Premetto che non so un granche' delle macchine di Turing e
di cio' che ci sta attorno, ma la curiosita' mi e' sorta sfogliando
un po' un libro di matematica.
La tesi di Church afferma che una funzione deve essere ricorsiva
per essere calcolabile e viceversa, ma a me una funzione
"elementare" (come ad esempio la printf() in C) non sembra molto
ricorsiva; cosi' io non definirei "calcolabili" le funzioni ricorsive che
entrano in loop, magari chiamando se stesse senza porre alcun
controllo... insomma, la tesi di Church mi appare formulata al
contrario.. :-)
Credo di attribuire un significato sbagliato ai termini "funzione",
"calcolabile" e "ricorsiva", ma sul libro c'era solo un paragrafetto en
passant...
Chi mi sa sciogliere il dubbio?
Ciao
Marino

 Chi mi sa sciogliere il dubbio?
Si, per funzioni ricorsive si intendono quelle che nel corpo hanno 
un'invocazione a se stesse, ma comprendono anche quelle che non hanno nessuna 
invocazione come caso speciale. Dipende dai contesti purtroppo. Se stai 
trattando di programmazione spicciola la distinzione e` tra ricorsive (che 
hanno invocazioni) e non ricorsive (che non hanno invocazioni), perche` non 
c'e' possibilita` di equivoco (fuori da queste due non c'e` praticamente 
altro). Se stai trattando di calcolabilita` ci sono piu` classi e ricorsive e` 
quella piu` "interna".
La defunizione dice che una funzione e` "ricorsiva" se e` "calcolabile con una 
macchina di turing" o meglio se esiste una macchina di turing che calcola 
sempre e solo f[x].

 controllo...
Una funzione ricorsiva primitiva non puo' entrare in loop - 
grossolanamente, sono funzioni C implementabili usando solo il "for" 
(pascallike, cioe' con un numero di iterazioni parametrico ma limitato). 
Una funzione computabile invece e' implementabile usando "while" (sempre in 
senso pascallike).
Occhio anche alla confusione tra "primitive ricorsive " e "parziali 
ricorsive" :). Le seconde consistono nel set di funzioni che si ottiene con 
le regole delle RP, ma permettendo funzioni parziali (ovvero quelle non 
definite per qualche valore del loro dominio, tipo f(x)=1/x dove x intero) 
e aggiungendo un'altra operazione. La definizione di "computabilita'" che 
fa uso di "funzioni" identifica un sottoinsieme delle seconde (che 
comprende le prime ;-).
-- 
Life's something u don't get out alive..
ObjectZone - 
http://space.tin.it/computer/csadun

 per essere calcolabile e viceversa, ma a me una funzione
In breve:
L'informatica e' la scienza che si occupa di trattare, rappresentare,
elaborare l'informazione; per far questo ci si serve di una macchina
che manipola in qualche modo una sua rappresentazione dei dati per
produrne di nuovi.
Domandone da 100 milioni di euro: ma questa macchina e' in grado di
cacolare proprio tutte le funzioni che un umano sa calcolare?
Ad esempio, prendi la funzione somma: questa e' una funzione che tu
sai calcolare, dunque e' una *funzione calcolabile*.
Di contro, la funzione che ad ogni persona associa quanto tempo gli
resta da vivere non e' calcolabile nemmeno per un uomo, percio' *NON*
e' una funzione calcolabile.
Studiando la risposta al domandone di sopra, i matematici avevano
bisogno di una macchina che sapesse calcolare funzioni, in modo da
vedere se questa era piu' o meno in grado di coprire tutto il
calcolabile.
Essendo pero' i matematici un po' astratti, ognuno si invento' una
macchina ideale, che non esisteva in realta', servendo solo come
modello mentale di macchina che calcola.
Se ne inventarono diverse, alcune di queste _si chiamano_:
 (*) Macchina di Turing
 (*) Unlimited Register Machine
 (*) Macchina di Post
 (*) Funzioni ricorsive
Dunque le funzioni ricorsive sono un particolare modello di calcolo.
Si e' pero' notato che tutti questi modelli avevano la stessa potenza
di calcolo: se una funziona la sapeva calcolare la Macchina di Turing,
allora era calcolabile anche da tutte le altre, e viceversa.
Il fatto che, per quanto ci si sforzasse, non si riuscisse a trovare
un modello di calcolo piu' potente della macchina di turing, ha
portato Church a pensare che la macchina di turing (e dunque la URM,
la macchina di Post, le funzioni ricorsive...) fossero effettivamente
la piu' potente delle macchine per il calcolo, e dunque che siano in
grado di calcolare *tutte* le funzioni calcolabili.
Ovviamente, questo asserto (la Tesi di Church) non e' dimostrabile,
perche' per farlo dovrei costruire tutte le macchine di turing che
calcolano tutte le *infinite* funzioni calcolabili...
Sarebbe pero' confutabile: se io trovassi una funzione calcolabile,
per la quale non esiste la macchina di turing che la computa, avrei
fatto vedere che c'e' almeno quella cosa che una Macchina di Turing
non sa fare.
Tieni conto che anche il PC di casa tua lo puoi vedere come una
macchina di turing (ha la stessa potenza di calcolo), e che ogni volta
che qualcuno scrive un programma sta, di fatto, dimostrando che quella
funzione calcolabile (per la quale e' stato costruito il programma)
puo' essere calcolata da macchina di Turing, mentre finora non si e'
trovato un solo esempio a sfavore della tesi di church.
Per questo motivo, possiamo affermare che Church aveva ragione, sulle
basi delle forti evidenze di cui ti ho appena parlato.
Spero di essere stato sufficientemente chiaro! ;-)
Ciao!
-- 
__/\__ * this mail has been written by Talpa Stellare
\ TS / * che da piccolo una volta e' morto.
 |/\|  * icq# 78630739 - togli i caratteri maiuscoli x e-mail

 Chi mi sa sciogliere il dubbio?
Credo che per chiarire i tuoi dubbi devi fare una netta distinzione tra funzioni
e programmi.
In teoria della calcolabilità si intende per funzione lo stesso concetto usato
in matematica, ossia un ente astratto che associa ad ogni possibile valore di
input un valore di output, senza alcun riferimento al modo con cui si può
calcolarlo.
Un programma invece è la descrizione, in un particolare formalismo o linguaggio,
di una procedura che calcola una funzione.
Con questo significato le funzioni del C sono dei programmi.
A stretto rigore di termini, quindi non ha senso parlare di funzioni che entrano
in loop, al massimo si parla di funzioni che non sono definite (ossia che non
hanno output) per alcuni valori di input. Mentre ovviamente ha senso per i
programmi.
Il termine ricorsivo ha due interpretazioni. Una è quella usata comunemente
nella pratica della programmazione, ed è quella che intendevi tu, ossia un
programma che richiama se stesso. Questo significato quindi si applica ai
programmi e non alle funzioni (intendendo per funzioni le funzioni
"matematiche").
L' altra interpretazione è quello della teoria della calcolabilità che si
applica proprio alla funzioni in senso matematico, ed il termine più completo è
"ricorsivo parziale", perchè ricorsivo da solo può dare ambiguità con "ricorsivo
primitivo" .
Nella t.d.c. ci sono molti formalismi per descrivere programmi che calcolano
funzioni. I più famosi sono quello delle macchine di Turing e quello delle
"funzioni ricorsive parziali". Più che spiegare in cosa consistono questi
formalismi, ti faccio degli esempi per spiegare il significato dei termini
usati.
Allora, per esempio, una funzione (sempre in senso matematico) si dice
Turing-calcolabile, se esiste una macchina di turing che la calcola (in questo
contesto "macchina di turing" è equivalente a "programma"). Allo stesso modo una
funzione si dice "ricorsiva parziale" se esiste un programma nel formalismo
delle "funzioni ricorsive parziali" che la calcola.
In realtà in senso stretto, la definizione delle funzioni ricorsive parziali non
ha niente a che fare con i programmi: è solo una definizione matematica di un
insieme di funzioni. Ma sarebbe proprio difficile ignorare il fatto che questa
definizione fornisce anche, per ciascuna funzione che definisce "ricorsiva
parziale", una procedura di calcolo, cioè un programma. Quindi è corretto
considerare questo formalismo allo stesso modo degli altri, ossia un formalismo
per descrivere programmi che calcolano funzioni.
Tutta questa distinzione tra funzioni e programmi è significativa, ovviamente,
perchè il risultato fondamentale della t.d.c è che esistono funzioni non
calcolabili, ossia funzioni per le quali in un certo formalismo non esiste
nessun programma che le calcola.
E qui veniamo alla tesi di Church. Ci si chiede: qual' è il formalismo che
permette di scrivere programmi per tutte le funzioni che intuitivamente sono
calcolabili? Church afferma che è appunto quello delle "funzione ricorsive
parziali".
In realtà non so se lui usasse proprio questo formalismo, perchè lui ne ha
inventato un altro...ma siccome si può dimostrare che il suo è equivalente a
questo, come anche è equivalente alle macchine di turing, il problema non si
pone.
Poichè si fa riferimento ad una nozione intuitiva di calcolabilità, la tesi di
church non è un teorema che possa essere dimostrato. Trae la sua forza solo dal
fatto che esistono innumerevoli formalismi equivalenti tra loro, per i quali
cioè si può dimostare che se in uno esiste un programma che calcola una certa
funzione, allora si può trovare un programma nell' altro che calcola la stessa
funzione.
Inoltre nessuno ha mai trovato un formalismo più potente, ossia nel quale
esistano programmi che calcolano funzioni che non sono calcolabili negli altri
formalismi.

 Spero di essere stato sufficientemente chiaro! ;-)
Assolutamente!
Ringrazio te e tutti gli altri che hanno risposto per aver soddisfatto la
mia curiosita'; l'argomento affascina, ma studi piu' approfonditi me li
riservo per l'universita'.. :-) 
Ciao
Marino
-- 
"It's only after you've lost everything that you are free to do anything"

Volevo solo aggiungere una cosa sul fatto che le funzioni, "vanno in 
loop" (divergono e' il termine più corretto), una funzione che diverge, 
ha un espressivita maggiore rispetto ad una che puo' colo convergere, 
infatti ci permette di risolvere problemi semidecidibili