Calcolabilit`a: temi d’esame
Simone Martini November 5, 2008
1 Approfondimenti tecnici
1. Altri approcci alla calcolabilit`a (e.g., i sistemi di (Post-)Markov [Min67, Odi89]).
2. La funzione di Ackermann: una funzione totale calcolabile, ma non primitivo- ricorsiva.
3. Discussione della tesi di Church; si pu`o partire da [Odi89], Vol 1, Sez. I.8.
Oppure da [Cop02].
4. Calcolabilit`a sui reali (“veri”) alla Blum-Shub-Smale, [BSS89].
5. Codifica delle funzioni ricorsive in λ-calcolo, [HS90].
6. I teoremi di Rice e di Rice-Shapiro, [Cut80], pag. 105 e 130.
2 Calcolabilit`a e. . .
1. Calcolabilit`a in analisi e fisica.
Un riferimento canonico per risultati sulla calcolabilit`a in analisi `e [PER89].
Per una prima riflessione introduttiva, vedi [Ghe08].
2. Hypercomputation (computazione al di l`a della MdT, attraverso e.g., pro- cessi fisici continui. Il tema `e una sorta di generalizzazione del precedente).
Vedi www.hypercomputation.net e la bibliografia ivi riportata (sito fermo al 2007).
3. (i) Complessit`a secondo Kolmogorov-Chaitin;
(ii) Il numero non calcolabile Ω;
[Cal02, Cha04] ed altri testi di Gregory Chaitin 4. DNA computing, [CP01, LE99]
5. Quantum computing, in generale/epistemologia [Lup04, LE99, NC00] (e.g.
What does quantum physics tell us about computation? in [LE99]).
6. L’algoritmo di Schor per la fattorizzazione in quantum computing.
1
References
[BSS89] L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive func- tions and universal machines. Bull. Amer. Math. Soc. (N.S.), 21:1–46, 1989.
[Cal02] C. Calude. Information and randomness. Springer, 2002.
[Cha04] Gregory J. Chaitin. Algorithmic information theory. Cambridge Uni- versity Press, 1988-2004.
[Cop02] B.J. Copeland. The church-turing thesis. In E. Zalta, editor, The Stanford Encyclopaedia of Philosophy. 2002.
[CP01] C. Calude and G. Paun. Computing with cells and atoms. Taylor and Francis, 2001.
[Cut80] N. Cutland. Computability, an introduction to recursive function the- ory. Cambridge University Press, 1980.
[Ghe08] G. Gherardi. Computability and incomputability of differential equa- tions. In G. Corsi and R. Lupacchini, editors, Deduction, Computation, Experiment. Springer, 2008.
[HS90] J. R. Hindley and J. P. Seldin. Introduction to combinators and lambda-calculus. Cambridge University Press, 1990.
[LE99] R. Lupacchini and G. Tamburrini (Eds.). Grounding effective processes in empirical laws. Bulzoni, 1999.
[Lup04] R. Lupacchini. Elementi di computazione quantistica. CLUEB, 2004.
[Min67] M. Minsky. Computation: finite and infinite machines. Prentice-Hall, 1967.
[NC00] M.A. Nielsen and I.L. Chuang. Quantum computation and quantum information. Cambridge university press, 2000.
[Odi89] P. Odifreddi. Classical recursion theory. North-Holland, 1989.
[PER89] M.B. Pour-El and J.I. Richards. Computability in Analysis and Physics. Springer, 1989.
2
