Representing and Reformulating Diagonalization Methods
Erica Melis⋆ · 1994
Abstract Finding an appropriate representation of planning operators is crucial for theorem provers that work with proof planning. We show a new representation of operators and demonstrate how diagonalization can be represented by operators. We explain how a diagonalization operator used in one proof-plan can be analogically transferred to an operator used in another proof-plan. Finally, we find an operator that is common to all the proof-plans and thus might be considered as the Diagonal Method. This research was supported by the Max-Kade Foundation Keywords: proof planning, analogy, knowledge representation 1 Introduction As pointed out by Bundy [3] and Bledsoe [1], using proof-plans is often very helpful in automated deduction. In planning, operators are needed and therefore an appropriate representation of these operators is crucial for proof planning. The operators have the same function in proof planning as mathematical methods (in the following referred to as mmethods) have in human theorem proving. Since m-methods can be adapted to different proofs, it is also desirable to have mechanisms for adapting operators. To be employed by a human-oriented theorem prover, these operators should allow for representing logical proof methods, such as Indirect Proof, and mathematical methods, such as Cantor's Diagonal method. In this paper we examine whether the presented representation actually covers mathematician's methods and how the methods can be adapted for other proof plans. We do this by analyzing the well-known Diagonal Method which is central and widely applicable in many mathematical proofs concerning computability and decidability, including G"odel's Incompleteness theorem for arithmetic, the Unsolvability of the halting problem, Rice's theorem, and the Second Recursion theorem (see [5]). Although this m-method seems to be clearly understood, not all proofs have an obvious common proof schema, and some proofs are difficult to generate in logical detail.