Journal of Formalized Mathematics
Volume 8, 1996
University of Bialystok
Copyright (c) 1996 Association of Mizar Users

The abstract of the Mizar article:

Constant Assignment Macro Instructions of \SCMFSA. Part II

by
Noriko Asamoto

Received August 27, 1996

MML identifier: SCMFSA7B
[ Mizar article, MML identifier index ]


environ

 vocabulary AMI_3, AMI_1, SCMFSA_2, FINSEQ_1, RELAT_1, SCMFSA_7, ARYTM_1,
      FUNCT_1, CAT_1, SCMFSA6A, CARD_1, FUNCT_4, INT_1, FINSEQ_2, AMI_2,
      SCMFSA6B, SF_MASTR, BOOLE, DTCONSTR, ABSVALUE, AMI_5, UNIALG_2, SCMFSA_4,
      FUNCOP_1, SCMFSA7B, FINSEQ_4;
 notation TARSKI, XBOOLE_0, ENUMSET1, XCMPLX_0, XREAL_0, REAL_1, NAT_1, INT_1,
      RELAT_1, FUNCT_1, FUNCT_4, FUNCT_7, FINSEQ_1, FINSEQ_2, FINSEQ_4,
      BINARITH, FINSOP_1, FUNCOP_1, DTCONSTR, CARD_1, CQC_LANG, AMI_1, AMI_3,
      AMI_5, SCMFSA_2, SCMFSA_4, SCMFSA_7, SCMFSA6A, SF_MASTR, SCMFSA6B,
      GROUP_1;
 constructors REAL_1, FINSOP_1, ENUMSET1, BINARITH, AMI_5, SCMFSA_7, SCMFSA6A,
      SF_MASTR, SCMFSA6B, FINSEQ_4, MEMBERED;
 clusters RELSET_1, FINSEQ_1, INT_1, FUNCT_1, AMI_1, SCMFSA_2, SCMFSA_4,
      SCMFSA_7, SF_MASTR, SCMFSA6B, FUNCOP_1, CQC_LANG, NAT_1, FRAENKEL,
      XREAL_0, MEMBERED;
 requirements REAL, NUMERALS, BOOLE, SUBSET, ARITHM;


begin

reserve m for Nat;

theorem :: SCMFSA7B:1  ::TG4
 for p being FinSequence of the Instructions of SCM+FSA holds
     dom Load p = {insloc m: m < len p};

theorem :: SCMFSA7B:2  ::T83(@AAAA)
 for p being FinSequence of the Instructions of SCM+FSA holds
     rng Load p = rng p;

definition
 let p be FinSequence of the Instructions of SCM+FSA;
 cluster Load p -> initial programmed;
end;

theorem :: SCMFSA7B:3  ::TQ50
   for i being Instruction of SCM+FSA holds
     Load <* i *> = insloc 0 .--> i;

theorem :: SCMFSA7B:4
 for i being Instruction of SCM+FSA holds
 dom Macro i = { insloc 0, insloc 1 };

theorem :: SCMFSA7B:5  ::TQ56
 for i being Instruction of SCM+FSA holds
     Macro i = Load <* i,halt SCM+FSA *>;

theorem :: SCMFSA7B:6  ::T54(@BBB8)
 for i being Instruction of SCM+FSA holds
     card Macro i = 2;

theorem :: SCMFSA7B:7  ::T25(@BBB8)
   for i being Instruction of SCM+FSA holds
     (i = halt SCM+FSA implies (Directed Macro i).insloc 0 = goto insloc 2) &
     (i <> halt SCM+FSA implies (Directed Macro i).insloc 0 = i);

theorem :: SCMFSA7B:8  ::T26(@BBB8)
   for i being Instruction of SCM+FSA holds
     (Directed Macro i).insloc 1 = goto insloc 2;

definition
 let a be Int-Location, k be Integer;
 cluster a := k -> initial programmed;
end;

