DECISION PROBLEMS AND RECURSIVENESS IN FORMAL LOGIC SYSTEMS

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 Entschei- dungsproblem) 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.

Keywords

• problemas de decisión
• lógicas formales
• lógicas de primer orden
• lógicas proposicionales parciales
• Entscheidungsproblem
• sistemas productivos semi-Thue