Geodesic
Natural limitations of algorithmic procedures in logic
Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali, Série 8, Tome 69 (1980) no. 3-4, pp. 101-105 Cet article a éte moissonné depuis la source Biblioteca Digitale Italiana di Matematica

Voir la notice de l'article

I più semplici aspetti (quantistici e relativistici) dei procedimenti di calcolo vengono matematizzati: quindi si ricavano risultati limitativi per quanto riguarda (i) la realizzabilità pratica dell’interpolazione di Craig, e (ii) la decidibilità pratica dell’aritmetica con quantificatori limitati. 
@article{RLINA_1980_8_69_3-4_a1,
     author = {Mundici, Daniele},
     title = {Natural limitations of algorithmic procedures in logic},
     journal = {Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali},
     pages = {101--105},
     year = {1980},
     volume = {Ser. 8, 69},
     number = {3-4},
     zbl = {0518.03005},
     mrnumber = {0670813},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RLINA_1980_8_69_3-4_a1/}
}
TY  - JOUR
AU  - Mundici, Daniele
TI  - Natural limitations of algorithmic procedures in logic
JO  - Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali
PY  - 1980
SP  - 101
EP  - 105
VL  - 69
IS  - 3-4
UR  - http://geodesic.mathdoc.fr/item/RLINA_1980_8_69_3-4_a1/
LA  - en
ID  - RLINA_1980_8_69_3-4_a1
ER  - 
%0 Journal Article
%A Mundici, Daniele
%T Natural limitations of algorithmic procedures in logic
%J Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali
%D 1980
%P 101-105
%V 69
%N 3-4
%U http://geodesic.mathdoc.fr/item/RLINA_1980_8_69_3-4_a1/
%G en
%F RLINA_1980_8_69_3-4_a1
Mundici, Daniele. Natural limitations of algorithmic procedures in logic. Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali, Série 8, Tome 69 (1980) no. 3-4, pp. 101-105. http://geodesic.mathdoc.fr/item/RLINA_1980_8_69_3-4_a1/

[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman (1974) - The design and analysis of computer algorithms, Addison-Wesley, Mass. | MR | Zbl

[2] J.L. Bell, M. Machover (1977) - A course in mathematical logic, North-Holland, Amsterdam. | MR | Zbl

[3] C.C. Chang, H.J. Keisler (1977) - Model theory, second ed., North-Holland, Amsterdam. | MR

[4] J. Ferrante, C.W. Rackoff (1979) - The computational complexity of logical theories, Lecture Notes in Math., 718, Springer, Berlin. | MR | Zbl

[5] M.J. Fischer, M.O. Rabin (1974) - Super-exponential complexity of Presburger arithmetic, «SIAM-AMS Proceedings», 7, 27-41. | MR | Zbl

[6] S.P. Gudder (1979) - Stochastic methods in quantum mechanics, North-Holland, Amsterdam. | MR | Zbl

[7] A.R. Meyer (1974) - The inherent complexity of theories of ordered sets, in: «Proc. Int. Cong. Math.», Vancouver, 2, Canadian Math. Congress, 477-482. | MR

[8] J.D. Monk (1976) - Mathematical logic, Springer, Berlin. | MR | Zbl

[9] D. Mundici (1982) - Compactness — JEP in any logic, «Fund. Math.», to appear, | MR

[10] D. Mundici (1981) - Robinson's consistency theorem in soft model theory, «Trans. AMS», 263, 231-241. | DOI | MR | Zbl

[11] D. Mundici - Complexity of Craig's interpolation, «J. Symb. Logic», to appear.

[12] D. Mundici - Impracticable theorem-proving Turing machines, to appear.

[13] D. Mundici - Natural limitations of decision procedures for arithmetic with bounded quantifiers, to appear.

[14] M.O. Rabin (1977) - Decidable theories, in: Handbook of math. logic (editor J. Barwise) North-Holland, Amsterdam, 595-630.

[15] J.E. Savage (1976) - The complexity of computing, Wiley, New York.

[16] L.J. Stockmeyer (1974) - The complexity of decision problems in automata theory and logic, Proj. MAC Tech. Report, 133.