definition
 let a be Int-Location, k be Integer;
 cluster a := k -> parahalting;
end;

theorem :: SCMFSA7B:9 ::*
   for s being State of SCM+FSA
 for a being read-write Int-Location, k being Integer holds
     IExec(a := k,s).a = k &
     (for b being read-write Int-Location st b <> a holds
         IExec(a := k,s).b = s.b) &
     (for f being FinSeq-Location holds IExec(a := k,s).f = s.f);

definition
 let f be FinSeq-Location, p be FinSequence of INT;
 cluster f := p -> initial programmed;
end;

definition
 let f be FinSeq-Location, p be FinSequence of INT;
 cluster f := p -> parahalting;
end;

theorem :: SCMFSA7B:10 ::*TG1
   for s being State of SCM+FSA, f being FinSeq-Location,
 p being FinSequence of INT holds
     IExec(f := p,s).f = p &
     (for a being read-write Int-Location st a <> intloc 1 & a <> intloc 2
         holds IExec(f := p,s).a = s.a) &
     for g being FinSeq-Location st g <> f holds IExec(f := p,s).g = s.g;

definition
 let i be Instruction of SCM+FSA;
 let a be Int-Location;
 pred i does_not_refer a means
:: SCMFSA7B:def 1
 ::D20'
   for b being Int-Location
 for l being Instruction-Location of SCM+FSA
 for f being FinSeq-Location holds
     b := a <> i &
     AddTo(b,a) <> i &
     SubFrom(b,a) <> i &
     MultBy(b,a) <> i &
     Divide(b,a) <> i &
     Divide(a,b) <> i &
     a =0_goto l <> i &
     a >0_goto l <> i &
     b :=(f,a) <> i &
     (f,b):= a <> i &
     (f,a):= b <> i &
     f :=<0,...,0> a <> i;
end;

definition
 let I be programmed FinPartState of SCM+FSA;
 let a be Int-Location;
 pred I does_not_refer a means
:: SCMFSA7B:def 2
 ::D20
   for i being Instruction of SCM+FSA
 st i in rng I holds i does_not_refer a;
end;

definition
 let i be Instruction of SCM+FSA;
 let a be Int-Location;
 pred i does_not_destroy a means
:: SCMFSA7B:def 3
 ::D19'
 for b being Int-Location
 for f being FinSeq-Location holds
     a := b <> i &
     AddTo(a,b) <> i &
     SubFrom(a,b) <> i &
     MultBy(a,b) <> i &
     Divide(a,b) <> i &
     Divide(b,a) <> i &
     a :=(f,b) <> i &
     a :=len f <> i;
end;

definition
 let I be FinPartState of SCM+FSA;
 let a be Int-Location;
 pred I does_not_destroy a means
:: SCMFSA7B:def 4
 ::D19
 for i being Instruction of SCM+FSA
 st i in rng I holds i does_not_destroy a;
end;

definition let I be FinPartState of SCM+FSA;
 attr I is good means
:: SCMFSA7B:def 5
 ::Dg
 I does_not_destroy intloc 0;
end;

definition let I be FinPartState of SCM+FSA;
 attr I is halt-free means
:: SCMFSA7B:def 6
 ::D8
 not halt SCM+FSA in rng I;
end;

definition
 cluster halt-free good Macro-Instruction;
end;

theorem :: SCMFSA7B:11  ::R0''
 for a being Int-Location holds
     halt SCM+FSA does_not_destroy a;

theorem :: SCMFSA7B:12  ::R1''
 for a,b,c being Int-Location holds
     a <> b implies b := c does_not_destroy a;

theorem :: SCMFSA7B:13  ::R2''
 for a,b,c being Int-Location holds
     a <> b implies AddTo(b,c) does_not_destroy a;

theorem :: SCMFSA7B:14  ::R3''
 for a,b,c being Int-Location holds
     a <> b implies SubFrom(b,c) does_not_destroy a;

