let p be Instruction-Sequence of SCM+FSA; :: thesis: for I being good Program of SCM+FSA
for J being Program of SCM+FSA
for s being State of SCM+FSA st s . (intloc 0) = 1 & I is_halting_on s,p & J is_halting_on IExec (I,p,s),p & I is_closed_on s,p & J is_closed_on IExec (I,p,s),p & Initialize ((intloc 0) .--> 1) c= s & I ';' J c= p holds
( IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I & DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) & Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
let I be good Program of SCM+FSA; :: thesis: for J being Program of SCM+FSA
for s being State of SCM+FSA st s . (intloc 0) = 1 & I is_halting_on s,p & J is_halting_on IExec (I,p,s),p & I is_closed_on s,p & J is_closed_on IExec (I,p,s),p & Initialize ((intloc 0) .--> 1) c= s & I ';' J c= p holds
( IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I & DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) & Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
let J be Program of SCM+FSA; :: thesis: for s being State of SCM+FSA st s . (intloc 0) = 1 & I is_halting_on s,p & J is_halting_on IExec (I,p,s),p & I is_closed_on s,p & J is_closed_on IExec (I,p,s),p & Initialize ((intloc 0) .--> 1) c= s & I ';' J c= p holds
( IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I & DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) & Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
let s be State of SCM+FSA; :: thesis: ( s . (intloc 0) = 1 & I is_halting_on s,p & J is_halting_on IExec (I,p,s),p & I is_closed_on s,p & J is_closed_on IExec (I,p,s),p & Initialize ((intloc 0) .--> 1) c= s & I ';' J c= p implies ( IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I & DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) & Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) ) )
assume that
A1: s . (intloc 0) = 1 and
A2: I is_halting_on s,p and
A3: J is_halting_on IExec (I,p,s),p and
A4: I is_closed_on s,p and
A5: J is_closed_on IExec (I,p,s),p ; :: thesis: ( not Initialize ((intloc 0) .--> 1) c= s or not I ';' J c= p or ( IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I & DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) & Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) ) )
set s1 = s;
set p1 = p +* I;
set m1 = LifeSpan ((p +* I),s);
set s4 = Comput (p,s,((LifeSpan ((p +* I),s)) + 1));
set p4 = p;
assume A10: Initialize ((intloc 0) .--> 1) c= s ; :: thesis: ( not I ';' J c= p or ( IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I & DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) & Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) ) )
then Start-At (0,SCM+FSA) c= s by MEMSTR_0:50;
then A11: Start-At (0,SCM+FSA) c= s ;
A12: s = s +* (Start-At (0,SCM+FSA)) by A11, FUNCT_4:98
.= Initialize s ;
then A13: p +* I halts_on s by A2, SCMFSA7B:def 7;
assume A14: I ';' J c= p ; :: thesis: ( IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I & DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) & Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
Directed I c= I ';' J by SCMFSA6A:16;
then Directed I c= p by A14, XBOOLE_1:1;
then A15: p +* (Directed I) = p by FUNCT_4:98;
Start-At (0,SCM+FSA) c= s by A10, MEMSTR_0:50;
then Start-At (0,SCM+FSA) c= s ;
then s = Initialize s by FUNCT_4:98;
hence A17: IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I by A2, A4, A15, SCMFSA8A:22; :: thesis: ( DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) & Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
set JAt = Start-At (0,SCM+FSA);
set InJ = Initialize ((intloc 0) .--> 1);
set s3 = Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))));
set p3 = (p +* I) +* J;
A18: J c= (p +* I) +* J by FUNCT_4:25;
reconsider kk = DataPart (Start-At (0,SCM+FSA)) as Function ;
A19: DataPart (Start-At (0,SCM+FSA)) = {} by MEMSTR_0:20;
(Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) . (intloc 0) = s . (intloc 0) by A4, A12, SCMFSA8C:68;
then A20: Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) = Initialize (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by A1, SCMFSA8C:4;
then DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) = (DataPart (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) +* kk by FUNCT_4:71;
then DataPart (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) by A19, FUNCT_4:98, XBOOLE_1:2;
hence A21: DataPart (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) by A2, A4, A12, A15, SCMFSA8A:22; :: thesis: ( Reloc (J,(card I)) c= p & (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
A22: Reloc (J,(card I)) c= I ';' J by FUNCT_4:25;
A23: intloc 0 in dom (Initialize ((intloc 0) .--> 1)) by SCMFSA6A:41;
A24: s = s +* (Initialize ((intloc 0) .--> 1)) by A10, FUNCT_4:98;
A25: DataPart (IExec (I,p,s)) = DataPart (Result ((p +* I),(Initialized s))) by SCMFSA6B:def 1
.= DataPart (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by A13, A24, EXTPRO_1:23 ;
then J is_halting_on Comput ((p +* I),s,(LifeSpan ((p +* I),s))),p +* I by A3, A5, SCMFSA8B:5;
then A26: (p +* I) +* J halts_on Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by A20, SCMFSA7B:def 7;
I ';' J c= p by A14;
then Reloc (J,(card I)) c= p by A22, XBOOLE_1:1;
then Reloc (J,(card I)) c= p ;
hence Reloc (J,(card I)) c= p ; :: thesis: ( (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = 1 & p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
A27: Reloc (J,(card I)) c= p by A14, A22, XBOOLE_1:1;
intloc 0 in Int-Locations by SCMFSA_2:def 4;
then A28: intloc 0 in Data-Locations by SCMFSA_2:100, XBOOLE_0:def 3;
hence (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) . (intloc 0) = (DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))))) . (intloc 0) by A21, FUNCT_1:49
.= (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) . (intloc 0) by A28, FUNCT_1:49
.= 1 by SCMFSA6A:43, A23, FUNCT_4:13 ;
:: thesis: ( p halts_on s & LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
set m3 = LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))));
reconsider m = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))) as Element of NAT ;
A33: DataPart (IExec (I,p,s)) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) by A20, A25, MEMSTR_0:79;
then A34: J is_closed_on Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))),(p +* I) +* J by A5, SCMFSA8B:3;
A35: Comput (p,s,(((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))))) = Comput (p,(Comput (p,s,((LifeSpan ((p +* I),s)) + 1))),(LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))))))) by EXTPRO_1:4;
IncAddr ((CurInstr (((p +* I) +* J),(Comput (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))),(LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))))))),(card I)) = CurInstr (p,(Comput (p,(Comput (p,s,((LifeSpan ((p +* I),s)) + 1))),(LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))))))))) by A34, A17, A21, A27, A18, SCMFSA8C:16;
then IncAddr ((CurInstr (((p +* I) +* J),(Comput (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))),(LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))))))),(card I)) = CurInstr (p,(Comput (p,s,(((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))))))) by A35;
then A37: CurInstr (p,(Comput (p,s,m))) = IncAddr ((halt SCM+FSA),(card I)) by A26, EXTPRO_1:def 15
.= halt SCM+FSA by COMPOS_1:11 ;
hence A38: p halts_on s by EXTPRO_1:29; :: thesis: ( LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) & ( J is good implies (Result (p,s)) . (intloc 0) = 1 ) )
A39: now
let k be Element of NAT ; :: thesis: ( ((LifeSpan ((p +* I),s)) + 1) + k < m implies not CurInstr (p,(Comput (p,s,(((LifeSpan ((p +* I),s)) + 1) + k)))) = halt SCM+FSA )
assume ((LifeSpan ((p +* I),s)) + 1) + k < m ; :: thesis: not CurInstr (p,(Comput (p,s,(((LifeSpan ((p +* I),s)) + 1) + k)))) = halt SCM+FSA
then A40: k < LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))))) by XREAL_1:6;
A41: Comput (p,s,(((LifeSpan ((p +* I),s)) + 1) + k)) = Comput (p,(Comput (p,s,((LifeSpan ((p +* I),s)) + 1))),k) by EXTPRO_1:4;
assume A42: CurInstr (p,(Comput (p,s,(((LifeSpan ((p +* I),s)) + 1) + k)))) = halt SCM+FSA ; :: thesis: contradiction
IncAddr ((CurInstr (((p +* I) +* J),(Comput (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))),k)))),(card I)) = halt SCM+FSA by A42, A41, A34, A17, A21, A27, A18, SCMFSA8C:16;
then InsCode (CurInstr (((p +* I) +* J),(Comput (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))),k)))) = 0 by COMPOS_1:def 17, SCMFSA_2:97;
then CurInstr (((p +* I) +* J),(Comput (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))),k))) = halt SCM+FSA by SCMFSA_2:95;
hence contradiction by A26, A40, EXTPRO_1:def 15; :: thesis: verum
end;
now
let k be Element of NAT ; :: thesis: ( k < m implies CurInstr (p,(Comput (p,s,b1))) <> halt SCM+FSA )
assume A43: k < m ; :: thesis: CurInstr (p,(Comput (p,s,b1))) <> halt SCM+FSA
per cases ( k <= LifeSpan ((p +* I),s) or LifeSpan ((p +* I),s) < k ) ;
suppose LifeSpan ((p +* I),s) < k ; :: thesis: CurInstr (p,(Comput (p,s,b1))) <> halt SCM+FSA
then (LifeSpan ((p +* I),s)) + 1 <= k by NAT_1:13;
then consider kk being Nat such that
A44: ((LifeSpan ((p +* I),s)) + 1) + kk = k by NAT_1:10;
reconsider kk = kk as Element of NAT by ORDINAL1:def 12;
((LifeSpan ((p +* I),s)) + 1) + kk = k by A44;
hence CurInstr (p,(Comput (p,s,k))) <> halt SCM+FSA by A39, A43; :: thesis: verum
end;
end;
end;
then for k being Element of NAT st CurInstr (p,(Comput (p,s,k))) = halt SCM+FSA holds
m <= k ;
then A45: LifeSpan (p,s) = m by A37, A38, EXTPRO_1:def 15;
Comput ((p +* I),s,(LifeSpan ((p +* I),s))) = Result ((p +* I),s) by A13, EXTPRO_1:23;
hence LifeSpan (p,s) = ((LifeSpan ((p +* I),s)) + 1) + (LifeSpan (((p +* I) +* J),(Initialized (Result ((p +* I),s))))) by A45; :: thesis: ( J is good implies (Result (p,s)) . (intloc 0) = 1 )
Start-At (0,SCM+FSA) c= Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by FUNCT_4:25, MEMSTR_0:50;
then A46: Initialize (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) = Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by FUNCT_4:98;
A47: Initialize ((intloc 0) .--> 1) c= Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by FUNCT_4:25;
hereby :: thesis: verum
A48: DataPart (Comput (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))),(LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))))) = DataPart (Comput (p,(Comput (p,s,((LifeSpan ((p +* I),s)) + 1))),(LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))))) by A34, A17, A21, A27, A18, SCMFSA8C:16;
assume A49: J is good ; :: thesis: (Result (p,s)) . (intloc 0) = 1
thus (Result (p,s)) . (intloc 0) = (Comput (p,s,m)) . (intloc 0) by A38, A45, EXTPRO_1:23
.= (Comput (p,(Comput (p,s,((LifeSpan ((p +* I),s)) + 1))),(LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))))) . (intloc 0) by EXTPRO_1:4
.= (Comput (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))),(LifeSpan (((p +* I) +* J),(Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))))))) . (intloc 0) by A48, SCMFSA6A:7
.= (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) . (intloc 0) by A5, A33, A46, A49, SCMFSA8B:3, SCMFSA8C:68
.= 1 by SCMFSA6A:43, A23, A47, GRFUNC_1:2 ; :: thesis: verum
end;