Keywords
formal logic
first-order logic
Entscheidungs problem
partial propositional logics
semi-Thue production systems
problemas de decisión
lógicas formales
lógicas de primer orden
lógicas proposicionales parciales
Entscheidungsproblem
sistemas productivos semi-Thue
How to Cite
Abstract
The recursion theory states that a decision problem is recursively solvable if there is a mechanical process to solve it. Within the context of formal logic, the decision problem consist to determine whether any wellformed formula of the system is a theorem or not.
This paper first discusses, among other things, the famous problem of decision of the canonical first-order logic F0 (also called Entscheidungsproblem) from a modern perspective. Then we study the decision problem of the partial propositional logics. It exploits the development achieved by recursion theory and semi-Thue production systems after the work of Post and Kleene in the 40’s and Davis in the early 70’s, among others, to explain a solution to these decision problems.
References
Church, A. (1936) “A note on the Entscheidungsproblem”, The Journal of Symbolic Logic 1(1): 40–41.
Church, A. (1956) Introduction to Mathematical Logic, Vol. 1. Princeton University Press, Princeton NJ.
Davis, M. (1958) Computability and Unsolvability. Dover Publications, New York.
Davis, M.; Weyuker, E. (1983) Computability, Complexity, and Languages. Academic Press, Boston.
Dekker, J.C.E. (1976) Equivalencia Recursiva. Editorial CAEM, San José.
Hennie, F. (1977) Introduction to Computability. Addison-Wesley, Boston MA.
Hopcroft, J.; Ullman, J. (1979) Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading MA.
Kfoury, A.J.; Moll, R.N.; Arbib, M.A. (1982) A Programming Approach to Computability. Springer-Verlag, New York.
Linial, S.; Post, E. (1949) “Recursive unsolvability of the deductibility, Tarsky’s completeness and independence of axioms problems of the propositional calculus”, Bulletin of the American Mathematical Society 55: 50.
Piza, E. (2001) Aritmética Recursiva y Algunas de sus Aplicaciones, Editorial CIMPA, San José.
Rogers, H. (1967) Theory of Recursive Function and Effective Computability. McGraw-Hill, New York.
Soare, R. (1980) Recursive Enumerate Sets and Degrees: a Study of Computable Functions and Computable Generated Sets. Springer-Verlag, Berlin.
Turing, A. (1936) “On computable numbers, with an application to the “Entscheidungsproblem”, Proceedings of the London Mathematical Society 42(2) 230–265.