# Posts Tagged ‘Algorithmically’

## Impossibility Paradox of Computers by Curry Paradox

Posted by allzermalmer on July 29, 2013

There was a paper called “Computer Implication and the Curry Paradox”. It was authored by both Wayne Aitken and Jeffery A. Barrett, which appears in Journal of Philosophical Logic vol. 33 in 2004.

Suppose an Implication Program has two input statements that are about the behavior of the program, then it tries to deduce the second statement from the first statement by some specified rules in it’s library.

If program finds a deduction of the second statement from the first statement, then the program halts and has output of 1 to signal proof has been found.

The Implication Program can prove statements involving the Implication Program itself.

It is assumed throughout the paper that programs are written in a fixed language for a computer with unlimited memory.

The Impossibility Theorem basically states that “no sufficiently powerful implication program can incorporate an unrestricted form of modus ponens.”

One of the consequences of this Impossibility Theorem is that “modus ponens is an example of a valid rule of inference that can be defined algorithmically, but cannot be used by the implication program.”

Assume (1) that property C(X) is defined to hold if and only if X having property X implies Goldbach’s Conjecture. Furthermore, suppose (2) that C (C). Thus, by the definition of C (X) it implies that C (C) implies Goldbach’s Conjecture. Since C (C) is true by assumption, then it follows by Modus Ponens that Goldbach’s Conjecture is true.

This doesn’t prove Goldbach’s Conjecture yet. However, it does prove that C (C) implies Goldbach’s Conjecture. So by the definition of C (X), it follows that C (C) is true. And by the use of Modus Ponens, Goldbach’s Conjecture is true.

A statement is a list, i.e.  [prog, in, and out]. Prog is a program considered as data, and in is an input for prog, and out is an anticipated output.

A statement is called true if the program prog halts with input in and output out. A statement that isn’t true is called false.

“There is a program to check if but not to test whether [prog, in, out] is a true statement. Given [prog, in, out] as an input, it ﬁrst runs prog as a sub-process with input in. If and when prog halts, it compares the actual output with out. If they match then the program outputs 1; if they do not match, the program does something else (say, outputs 0). This program will output 1 if and only if [prog, in, out] is true, but it might not halt if [prog, in, out] is false. Due to the halting problem, no program can check for falsity.”

So there is a program that check whether [prog, in, out] is a true statement, but the program can’t test whether [prog, in, out] is a true statement. From the Halting problem, no program can check for falsity. So the program can’t check for it’s own falsity, but can check for it’s truth.

It will use 1 as a signal of positive result, and 0 to signal a negative results. However, failure to halt also indicates, but is not a signal to a real use,  a negative result. So failure of the program to halt doesn’t signal a negative result, but it does indicate a negative result.

“A rule is a program that takes as input a list of statements and outputs a list of statements…A valid rule is a rule with the property that whenever the input list consists of only true statements, the output list also consists of only true statements.”

The output list will include the input list as a sublist, and that the rule halt for all input lists.

Take the program AND. This specific program expects as an input a list of two statements. These two statements are [A,B]. The AND Program first checks the truth of A in manner indicated above. If the program determines A is true, then it checks the truth of B. If B is true, then it outputs 1. Now if either A or B is false, the AND program fails to halt.

“A library is a list of rules used by an implication program in its proofs. We assume here that the library is finite at any given time. A valid library is one that contains only valid rules.”

“Consider the implication program ⇒ deﬁned as follows. The program ⇒ expects as input a list of two statements [A, B]. Then it sets up and manipulates a list of sentences called the consequence list. The consequence list begins as a singleton list consisting only of A. The program ⇒ then goes to the library and chooses a rule. It applies the rule to the consequence list, and the result becomes the new consequence list. Since rules are required to include the input list as a sublist of the output list, once a statement appears on any consequence list it will appear on all subsequent consequence lists. After applying a rule, the program ⇒checks whether the consequent B is on the new consequence list. If so, it outputs 1; otherwise it chooses another rule, applies it to update the consequence list, and checks for B on the new consequence list. It continues to apply the rules in an exhaustive way until B is found, in which case ⇒outputs 1. If the consequent B is never found, the implication program ⇒does not halt.”

