Decision problems and recursiveness in formal logic systems
Saved in:
| Authors: | , |
|---|---|
| Format: | artículo original |
| Status: | Versión publicada |
| Publication Date: | 2017 |
| Description: | 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. |
| Country: | Portal de Revistas UCR |
| Institution: | Universidad de Costa Rica |
| Repositorio: | Portal de Revistas UCR |
| Language: | Español |
| OAI Identifier: | oai:portal.ucr.ac.cr:article/22338 |
| Online Access: | https://revistas.ucr.ac.cr/index.php/matematica/article/view/22338 |
| Keyword: | decision problems 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 |