Mundici: Natural limitations of algorithmic procedures in logic

Mundici, Daniele:
Natural limitations of algorithmic procedures in logic
Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Serie 8 69 (1980), fasc. n.3-4, p. 101-105, (English)
pdf (349 Kb), djvu (218 Kb). | MR 0670813 | Zbl 0518.03005

Sunto

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.

Referenze Bibliografiche

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

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

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

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

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

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

[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 441705

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

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

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

[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.

bdim: Biblioteca Digitale Italiana di Matematica

Un progetto SIMAI e UMI

Referenza completa

Sunto

Referenze Bibliografiche