|
La questione non è così semplice perché prima devi definire cos'è un algoritmo.
In genere si definisce algoritmo una sequenza determinata (possibilmente finita) di passi elementari.
I passi elementari sono definiti dal modello computazionale, quindi a seconda delle fondamenta la dimostrazione cambia.
Ad esempio puoi scegliere di usare come modello computazionale quello random access machine, che in pratica è una macchina di Turing. Oppure puoi decidere di basarti sul lambda calcolo.
Rimane anche da vedere cosa vuol dire sequenza, iterazione e selezione nel contesto.
(in realtà, una volta dimostrato il teorema per ad es. macchine di Turing, la tesi di Church-Turing assicura l'equivalenza per gli altri modelli computazionali)
Di più non saprei dire perché non ho mai cercato la dimostrazione, e in realtà non ho nemmeno ancora fatto il corso di informatica teorica che però dovrei fare l'anno prossimo all'uni.
Ultima modifica effettuata da pierotofy il 03/07/2016 alle 16:56 | 
Mi scuso se non mi sono fatto vivo per un bel po' di tempo, ero occupato..