Take the Modus Ponens Program. This program expects an input list of statements, and from this it starts by forming empty result list. It searches the input list for any statement of the form [–>,[A,B],1] where A and B are statements. From all the statements, it searches to check if A is a statement on the input list. If A is found, then Modus Ponens Program adds B to the result list. The Program outputs a list that shows all the statements in the input list that are followed by all the statements of the result list (if any statements).

“The Modus Ponens program is a rule. A rule is valid if, for an input list of true statements, it only adds true statements. From the definition of –>, if [–>, [A,B],1] and A are on the input list and if they are both true and if the library is valid, then B will be true. So, MP is a valid rule if the library used by –> is valid. “

The EQ program expects an input list that contains [m,n], which are two natural numbers. Supposing m=n, then the EQ outputs 1, or outputs O. This is an example that some statements are clearly false. So let false be the false statement [EQ,[0,1],1]. If 0=1, then the EQ outputs 1, which is truth. This shows some statements are clearly false.

“Consider the program CURRY defined as follows. It expects a program X as input. Then it runs ⇒ as a subprocess with input [[X, X, 1], false]. The output of the subprocess (if any) is then used as the output of CURRY. If X checks for a particular property of programs, then the statement [X, X, 1] asserts that the program X has the very property for which it checks. The program CURRY when applied to program X can be thought of as trying to ﬁnd a proof by contradiction that the statement [X, X, 1] does not hold.”

There is only way that CURRY can output 1 with input X. This is done by if –> outputs 1 with input [[X,X,1}, false].  This is what lies behind the Ad Hoc Rule (AH).

The AH expects a list of statements as input. From there it begins producing an empty result list. It than checks its input for statements that take the form of [CURRY, X, 1] where X is a program. For all such statements on input list, AH adds the statement [–>,[[X,X,1], false] to the result list. The AH will than construct a result list, which contains statements in the input list followed by the statements of the result list (if any).

AH is a valid rule because the statements on the input list are true and AH only adds true statements to form the output list. AH is ad hoc because it is specifically designed for the CURRY program.

“We now describe an algorithmic version of the Curry paradox. We assume that the library is valid and contains MP and AH. Consider what happens when we run ⇒ with input [[ CURRY, CURRY, 1], false]. First a consequence list containing the statement [ CURRY, CURRY, 1] is set-up. Next rules from the library are applied to the consequence list. At some point the Ad Hoc Rule AH is applied and, since [ CURRY, CURRY, 1] is on the consequence list, [⇒, [[CURRY, CURRY, 1], false], 1] is added to the consequence list. Because of this, when MP is next applied to the consequence list, false will be added to the list. Since the initial input had the statement false as the second item on the input list, ⇒will halt with output 1 when false appears on the consequence list.”

So the Implication Program outputs 1 with input of [[CURRY, CURRY, 1], false]. Based on the definition of CURRY Program, it implies that CURRY outputs 1 as CURRY is given as an input. Basically, the statement [CURRY, CURRY, 1] is true. A false statement is true.

Suppose that –> is applied to [[CURRY, CURRY, 1], false]. Because the antecedent [CURRY, CURRY, 1] is true, all statements added to the consequence list will also be true. But the statement false is added to the consequences list, which means that false is true, which is a contradiction.

The Curry Paradox has occurred in a concrete setting of a perfectly well-defined program and careful reasoning about the expected behavior.

The Curry Paradox proves that any library containing the Modus Ponens program and Ad Hoc Rule are not valid. AH is unconditionally valid, so we can conclude that MP is not valid in the case where all the other rules in the library are valid.

“We conclude from this that there are valid inference rules (including MP) that are valid only so long as they are not included in the library of rules to be used. Informally, we can say that there are valid rules that one is not allowed to use (in an unrestricted manner) in one’s proofs. It is the very usage of the rule in inference that invalidates it.”

In order to maintain a valid open library, one must check that the rule is valid itself and that it remains valid when added to the library. A rule is independently valid if it is valid regardless of which library is used by the implication library. The Ad Hoc Rule is an example of an independently valid rule. Any library consistent of only independently valid rules is valid.

The Mods Ponens rule isn’t independently valid. The Modus Ponens rule is contingent on the nature of the library. The Curry Paradox itself provides an example of libraries which MP is not valid.

It is thought that the source of the paradox can be considered to be the misuse of MP. It is suggested that modus ponens is the source of the classical Curry paradox