TSTP Solution File: COM003+2 by CSE---1.6
View Problem
- Process Solution
%------------------------------------------------------------------------------
% File : CSE---1.6
% Problem : COM003+2 : TPTP v8.1.2. Bugfixed v2.2.0.
% Transfm : none
% Format : tptp:raw
% Command : java -jar /export/starexec/sandbox/solver/bin/mcs_scs.jar %s %d
% Computer : n003.cluster.edu
% Model : x86_64 x86_64
% CPU : Intel(R) Xeon(R) CPU E5-2620 v4 2.10GHz
% Memory : 8042.1875MB
% OS : Linux 3.10.0-693.el7.x86_64
% CPULimit : 300s
% WCLimit : 300s
% DateTime : Wed Aug 30 18:35:08 EDT 2023
% Result : Theorem 0.59s 0.74s
% Output : CNFRefutation 0.61s
% Verified :
% SZS Type : -
% Comments :
%------------------------------------------------------------------------------
%----WARNING: Could not form TPTP format derivation
%------------------------------------------------------------------------------
%----ORIGINAL SYSTEM OUTPUT
% 0.03/0.12 % Problem : COM003+2 : TPTP v8.1.2. Bugfixed v2.2.0.
% 0.03/0.13 % Command : java -jar /export/starexec/sandbox/solver/bin/mcs_scs.jar %s %d
% 0.12/0.34 % Computer : n003.cluster.edu
% 0.12/0.34 % Model : x86_64 x86_64
% 0.12/0.34 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
% 0.12/0.34 % Memory : 8042.1875MB
% 0.12/0.34 % OS : Linux 3.10.0-693.el7.x86_64
% 0.12/0.34 % CPULimit : 300
% 0.12/0.34 % WCLimit : 300
% 0.12/0.34 % DateTime : Tue Aug 29 13:40:10 EDT 2023
% 0.12/0.34 % CPUTime :
% 0.21/0.61 start to proof:theBenchmark
% 0.59/0.73 %-------------------------------------------
% 0.59/0.73 % File :CSE---1.6
% 0.59/0.73 % Problem :theBenchmark
% 0.59/0.73 % Transform :cnf
% 0.59/0.73 % Format :tptp:raw
% 0.59/0.73 % Command :java -jar mcs_scs.jar %d %s
% 0.59/0.73
% 0.59/0.73 % Result :Theorem 0.080000s
% 0.59/0.73 % Output :CNFRefutation 0.080000s
% 0.59/0.73 %-------------------------------------------
% 0.59/0.73 %--------------------------------------------------------------------------
% 0.59/0.73 % File : COM003+2 : TPTP v8.1.2. Bugfixed v2.2.0.
% 0.59/0.73 % Domain : Computing Theory
% 0.59/0.73 % Problem : The halting problem is undecidable
% 0.59/0.73 % Version : [Bru91] axioms.
% 0.59/0.73 % English :
% 0.59/0.73
% 0.59/0.73 % Refs : [Gan98] Ganzinger (1998), Email to Geoff Sutcliffe
% 0.59/0.73 % : [Bur87b] Burkholder (1987), A 76th Automated Theorem Proving Pr
% 0.59/0.73 % : [Bru91] Brushi (1991), The Halting Problem
% 0.59/0.73 % Source : [Bru91]
% 0.59/0.73 % Names : - [Bru91]
% 0.59/0.73
% 0.59/0.73 % Status : Theorem
% 0.59/0.74 % Rating : 0.07 v7.5.0, 0.14 v7.4.0, 0.06 v7.3.0, 0.00 v7.0.0, 0.07 v6.4.0, 0.00 v6.3.0, 0.08 v6.2.0, 0.09 v6.1.0, 0.12 v6.0.0, 0.50 v5.5.0, 0.21 v5.4.0, 0.17 v5.3.0, 0.26 v5.2.0, 0.14 v5.0.0, 0.10 v4.1.0, 0.06 v4.0.1, 0.11 v4.0.0, 0.10 v3.7.0, 0.33 v3.5.0, 0.12 v3.4.0, 0.08 v3.3.0, 0.11 v3.2.0, 0.22 v3.1.0, 0.00 v2.5.0, 0.33 v2.4.0, 0.33 v2.2.1
% 0.59/0.74 % Syntax : Number of formulae : 16 ( 1 unt; 0 def)
% 0.59/0.74 % Number of atoms : 52 ( 0 equ)
% 0.59/0.74 % Maximal formula atoms : 7 ( 3 avg)
% 0.59/0.74 % Number of connectives : 39 ( 3 ~; 0 |; 15 &)
% 0.59/0.74 % ( 11 <=>; 10 =>; 0 <=; 0 <~>)
% 0.59/0.74 % Maximal formula depth : 8 ( 6 avg)
% 0.59/0.74 % Maximal term depth : 1 ( 1 avg)
% 0.59/0.74 % Number of predicates : 17 ( 17 usr; 0 prp; 1-4 aty)
% 0.59/0.74 % Number of functors : 2 ( 2 usr; 2 con; 0-0 aty)
% 0.59/0.74 % Number of variables : 44 ( 37 !; 7 ?)
% 0.59/0.74 % SPC : FOF_THM_RFO_NEQ
% 0.59/0.74
% 0.59/0.74 % Comments :
% 0.59/0.74 % Bugfixes : v2.2.0 - Clauses program_halts2_halts3_outputs_def, program_
% 0.59/0.74 % not_halts2_halts3_outputs_def, program_halts2_halts2_outputs_
% 0.59/0.74 % def, program_not_halts2_halts2_outputs_def, p4 by [Gan98].
% 0.59/0.74 %--------------------------------------------------------------------------
% 0.59/0.74 fof(program_decides_def,axiom,
% 0.59/0.74 ! [X] :
% 0.59/0.74 ( program_decides(X)
% 0.59/0.74 <=> ! [Y] :
% 0.59/0.74 ( program(Y)
% 0.59/0.74 => ! [Z] : decides(X,Y,Z) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(program_program_decides_def,axiom,
% 0.59/0.74 ! [X] :
% 0.59/0.74 ( program_program_decides(X)
% 0.59/0.74 <=> ( program(X)
% 0.59/0.74 & program_decides(X) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(algorithm_program_decides_def,axiom,
% 0.59/0.74 ! [X] :
% 0.59/0.74 ( algorithm_program_decides(X)
% 0.59/0.74 <=> ( algorithm(X)
% 0.59/0.74 & program_decides(X) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(program_halts2_def,axiom,
% 0.59/0.74 ! [X,Y] :
% 0.59/0.74 ( program_halts2(X,Y)
% 0.59/0.74 <=> ( program(X)
% 0.59/0.74 & halts2(X,Y) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(halts3_outputs_def,axiom,
% 0.59/0.74 ! [X,Y,Z,W] :
% 0.59/0.74 ( halts3_outputs(X,Y,Z,W)
% 0.59/0.74 <=> ( halts3(X,Y,Z)
% 0.59/0.74 & outputs(X,W) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(program_not_halts2_def,axiom,
% 0.59/0.74 ! [X,Y] :
% 0.59/0.74 ( program_not_halts2(X,Y)
% 0.59/0.74 <=> ( program(X)
% 0.59/0.74 & ~ halts2(X,Y) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(halts2_outputs_def,axiom,
% 0.59/0.74 ! [X,Y,W] :
% 0.59/0.74 ( halts2_outputs(X,Y,W)
% 0.59/0.74 <=> ( halts2(X,Y)
% 0.59/0.74 & outputs(X,W) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(program_halts2_halts3_outputs_def,axiom,
% 0.59/0.74 ! [X,Y,Z,W] :
% 0.59/0.74 ( program_halts2_halts3_outputs(X,Y,Z,W)
% 0.59/0.74 <=> ( program_halts2(Y,Z)
% 0.59/0.74 => halts3_outputs(X,Y,Z,W) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(program_not_halts2_halts3_outputs_def,axiom,
% 0.59/0.74 ! [X,Y,Z,W] :
% 0.59/0.74 ( program_not_halts2_halts3_outputs(X,Y,Z,W)
% 0.59/0.74 <=> ( program_not_halts2(Y,Z)
% 0.59/0.74 => halts3_outputs(X,Y,Z,W) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(program_halts2_halts2_outputs_def,axiom,
% 0.59/0.74 ! [X,Y,W] :
% 0.59/0.74 ( program_halts2_halts2_outputs(X,Y,W)
% 0.59/0.74 <=> ( program_halts2(Y,Y)
% 0.59/0.74 => halts2_outputs(X,Y,W) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(program_not_halts2_halts2_outputs_def,axiom,
% 0.59/0.74 ! [X,Y,W] :
% 0.59/0.74 ( program_not_halts2_halts2_outputs(X,Y,W)
% 0.59/0.74 <=> ( program_not_halts2(Y,Y)
% 0.59/0.74 => halts2_outputs(X,Y,W) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(p1,axiom,
% 0.59/0.74 ( ? [X] : algorithm_program_decides(X)
% 0.59/0.74 => ? [W] : program_program_decides(W) ) ).
% 0.59/0.74
% 0.59/0.74 fof(p2,axiom,
% 0.59/0.74 ! [W] :
% 0.59/0.74 ( program_program_decides(W)
% 0.59/0.74 => ! [Y,Z] :
% 0.59/0.74 ( program_halts2_halts3_outputs(W,Y,Z,good)
% 0.59/0.74 & program_not_halts2_halts3_outputs(W,Y,Z,bad) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(p3,axiom,
% 0.59/0.74 ( ? [W] :
% 0.59/0.74 ( program(W)
% 0.59/0.74 & ! [Y] :
% 0.59/0.74 ( program_halts2_halts3_outputs(W,Y,Y,good)
% 0.59/0.74 & program_not_halts2_halts3_outputs(W,Y,Y,bad) ) )
% 0.59/0.74 => ? [V] :
% 0.59/0.74 ( program(V)
% 0.59/0.74 & ! [Y] :
% 0.59/0.74 ( program_halts2_halts2_outputs(V,Y,good)
% 0.59/0.74 & program_not_halts2_halts2_outputs(V,Y,bad) ) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(p4,axiom,
% 0.59/0.74 ( ? [V] :
% 0.59/0.74 ( program(V)
% 0.59/0.74 & ! [Y] :
% 0.59/0.74 ( program_halts2_halts2_outputs(V,Y,good)
% 0.59/0.74 & program_not_halts2_halts2_outputs(V,Y,bad) ) )
% 0.59/0.74 => ? [U] :
% 0.59/0.74 ( program(U)
% 0.59/0.74 & ! [Y] :
% 0.59/0.74 ( ( program_halts2(Y,Y)
% 0.59/0.74 => ~ halts2(U,Y) )
% 0.59/0.74 & program_not_halts2_halts2_outputs(U,Y,good) ) ) ) ).
% 0.59/0.74
% 0.59/0.74 fof(prove_this,conjecture,
% 0.59/0.74 ~ ? [X] : algorithm_program_decides(X) ).
% 0.59/0.74
% 0.59/0.74 %--------------------------------------------------------------------------
% 0.59/0.74 %-------------------------------------------
% 0.59/0.74 % Proof found
% 0.59/0.74 % SZS status Theorem for theBenchmark
% 0.59/0.74 % SZS output start Proof
% 0.59/0.74 %ClaNum:43(EqnAxiom:0)
% 0.59/0.74 %VarNum:225(SingletonVarNum:103)
% 0.59/0.74 %MaxLitNum:5
% 0.59/0.74 %MaxfuncDepth:1
% 0.59/0.74 %SharedTerms:10
% 0.59/0.74 %goalClause: 1
% 0.59/0.74 %singleGoalClaCount:1
% 0.59/0.74 [1]P1(a1)
% 0.59/0.74 [2]~P1(x21)+P3(a3)
% 0.59/0.74 [3]~P3(x31)+P4(x31)
% 0.59/0.74 [4]~P1(x41)+P4(x41)
% 0.59/0.74 [5]~P3(x51)+P5(x51)
% 0.59/0.74 [6]~P1(x61)+P2(x61)
% 0.59/0.74 [7]P4(x71)+P5(f4(x71))
% 0.59/0.74 [22]P4(x221)+~P7(x221,f4(x221),f5(x221))
% 0.59/0.74 [10]P5(x101)+~P12(x101,x102)
% 0.59/0.74 [11]P5(x111)+~P13(x111,x112)
% 0.59/0.74 [13]~P12(x131,x132)+P6(x131,x132)
% 0.59/0.74 [15]~P13(x151,x152)+~P6(x151,x152)
% 0.59/0.74 [17]P12(x171,x171)+P14(x172,x171,x173)
% 0.59/0.74 [18]P13(x181,x181)+P16(x182,x181,x183)
% 0.59/0.74 [20]P6(x201,x202)+~P8(x201,x202,x203)
% 0.59/0.74 [21]P9(x211,x212)+~P8(x211,x213,x212)
% 0.59/0.74 [23]~P8(x231,x232,x233)+P14(x231,x232,x233)
% 0.59/0.74 [24]~P8(x241,x242,x243)+P16(x241,x242,x243)
% 0.59/0.74 [30]~P3(x301)+P15(x301,x302,x303,a12)
% 0.59/0.74 [31]~P3(x311)+P17(x311,x312,x313,a2)
% 0.59/0.74 [32]P12(x321,x322)+P15(x323,x321,x322,x324)
% 0.59/0.74 [33]P13(x331,x332)+P17(x333,x331,x332,x334)
% 0.59/0.74 [35]P9(x351,x352)+~P10(x351,x353,x354,x352)
% 0.59/0.74 [36]P11(x361,x362,x363)+~P10(x361,x362,x363,x364)
% 0.59/0.74 [37]~P10(x371,x372,x373,x374)+P15(x371,x372,x373,x374)
% 0.59/0.74 [38]~P10(x381,x382,x383,x384)+P17(x381,x382,x383,x384)
% 0.59/0.74 [8]~P4(x81)+~P5(x81)+P3(x81)
% 0.59/0.74 [9]~P4(x91)+~P2(x91)+P1(x91)
% 0.59/0.74 [12]P13(x121,x122)+~P5(x121)+P6(x121,x122)
% 0.59/0.74 [14]~P5(x141)+~P6(x141,x142)+P12(x141,x142)
% 0.59/0.74 [16]~P4(x161)+~P5(x162)+P7(x161,x162,x163)
% 0.61/0.74 [19]~P6(x191,x192)+~P9(x191,x193)+P8(x191,x192,x193)
% 0.61/0.74 [25]~P12(x252,x252)+~P14(x251,x252,x253)+P8(x251,x252,x253)
% 0.61/0.74 [26]~P13(x262,x262)+~P16(x261,x262,x263)+P8(x261,x262,x263)
% 0.61/0.74 [34]~P9(x341,x344)+~P11(x341,x342,x343)+P10(x341,x342,x343,x344)
% 0.61/0.74 [39]~P12(x392,x393)+~P15(x391,x392,x393,x394)+P10(x391,x392,x393,x394)
% 0.61/0.74 [40]~P13(x402,x403)+~P17(x401,x402,x403,x404)+P10(x401,x402,x403,x404)
% 0.61/0.74 [27]~P5(x271)+~P14(x271,f7(x271),a12)+~P16(x271,f11(x271),a2)+P5(a6)
% 0.61/0.74 [41]~P5(x411)+~P15(x411,f9(x411),f9(x411),a12)+~P17(x411,f10(x411),f10(x411),a2)+P5(a8)
% 0.61/0.74 [29]~P5(x292)+~P14(x292,f7(x292),a12)+~P16(x292,f11(x292),a2)+P16(a6,x291,a12)
% 0.61/0.74 [42]~P5(x422)+~P15(x422,f9(x422),f9(x422),a12)+~P17(x422,f10(x422),f10(x422),a2)+P14(a8,x421,a12)
% 0.61/0.74 [43]~P5(x432)+~P15(x432,f9(x432),f9(x432),a12)+~P17(x432,f10(x432),f10(x432),a2)+P16(a8,x431,a2)
% 0.61/0.74 [28]~P5(x281)+~P12(x282,x282)+~P6(a6,x282)+~P14(x281,f7(x281),a12)+~P16(x281,f11(x281),a2)
% 0.61/0.74 %EqnAxiom
% 0.61/0.74
% 0.61/0.74 %-------------------------------------------
% 0.61/0.74 cnf(45,plain,
% 0.61/0.74 (P4(a1)),
% 0.61/0.74 inference(scs_inference,[],[1,6,4])).
% 0.61/0.74 cnf(46,plain,
% 0.61/0.74 (P3(a3)),
% 0.61/0.74 inference(scs_inference,[],[1,6,4,2])).
% 0.61/0.74 cnf(51,plain,
% 0.61/0.74 (P17(a3,x511,x512,a2)),
% 0.61/0.74 inference(scs_inference,[],[46,31])).
% 0.61/0.74 cnf(59,plain,
% 0.61/0.74 (P16(a8,x591,a2)),
% 0.61/0.74 inference(scs_inference,[],[46,31,30,5,3,43])).
% 0.61/0.74 cnf(61,plain,
% 0.61/0.74 (P14(a8,x611,a12)),
% 0.61/0.74 inference(scs_inference,[],[46,31,30,5,3,43,42])).
% 0.61/0.74 cnf(63,plain,
% 0.61/0.74 (P5(a8)),
% 0.61/0.74 inference(scs_inference,[],[46,31,30,5,3,43,42,41])).
% 0.61/0.74 cnf(69,plain,
% 0.61/0.74 (P16(a6,x691,a12)),
% 0.61/0.74 inference(scs_inference,[],[45,46,31,30,5,3,43,42,41,40,16,29])).
% 0.61/0.74 cnf(90,plain,
% 0.61/0.74 (P5(a6)),
% 0.61/0.74 inference(scs_inference,[],[59,61,63,27])).
% 0.61/0.74 cnf(98,plain,
% 0.61/0.74 (P6(a6,x981)+P13(a6,x981)),
% 0.61/0.74 inference(scs_inference,[],[90,12])).
% 0.61/0.74 cnf(110,plain,
% 0.61/0.74 (~P12(x1101,x1101)+~P6(a6,x1101)),
% 0.61/0.74 inference(scs_inference,[],[59,61,63,28])).
% 0.61/0.74 cnf(120,plain,
% 0.61/0.74 (P12(a6,x1201)+~P6(a6,x1201)),
% 0.61/0.74 inference(scs_inference,[],[90,14])).
% 0.61/0.74 cnf(152,plain,
% 0.61/0.74 (P10(a3,a6,x1521,a2)+P6(a6,x1521)),
% 0.61/0.74 inference(scs_inference,[],[51,40,98])).
% 0.61/0.74 cnf(196,plain,
% 0.61/0.74 (~P6(a6,a6)),
% 0.61/0.74 inference(scs_inference,[],[110,120])).
% 0.61/0.75 cnf(205,plain,
% 0.61/0.75 ($false),
% 0.61/0.75 inference(scs_inference,[],[196,69,152,37,98,26,20]),
% 0.61/0.75 ['proof']).
% 0.61/0.75 % SZS output end Proof
% 0.61/0.75 % Total time :0.080000s
%------------------------------------------------------------------------------