:: SCMFSA9A semantic presentation :: Showing IDV graph ... (Click the Palm Trees again to close it)
theorem Th1: :: SCMFSA9A:1 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem :: SCMFSA9A:2 :: Showing IDV graph ... (Click the Palm Tree again to close it)
canceled;
theorem :: SCMFSA9A:3 :: Showing IDV graph ... (Click the Palm Tree again to close it)
canceled;
theorem Th4: :: SCMFSA9A:4 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem :: SCMFSA9A:5 :: Showing IDV graph ... (Click the Palm Tree again to close it)
canceled;
theorem Th6: :: SCMFSA9A:6 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th7: :: SCMFSA9A:7 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th8: :: SCMFSA9A:8 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th9: :: SCMFSA9A:9 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th10: :: SCMFSA9A:10 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th11: :: SCMFSA9A:11 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th12: :: SCMFSA9A:12 :: Showing IDV graph ... (Click the Palm Tree again to close it)
set D = Int-Locations \/ FinSeq-Locations ;
set SAt = Start-At (insloc 0);
set IL = the Instruction-Locations of SCM+FSA ;
theorem Th13: :: SCMFSA9A:13 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th14: :: SCMFSA9A:14 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th15: :: SCMFSA9A:15 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th16: :: SCMFSA9A:16 :: Showing IDV graph ... (Click the Palm Tree again to close it)
Lm1:
for a being Int-Location
for I being Macro-Instruction holds
( insloc ((card I) + 4) in dom (if=0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) & (if=0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) . (insloc ((card I) + 4)) = goto ((insloc 0) + ((card I) + 4)) )
Lm2:
for a being Int-Location
for I being Macro-Instruction holds UsedIntLoc (if=0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) = UsedIntLoc ((if=0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) +* ((insloc ((card I) + 4)) .--> (goto (insloc 0))))
Lm3:
for a being Int-Location
for I being Macro-Instruction holds UsedInt*Loc (if=0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) = UsedInt*Loc ((if=0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) +* ((insloc ((card I) + 4)) .--> (goto (insloc 0))))
theorem :: SCMFSA9A:17 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem :: SCMFSA9A:18 :: Showing IDV graph ... (Click the Palm Tree again to close it)
definition
let s be
State of
SCM+FSA ;
let a be
read-write Int-Location ;
let I be
Macro-Instruction;
pred ProperBodyWhile=0 a,
I,
s means :
Def1:
:: SCMFSA9A:def 1
for
k being
Nat st
((StepWhile=0 a,I,s) . k) . a = 0 holds
(
I is_closed_on (StepWhile=0 a,I,s) . k &
I is_halting_on (StepWhile=0 a,I,s) . k );
pred WithVariantWhile=0 a,
I,
s means :
Def2:
:: SCMFSA9A:def 2
ex
f being
Function of
product the
Object-Kind of
SCM+FSA ,
NAT st
for
k being
Nat holds
(
f . ((StepWhile=0 a,I,s) . (k + 1)) < f . ((StepWhile=0 a,I,s) . k) or
((StepWhile=0 a,I,s) . k) . a <> 0 );
end;
:: deftheorem Def1 defines ProperBodyWhile=0 SCMFSA9A:def 1 :
:: deftheorem Def2 defines WithVariantWhile=0 SCMFSA9A:def 2 :
theorem Th19: :: SCMFSA9A:19 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th20: :: SCMFSA9A:20 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th21: :: SCMFSA9A:21 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th22: :: SCMFSA9A:22 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th23: :: SCMFSA9A:23 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th24: :: SCMFSA9A:24 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th25: :: SCMFSA9A:25 :: Showing IDV graph ... (Click the Palm Tree again to close it)
for
s being
State of
SCM+FSA for
a being
read-write Int-Location for
I being
Macro-Instruction for
k being
Nat st ( (
I is_halting_on Initialize ((StepWhile=0 a,I,s) . k) &
I is_closed_on Initialize ((StepWhile=0 a,I,s) . k) ) or
I is
parahalting ) &
((StepWhile=0 a,I,s) . k) . a = 0 &
((StepWhile=0 a,I,s) . k) . (intloc 0) = 1 holds
((StepWhile=0 a,I,s) . (k + 1)) | (Int-Locations \/ FinSeq-Locations ) = (IExec I,((StepWhile=0 a,I,s) . k)) | (Int-Locations \/ FinSeq-Locations )
theorem :: SCMFSA9A:26 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem :: SCMFSA9A:27 :: Showing IDV graph ... (Click the Palm Tree again to close it)
definition
let s be
State of
SCM+FSA ;
let a be
read-write Int-Location ;
let I be
Macro-Instruction;
assume that A1:
(
ProperBodyWhile=0 a,
I,
s or
I is
parahalting )
and A2:
WithVariantWhile=0 a,
I,
s
;
func ExitsAtWhile=0 a,
I,
s -> Nat means :
Def3:
:: SCMFSA9A:def 3
ex
k being
Nat st
(
it = k &
((StepWhile=0 a,I,s) . k) . a <> 0 & ( for
i being
Nat st
((StepWhile=0 a,I,s) . i) . a <> 0 holds
k <= i ) &
((Computation (s +* ((while=0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while=0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile=0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) );
existence
ex b1, k being Nat st
( b1 = k & ((StepWhile=0 a,I,s) . k) . a <> 0 & ( for i being Nat st ((StepWhile=0 a,I,s) . i) . a <> 0 holds
k <= i ) & ((Computation (s +* ((while=0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while=0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile=0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) )
uniqueness
for b1, b2 being Nat st ex k being Nat st
( b1 = k & ((StepWhile=0 a,I,s) . k) . a <> 0 & ( for i being Nat st ((StepWhile=0 a,I,s) . i) . a <> 0 holds
k <= i ) & ((Computation (s +* ((while=0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while=0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile=0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) ) & ex k being Nat st
( b2 = k & ((StepWhile=0 a,I,s) . k) . a <> 0 & ( for i being Nat st ((StepWhile=0 a,I,s) . i) . a <> 0 holds
k <= i ) & ((Computation (s +* ((while=0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while=0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile=0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) ) holds
b1 = b2
end;
:: deftheorem Def3 defines ExitsAtWhile=0 SCMFSA9A:def 3 :
for
s being
State of
SCM+FSA for
a being
read-write Int-Location for
I being
Macro-Instruction st (
ProperBodyWhile=0 a,
I,
s or
I is
parahalting ) &
WithVariantWhile=0 a,
I,
s holds
for
b4 being
Nat holds
(
b4 = ExitsAtWhile=0 a,
I,
s iff ex
k being
Nat st
(
b4 = k &
((StepWhile=0 a,I,s) . k) . a <> 0 & ( for
i being
Nat st
((StepWhile=0 a,I,s) . i) . a <> 0 holds
k <= i ) &
((Computation (s +* ((while=0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while=0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile=0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) ) );
theorem :: SCMFSA9A:28 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem :: SCMFSA9A:29 :: Showing IDV graph ... (Click the Palm Tree again to close it)
for
s being
State of
SCM+FSA for
a being
read-write Int-Location for
I being
Macro-Instruction st (
ProperBodyWhile=0 a,
I,
Initialize s or
I is
parahalting ) &
WithVariantWhile=0 a,
I,
Initialize s holds
(IExec (while=0 a,I),s) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile=0 a,I,(Initialize s)) . (ExitsAtWhile=0 a,I,(Initialize s))) | (Int-Locations \/ FinSeq-Locations )
Lm4:
for a being Int-Location
for I being Macro-Instruction holds
( insloc ((card I) + 4) in dom (if>0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) & (if>0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) . (insloc ((card I) + 4)) = goto ((insloc 0) + ((card I) + 4)) )
Lm5:
for a being Int-Location
for I being Macro-Instruction holds UsedIntLoc (if>0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) = UsedIntLoc ((if>0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) +* ((insloc ((card I) + 4)) .--> (goto (insloc 0))))
Lm6:
for a being Int-Location
for I being Macro-Instruction holds UsedInt*Loc (if>0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) = UsedInt*Loc ((if>0 a,(I ';' (Goto (insloc 0))),SCM+FSA-Stop ) +* ((insloc ((card I) + 4)) .--> (goto (insloc 0))))
theorem :: SCMFSA9A:30 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem :: SCMFSA9A:31 :: Showing IDV graph ... (Click the Palm Tree again to close it)
definition
let s be
State of
SCM+FSA ;
let a be
read-write Int-Location ;
let I be
Macro-Instruction;
pred ProperBodyWhile>0 a,
I,
s means :
Def4:
:: SCMFSA9A:def 4
for
k being
Nat st
((StepWhile>0 a,I,s) . k) . a > 0 holds
(
I is_closed_on (StepWhile>0 a,I,s) . k &
I is_halting_on (StepWhile>0 a,I,s) . k );
pred WithVariantWhile>0 a,
I,
s means :
Def5:
:: SCMFSA9A:def 5
ex
f being
Function of
product the
Object-Kind of
SCM+FSA ,
NAT st
for
k being
Nat holds
(
f . ((StepWhile>0 a,I,s) . (k + 1)) < f . ((StepWhile>0 a,I,s) . k) or
((StepWhile>0 a,I,s) . k) . a <= 0 );
end;
:: deftheorem Def4 defines ProperBodyWhile>0 SCMFSA9A:def 4 :
:: deftheorem Def5 defines WithVariantWhile>0 SCMFSA9A:def 5 :
theorem Th32: :: SCMFSA9A:32 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th33: :: SCMFSA9A:33 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th34: :: SCMFSA9A:34 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th35: :: SCMFSA9A:35 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th36: :: SCMFSA9A:36 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th37: :: SCMFSA9A:37 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th38: :: SCMFSA9A:38 :: Showing IDV graph ... (Click the Palm Tree again to close it)
for
s being
State of
SCM+FSA for
a being
read-write Int-Location for
I being
Macro-Instruction for
k being
Nat st ( (
I is_halting_on Initialize ((StepWhile>0 a,I,s) . k) &
I is_closed_on Initialize ((StepWhile>0 a,I,s) . k) ) or
I is
parahalting ) &
((StepWhile>0 a,I,s) . k) . a > 0 &
((StepWhile>0 a,I,s) . k) . (intloc 0) = 1 holds
((StepWhile>0 a,I,s) . (k + 1)) | (Int-Locations \/ FinSeq-Locations ) = (IExec I,((StepWhile>0 a,I,s) . k)) | (Int-Locations \/ FinSeq-Locations )
theorem Th39: :: SCMFSA9A:39 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th40: :: SCMFSA9A:40 :: Showing IDV graph ... (Click the Palm Tree again to close it)
definition
let s be
State of
SCM+FSA ;
let a be
read-write Int-Location ;
let I be
Macro-Instruction;
assume that A1:
(
ProperBodyWhile>0 a,
I,
s or
I is
parahalting )
and A2:
WithVariantWhile>0 a,
I,
s
;
func ExitsAtWhile>0 a,
I,
s -> Nat means :
Def6:
:: SCMFSA9A:def 6
ex
k being
Nat st
(
it = k &
((StepWhile>0 a,I,s) . k) . a <= 0 & ( for
i being
Nat st
((StepWhile>0 a,I,s) . i) . a <= 0 holds
k <= i ) &
((Computation (s +* ((while>0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while>0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile>0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) );
existence
ex b1, k being Nat st
( b1 = k & ((StepWhile>0 a,I,s) . k) . a <= 0 & ( for i being Nat st ((StepWhile>0 a,I,s) . i) . a <= 0 holds
k <= i ) & ((Computation (s +* ((while>0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while>0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile>0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) )
uniqueness
for b1, b2 being Nat st ex k being Nat st
( b1 = k & ((StepWhile>0 a,I,s) . k) . a <= 0 & ( for i being Nat st ((StepWhile>0 a,I,s) . i) . a <= 0 holds
k <= i ) & ((Computation (s +* ((while>0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while>0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile>0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) ) & ex k being Nat st
( b2 = k & ((StepWhile>0 a,I,s) . k) . a <= 0 & ( for i being Nat st ((StepWhile>0 a,I,s) . i) . a <= 0 holds
k <= i ) & ((Computation (s +* ((while>0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while>0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile>0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) ) holds
b1 = b2
end;
:: deftheorem Def6 defines ExitsAtWhile>0 SCMFSA9A:def 6 :
for
s being
State of
SCM+FSA for
a being
read-write Int-Location for
I being
Macro-Instruction st (
ProperBodyWhile>0 a,
I,
s or
I is
parahalting ) &
WithVariantWhile>0 a,
I,
s holds
for
b4 being
Nat holds
(
b4 = ExitsAtWhile>0 a,
I,
s iff ex
k being
Nat st
(
b4 = k &
((StepWhile>0 a,I,s) . k) . a <= 0 & ( for
i being
Nat st
((StepWhile>0 a,I,s) . i) . a <= 0 holds
k <= i ) &
((Computation (s +* ((while>0 a,I) +* (Start-At (insloc 0))))) . (LifeSpan (s +* ((while>0 a,I) +* (Start-At (insloc 0)))))) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile>0 a,I,s) . k) | (Int-Locations \/ FinSeq-Locations ) ) );
theorem :: SCMFSA9A:41 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem Th42: :: SCMFSA9A:42 :: Showing IDV graph ... (Click the Palm Tree again to close it)
for
s being
State of
SCM+FSA for
a being
read-write Int-Location for
I being
Macro-Instruction st (
ProperBodyWhile>0 a,
I,
Initialize s or
I is
parahalting ) &
WithVariantWhile>0 a,
I,
Initialize s holds
(IExec (while>0 a,I),s) | (Int-Locations \/ FinSeq-Locations ) = ((StepWhile>0 a,I,(Initialize s)) . (ExitsAtWhile>0 a,I,(Initialize s))) | (Int-Locations \/ FinSeq-Locations )
theorem Th43: :: SCMFSA9A:43 :: Showing IDV graph ... (Click the Palm Tree again to close it)
theorem :: SCMFSA9A:44 :: Showing IDV graph ... (Click the Palm Tree again to close it)
Lm7:
for s being State of SCM+FSA
for I being Macro-Instruction st s . (intloc 0) = 1 holds
( I is_closed_on s iff I is_closed_on Initialize s )
Lm8:
for s being State of SCM+FSA
for I being Macro-Instruction st s . (intloc 0) = 1 holds
( I is_closed_on s & I is_halting_on s iff ( I is_closed_on Initialize s & I is_halting_on Initialize s ) )
theorem Th45: :: SCMFSA9A:45 :: Showing IDV graph ... (Click the Palm Tree again to close it)
for
s being
State of
SCM+FSA for
a being
read-write Int-Location for
Ig being
good Macro-Instruction st
s . (intloc 0) = 1 &
ProperBodyWhile>0 a,
Ig,
s &
WithVariantWhile>0 a,
Ig,
s holds
for
i,
j being
Nat st
i <> j &
i <= ExitsAtWhile>0 a,
Ig,
s &
j <= ExitsAtWhile>0 a,
Ig,
s holds
(
(StepWhile>0 a,Ig,s) . i <> (StepWhile>0 a,Ig,s) . j &
((StepWhile>0 a,Ig,s) . i) | (Int-Locations \/ FinSeq-Locations ) <> ((StepWhile>0 a,Ig,s) . j) | (Int-Locations \/ FinSeq-Locations ) )
:: deftheorem Def7 defines on_data_only SCMFSA9A:def 7 :
theorem Th46: :: SCMFSA9A:46 :: Showing IDV graph ... (Click the Palm Tree again to close it)
for
s being
State of
SCM+FSA for
a being
read-write Int-Location for
Ig being
good Macro-Instruction st
s . (intloc 0) = 1 &
ProperBodyWhile>0 a,
Ig,
s &
WithVariantWhile>0 a,
Ig,
s holds
ex
f being
Function of
product the
Object-Kind of
SCM+FSA ,
NAT st
(
f is
on_data_only & ( for
k being
Nat holds
(
f . ((StepWhile>0 a,Ig,s) . (k + 1)) < f . ((StepWhile>0 a,Ig,s) . k) or
((StepWhile>0 a,Ig,s) . k) . a <= 0 ) ) )
theorem :: SCMFSA9A:47 :: Showing IDV graph ... (Click the Palm Tree again to close it)
definition
let N,
result be
Int-Location ;
set next = 1
-stRWNotIn {N,result};
set aux = 2
-ndRWNotIn {N,result};
set rem2 = 3
-rdRWNotIn {N,result};
func Fusc_macro N,
result -> Macro-Instruction equals :: SCMFSA9A:def 8
(((SubFrom result,result) ';' ((1 -stRWNotIn {N,result}) := (intloc 0))) ';' ((2 -ndRWNotIn {N,result}) := N)) ';' (while>0 (2 -ndRWNotIn {N,result}),((((3 -rdRWNotIn {N,result}) := 2) ';' (Divide (2 -ndRWNotIn {N,result}),(3 -rdRWNotIn {N,result}))) ';' (if=0 (3 -rdRWNotIn {N,result}),(Macro (AddTo (1 -stRWNotIn {N,result}),result)),(Macro (AddTo result,(1 -stRWNotIn {N,result}))))));
correctness
coherence
(((SubFrom result,result) ';' ((1 -stRWNotIn {N,result}) := (intloc 0))) ';' ((2 -ndRWNotIn {N,result}) := N)) ';' (while>0 (2 -ndRWNotIn {N,result}),((((3 -rdRWNotIn {N,result}) := 2) ';' (Divide (2 -ndRWNotIn {N,result}),(3 -rdRWNotIn {N,result}))) ';' (if=0 (3 -rdRWNotIn {N,result}),(Macro (AddTo (1 -stRWNotIn {N,result}),result)),(Macro (AddTo result,(1 -stRWNotIn {N,result})))))) is Macro-Instruction;
;
end;
:: deftheorem defines Fusc_macro SCMFSA9A:def 8 :
for
N,
result being
Int-Location holds
Fusc_macro N,
result = (((SubFrom result,result) ';' ((1 -stRWNotIn {N,result}) := (intloc 0))) ';' ((2 -ndRWNotIn {N,result}) := N)) ';' (while>0 (2 -ndRWNotIn {N,result}),((((3 -rdRWNotIn {N,result}) := 2) ';' (Divide (2 -ndRWNotIn {N,result}),(3 -rdRWNotIn {N,result}))) ';' (if=0 (3 -rdRWNotIn {N,result}),(Macro (AddTo (1 -stRWNotIn {N,result}),result)),(Macro (AddTo result,(1 -stRWNotIn {N,result}))))));
theorem :: SCMFSA9A:48 :: Showing IDV graph ... (Click the Palm Tree again to close it)