Natural limitations of algorithmic procedures in logic
Mundici, Daniele
Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, Tome 68 (1980), p. 101-105 / Harvested from Biblioteca Digitale Italiana di Matematica
Access to full text
Full (PDF)
Full (DjVu)

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.

Publié le : 1980-09-01
@article{RLINA_1980_8_69_3-4_101_0,
     author = {Daniele Mundici},
     title = {Natural limitations of algorithmic procedures in logic},
     journal = {Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti},
     volume = {68},
     year = {1980},
     pages = {101-105},
     zbl = {0518.03005},
     mrnumber = {0670813},
     language = {en},
     url = {http://dml.mathdoc.fr/item/RLINA_1980_8_69_3-4_101_0}
}

Mundici, Daniele. Natural limitations of algorithmic procedures in logic. Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, Tome 68 (1980) pp. 101-105. http://gdmltest.u-ga.fr/item/RLINA_1980_8_69_3-4_101_0/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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