Effective Procedures
The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectiv...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Philosophies |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2409-9287/8/2/27 |
| _version_ | 1797225499640987648 |
|---|---|
| author | Nathan Salmon |
| author_facet | Nathan Salmon |
| author_sort | Nathan Salmon |
| collection | DOAJ |
| description | The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the notion of an effective procedure, without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis, that the class of effective procedures is undecidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though the result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict. |
| first_indexed | 2024-03-11T04:37:32Z |
| format | Article |
| id | doaj.art-ab2ebacb2b7d454a85bbc4d7f09cb251 |
| institution | Directory Open Access Journal |
| issn | 2409-9287 |
| language | English |
| last_indexed | 2024-04-24T14:09:59Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Philosophies |
| spelling | doaj.art-ab2ebacb2b7d454a85bbc4d7f09cb2512024-04-03T09:30:38ZengMDPI AGPhilosophies2409-92872023-03-01822710.3390/philosophies8020027Effective ProceduresNathan Salmon0Department of Philosophy, University of California, Santa Barbara, CA 93106-3090, USAThe “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the notion of an effective procedure, without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis, that the class of effective procedures is undecidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though the result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict.https://www.mdpi.com/2409-9287/8/2/27algorithmChurch’s thesisChurch–Turing thesiscomputabilitydecidabilitydecision problem |
| spellingShingle | Nathan Salmon Effective Procedures Philosophies algorithm Church’s thesis Church–Turing thesis computability decidability decision problem |
| title | Effective Procedures |
| title_full | Effective Procedures |
| title_fullStr | Effective Procedures |
| title_full_unstemmed | Effective Procedures |
| title_short | Effective Procedures |
| title_sort | effective procedures |
| topic | algorithm Church’s thesis Church–Turing thesis computability decidability decision problem |
| url | https://www.mdpi.com/2409-9287/8/2/27 |
| work_keys_str_mv | AT nathansalmon effectiveprocedures |