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