let p be the Instructions of SCM+FSA -valued ManySortedSet of NAT ; :: 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 SCMFSA6B:8;
then A11: Start-At (0,SCM+FSA) c= s ;
A12: s = s +* (Start-At (0,SCM+FSA)) by A11, FUNCT_4:104
.= Initialize s ;
then A13: p +* I halts_on s by A2, SCMFSA7B:def 8;
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:55;
then Directed I c= p by A14, XBOOLE_1:1;
then A15: p +* (Directed I) = p by FUNCT_4:103, FUNCT_4:104;
Start-At (0,SCM+FSA) c= s by A10, SCMFSA6B:8;
then Start-At (0,SCM+FSA) c= s ;
then s = Initialize s by FUNCT_4:103, FUNCT_4:104;
hence A17: IC (Comput (p,s,((LifeSpan ((p +* I),s)) + 1))) = card I by A2, A4, A15, SCMFSA8A:36; :: 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:26;
reconsider kk = DataPart (Start-At (0,SCM+FSA)) as Function ;
A19: DataPart (Start-At (0,SCM+FSA)) = {} by Th2;
(Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) . (intloc 0) = s . (intloc 0) by A4, A12, SCMFSA8C:97;
then A20: Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) = Initialize (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by A1, SCMFSA8C:18;
then DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) = (DataPart (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) +* kk by FUNCT_4:75;
then DataPart (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) = DataPart (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) by A19, FUNCT_4:104, 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:36; :: 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:26;
A23: intloc 0 in dom (Initialize ((intloc 0) .--> 1)) by SCMFSA6A:86;
A24: s = s +* (Initialize ((intloc 0) .--> 1)) by A10, FUNCT_4:104;
A25: DataPart (IExec (I,p,s)) = DataPart ((Result ((p +* I),(s +* (Initialize ((intloc 0) .--> 1))))) +* (s | NAT)) by SCMFSA6B:def 1
.= DataPart (Result ((p +* I),(s +* (Initialize ((intloc 0) .--> 1))))) by COMPOS_1:82
.= 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:8;
then A26: (p +* I) +* J halts_on Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by A20, SCMFSA7B:def 8;
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 SCM+FSA by SCMFSA_2:127, 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:72
.= (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) . (intloc 0) by A28, FUNCT_1:72
.= 1 by LmY, A23, FUNCT_4:14 ;
:: 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, SCMFSA8A:10;
then A34: J is_closed_on Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))),(p +* I) +* J by A5, SCMFSA8B:6;
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:5;
A36: Start-At (0,SCM+FSA) c= Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by FUNCT_4:26, SCMFSA6B:8;
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,(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:42;
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 14
.= halt SCM+FSA by COMPOS_1:93 ;
hence A38: p halts_on s by EXTPRO_1:30; :: 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:8;
A41: Comput (p,s,(((LifeSpan ((p +* I),s)) + 1) + k)) = Comput (p,(Comput (p,s,((LifeSpan ((p +* I),s)) + 1))),k) by EXTPRO_1:5;
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, A36, A27, A18, SCMFSA8C:42;
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 38, SCMFSA_2:124;
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:122;
hence contradiction by A26, A40, EXTPRO_1:def 14; :: 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 13;
((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 14;
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:26, SCMFSA6B:8;
then A46: Initialize (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) = Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by FUNCT_4:103, FUNCT_4:104;
A47: Initialize ((intloc 0) .--> 1) c= Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s)))) by FUNCT_4:26;
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, A36, A27, A18, SCMFSA8C:42;
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:5
.= (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:38
.= (Initialized (Comput ((p +* I),s,(LifeSpan ((p +* I),s))))) . (intloc 0) by A5, A33, A46, A49, SCMFSA8B:6, SCMFSA8C:97
.= 1 by LmY, A23, A47, GRFUNC_1:8 ; :: thesis: verum
end;