The decision problem for effective procedures (Q6113688): Difference between revisions

Consider the following claim: \textbf{Claim.} The class of effective procedures is undecidable. The article has two goals: (i) to prove Claim and (ii) to do so without formalizing the notion of effective procedure (e.g. without equating it with the notion of Turing computable function or other formal notions studied in computability theory). I explain how the author proves Claim. Then, I comment on another result of the paper that I take to be more interesting because it points to an unclarity concerning the notions of procedure and instruction that is relevant to specific views concerning mathematics. \textbf{The proof of Claim.} The author relies on the following elements to prove Claim 1: (i) the primitive notions of property, class of objects, and procedure; (ii) the characterized notions (the characterized notions are defined or, at least, described in terms of the primitive notions) of \textit{judgment procedure}, \textit{effective procedure}, \textit{decision procedure}, \textit{self-certification}, and \textit{decidability} (relative to a universe of objects); and (iii) the lemma that the class of self-certifying decision procedures is undecidable. With these elements, the outline of the proof of Claim is as follows: (i) if the class of effective procedures is decidable, then one can define an effective procedure to decide the class of self-certifying decision procedures; (ii) the class of self-certifying procedures is undecidable; (iii) therefore, the class of effective procedures is undecidable. Let us unpack the above elements. \underline{Judgment procedure}. A \textit{judgment procedure} \(\varphi^C_P\) on a class \(C\) of objects for a property \(P\) is a finite list of finitely specified instructions defining a procedure that, given an element \(x\in C\), (i) outputs 1 if the procedure deems \(P(x)\) to hold, (ii) outputs 0 if the procedure deems \(P(x)\) not to hold, and (iii) diverges otherwise. I write \(\varphi^C_P(x)=1\) to mean that \(\varphi^C_P\) deems \(P(x)\) to hold and \(\varphi^C_P(x)=0\) to mean that \(\varphi^C_P\) deems \(P(x)\) not to hold. \underline{Effective procedure}. If a judgment procedure \(\varphi^C_P\) is \textit{effective}, then (i) it is infallible, i.e., for every \(x\in C\), \(\varphi^C_P=1\) if and only if \(P(x)\), and, (ii) for every \(x\in C\), \(\varphi^C_P(x)\) terminates after finitely many steps. \underline{Decision procedure}. A procedure is a \textit{decision procedure} if and only if it is an effective judgment procedure. \underline{Self-certification}. Given a judgment procedure \(\varphi^C_P\), let us define a property \(S\) (the \textit{self-certification} property) such that \(S(\varphi^C_P)\) if and only if \(\varphi^C_P(\varphi^C_P)=1\). \underline{Decidability} (relative to a universe of objects). (The author does not mention the relativity of decidability to a universe of objects, probably because it takes it to be obvious. For example, the authors says that the the method of truth-tables decides ``the class of arguments that are derivable (deducible) in the propositional calculus'' (p. 162). This is true only if the class of atomic propositions is countable. Though the above point is clear (and not mentioning it does not lead the author to any mistake), it is appropriate to mention such relativity in a discussion of decidablity that is so general to allow procedures for any class of objects.) Given a class \(C\), a class \(D\subseteq C\) is decidable in \(C\) if and only if there is a decision procedure that, for every \(x\in C\), it outputs 1 if the \(x\in D\) and 0 otherwise. \textbf{Lemma 1.} Let \(J\) be the class of exactly all judgment procedures. Let \(\delta\) be the property of being both a decision procedure and having property \(S\). Let \(D\subseteq J\) be the class of exactly all decision procedures that have property \(\delta\). \(D\) is undecidable. Proof: Suppose, toward a contradiction, that there is a decision procedure \(\psi^J_{\delta}\) such that \(\psi^J_{\delta}(x)=1\) if \(x\in D\) and \(\psi^J_{\delta}(x)=0\) otherwise. Then, there is a decision procedure \(\psi^J_{\delta^{-1}}\) for the complement property \(\delta^{-1}\) of \(\delta\) in \(J\) (namely: apply \(\psi^J_{\delta}\) and reverse the result). Either \(S(\psi^J_{\delta^{-1}})\) holds or \(S(\psi^J_{\delta^{-1}})\) does not hold. I reason by cases to show that both situations are absurd and, therefore, there is no decision procedure for \(\delta^{-1}\) in \(J\) and, therefore, there is also no decision procedure for \(\delta\) in \(J\) (i.e. the class \(D\) is undecidable). Case 1: suppose that \(S(\psi^J_{\delta^{-1}})\) holds. Therefore, \(\psi^J_{\delta^{-1}}(\psi^J_{\delta^{-1}})=1\). Since \(\psi^J_{\delta^{-1}}\) is a decision procedure, it is infallible. Therefore, \(\delta^{-1}(\psi^J_{\delta^{-1}})\) holds. Therefore, \(\delta(\psi^J_{\delta^{-1}})\) does not hold. Therefore, either \(\psi^J_{\delta^{-1}}\) is not effective or \(S(\psi^J_{\delta^{-1}})\) does not hold. Since \(\psi^J_{\delta^{-1}}\) is a decision procedure, it is effective. Therefore, \(S(\psi^J_{\delta^{-1}})\) does not hold, which is absurd. Case 2: suppose that \(S(\psi^J_{\delta^{-1}})\) does not hold. Therefore, \(\delta(\psi^J_{\delta^{-1}})\) does not hold. Therefore, \(\delta^{-1}(\psi^J_{\delta^{-1}})\) holds. Since \(\psi^J_{\delta^{-1}}\) is infallible, \(\psi^J_{\delta^{-1}}(\psi^J_{\delta^{-1}})=1\). Therefore, \(S(\psi^J_{\delta^{-1}})\) holds, which is absurd. Now, let \(J\) and \(\delta\) be as in Lemma. Consider the following judgment procedure \(\psi^J_{\delta}\): \begin{itemize} \item[1.] Given a judgment procedure \(\varphi^J_P\), determine whether \(\varphi^J_P\) is a decision procedure. \item[2.] If you determine that \(\varphi^J_P\) is not a decision property, conclude that \(\delta(\varphi^J_P)\) does not hold. \item[3.] If you determine that \(\varphi^J_P\) is a decision procedure, determine the result of \(\varphi^J_P(\varphi^J_P)\). \item[4.] If you determine that \(\varphi^J_P(\varphi^J_P)=1\), conclude that \(\delta(\varphi^J_P)\) holds. \item[5.] If you do not determine that \(\varphi^J_P(\varphi^J_P)=1\), conclude that \(\delta(\varphi^J_P)\) does not hold. \end{itemize} With Lemma 1 and the definition of \(\psi^J_{\delta}\), the proof of Claim is as follows: If none of the steps 1-5 of \(\psi^J_{\delta}\) disqualify it from being a decision procedure for \(\delta\), then the class \(D\) of exactly all judgment procedures that have property \(\delta\) is decidable. By Lemma, \(D\) is undecidable. Therefore, at least one step among 1-5 of \(\psi^J_{\delta}\) disqualifies \(\psi^J_{\delta}\) from being a decision procedure. None of the steps 2-5 disqualify \(\psi^J_{\delta}\) from being a decision procedure. Therefore, step 1 disqualifies \(\psi^J_{\delta}\) from being a decision procedure. Therefore, there is no decision procedure to determine whether a judgment procedure is a decision procedure. \textbf{Comments on the notions of procedure and instruction.} In another result, the author shows that, even in simple cases, it is impossible to say whether a finite list of finitely specified instructions is a procedure. Such a result does not threaten Claim, because we know that the notion of effective procedure has instances (e.g. the algorithm to determine whether a natural number is prime) and, therefore, is coherent. To highlight the obscurity of the notion of procedure, consider the following list \(L\) of steps: \begin{itemize} \item[1.] Given a judgment procedure \(\varphi^J_P\), determine whether \(\varphi^J_P\) is a possible argument of \(\varphi^J_P\). \item[2.] If you determine that \(\varphi^J_P\) is not a possible argument of \(\varphi^J_P\), then conclude that \(S\) does not hold for \(\varphi^J_P\). \item[3.] If you determine that \(\varphi^J_P\) is a possible argument of \(\varphi^J_P\), determine whether \(\varphi^J_P(\varphi^J_P)\) yields a result. \item[4.] If you determine that \(\varphi^J_P\) does not yield a result, then conclude that \(S\) does not hold for \(\varphi^J_P\). \item[5.] If you determine that \(\varphi^J_P(\varphi^J_P)=0\), then conclude that \(S\) does not hold for \(\varphi^J_P\). \item[6.] If you determine that \(\varphi^J_P(\varphi^J_P)=1\), then conclude that \(S\) holds for \(\varphi^J_P\). \end{itemize} The author proves the following proposition. \textbf{Proposition.} \(L\) does not describe a judgment procedure. Proof: Suppose that \(L\) describes a judgment procedure \(\psi^J_{S^{-1}}\) where \(S^{-1}\) is the complement of \(S\) in \(J\). Either \(S(\psi^J_{S^{-1}})\) holds or not. I show that both cases are absurd. Suppose that \(S(\psi^J_{S^{-1}})\). Therefore, \(\psi^J_{S^{-1}}(\psi^J_{S^{-1}})=1\). By inspection, \(\psi^J_{S^{-1}}\) is infallible. Therefore, \(S^{-1}(\psi^J_{S^{-1}})\) holds. Therefore, \(S(\psi^J_{S^{-1}})\) does not hold, which is absurd. Now, suppose that \(S(\psi^J_{S^{-1}})\) does not hold. Therefore, \(\psi^J_{S^{-1}}(\psi^J_{S^{-1}})=0\). Therefore, \(S^{-1}(\psi^J_{S^{-1}})\) does not hold. Therefore, \(S(\psi^J_{S^{-1}})\) holds, which is absurd. Therefore, \(L\) does not describe a judgment procedure. If \(L\) describes a procedure, then it describes a judgment procedure (because, whenever it converges, it assigns values in \(\{0,\ 1\}\) and no other values to its arguments). Moreover, if \(L\) is a procedure, then it is a finite list of finitely specified instructions. Since \(L\) does not describe a judgment procedure, it follows that \(L\) does not describe a procedure. Therefore, since \(L\) is a list of finitely specified items, at least one of the items listed in \(L\) is not an instruction. But, then, which step of \(L\) is not an instruction and why? Each step of \(L\) seems to specify a condition and an action (or operation) to carry out if that condition holds. Is that not enough for a step to be an instruction? Or the notions of \textit{conditions}, \textit{actions}, or \textit{operation} are so unclear that, contrary to what appears, at least one step in \(L\) either does not specify a condition or does not specify an action (or operation)? If our understanding of the notions of procedure and instruction (or the related notions of condition, action, and operation) is so deficient, how can we assess, albeit to some degree and non-conclusively, the truth of the Turing Thesis (where what a Turing machine can do is compared with what a human working through exact \textit{instructions} can do)? And how can we clarify those views of mathematics (or, at least some mathematical proofs) as the result of \textit{procedures} that an idealized agent carries out? (Among those that expressed such views, I mention L. E. J. Brouwer (concerning his project of intuitionistic mathematics; see e.g. [\textit{L. E. J. Brouwer}, ``Consciousness, philosophy and mathematics'', in: Actes du Xme congrès international de philosophie. 1235--1249 (1949)]), Gaisi Takeuti concerning the use of an idealized agent to analyse foundational positions; see e.g. [\textit{G. Takeuti}, ``Proof theory and set theory'', Synthese 62, 255--263 (1985)], and Philip Kitcher (concerning his use of the notion of idealized agent to justify mathematics empiristically; see [\textit{P. Kitcher}, The nature of mathematical knowledge. New York - Oxford: Oxford University Press (1983; Zbl 0519.00022)].)