theorem :: SCMFSA7B:15  ::R4''
   for a,b,c being Int-Location holds
     a <> b implies MultBy(b,c) does_not_destroy a;

theorem :: SCMFSA7B:16  ::R5''
   for a,b,c being Int-Location holds
     a <> b & a <> c implies Divide(b,c) does_not_destroy a;

theorem :: SCMFSA7B:17  ::R6''
   for a being Int-Location, l being Instruction-Location of SCM+FSA holds
     goto l does_not_destroy a;

theorem :: SCMFSA7B:18  ::R7''
   for a,b being Int-Location, l being Instruction-Location of SCM+FSA holds
     b =0_goto l does_not_destroy a;

theorem :: SCMFSA7B:19  ::R8''
   for a,b being Int-Location, l being Instruction-Location of SCM+FSA holds
     b >0_goto l does_not_destroy a;

theorem :: SCMFSA7B:20  ::R9''
   for a,b,c being Int-Location, f being FinSeq-Location holds
     a <> b implies b := (f,c) does_not_destroy a;

theorem :: SCMFSA7B:21  ::R10''
   for a,b,c being Int-Location, f being FinSeq-Location holds
     (f,c):= b does_not_destroy a;

theorem :: SCMFSA7B:22  ::R11''
   for a,b being Int-Location, f being FinSeq-Location holds
     a <> b implies b :=len f does_not_destroy a;

theorem :: SCMFSA7B:23  ::R12''
   for a,b being Int-Location, f being FinSeq-Location holds
     f :=<0,...,0> b does_not_destroy a;

definition
 let I be FinPartState of SCM+FSA;
 let s be State of SCM+FSA;
 pred I is_closed_on s means
:: SCMFSA7B:def 7
 ::D18
 for k being Nat holds
     IC (Computation (s +* (I +* Start-At insloc 0))).k in dom I;
 pred I is_halting_on s means
:: SCMFSA7B:def 8
 ::D18'
 s +* (I +* Start-At insloc 0) is halting;
end;

theorem :: SCMFSA7B:24  ::TQ6
 for I being Macro-Instruction holds
     I is paraclosed iff for s being State of SCM+FSA holds I is_closed_on s;

theorem :: SCMFSA7B:25 ::*TQ6'
   for I being Macro-Instruction holds
     I is parahalting iff for s being State of SCM+FSA holds I is_halting_on s;

theorem :: SCMFSA7B:26  ::TA10
 for i being Instruction of SCM+FSA, a being Int-Location,
 s being State of SCM+FSA holds
     i does_not_destroy a implies Exec(i,s).a = s.a;

theorem :: SCMFSA7B:27  ::TQ9''
 for s being State of SCM+FSA, I being Macro-Instruction, a being Int-Location
 st I does_not_destroy a & I is_closed_on s holds
     for k being Nat holds
         (Computation (s +* (I +* Start-At insloc 0))).k.a = s.a;

theorem :: SCMFSA7B:28  ::TQ7
 SCM+FSA-Stop does_not_destroy intloc 0;

definition
 cluster parahalting good Macro-Instruction;
end;

definition
 cluster SCM+FSA-Stop -> parahalting good;
end;

definition
 cluster paraclosed good -> keeping_0 Macro-Instruction;
end;

theorem :: SCMFSA7B:29  ::TS3
 for a being Int-Location, k being Integer holds
     rng aSeq(a,k) c=
         {a := intloc 0,AddTo(a,intloc 0),SubFrom(a,intloc 0)};

theorem :: SCMFSA7B:30  ::TS1
 for a being Int-Location, k being Integer holds
     rng (a := k) c=
         {halt SCM+FSA,a := intloc 0,AddTo(a,intloc 0),SubFrom(a,intloc 0)};

definition
 let a be read-write Int-Location, k be Integer;
 cluster a := k -> good;
end;

definition
 let a be read-write Int-Location, k be Integer;
 cluster a := k -> keeping_0;
end;

Back to top