changeset 180:4c5d26c149fa

...
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Thu, 18 Mar 2021 07:47:39 +0900
parents f226c21d61bf
children 9c63284d7695
files agda/halt.agda
diffstat 1 files changed, 18 insertions(+), 24 deletions(-) [+]
line wrap: on
line diff
--- a/agda/halt.agda	Thu Mar 18 00:16:42 2021 +0900
+++ b/agda/halt.agda	Thu Mar 18 07:47:39 2021 +0900
@@ -60,7 +60,6 @@
 open UTM 
 
 open _∧_
-open ≡-Reasoning
 
 open import Axiom.Extensionality.Propositional
 postulate f-extensionality : { n : Level}  → Axiom.Extensionality.Propositional.Extensionality n n 
@@ -71,50 +70,45 @@
       is-halt :     (t : TM ) → (x : List Bool ) → (halt t x ≡ true )  ⇔ ( (just true ≡ tm t x ) ∨ (just false ≡ tm t x ) )
       is-not-halt : (t : TM ) → (x : List Bool ) → (halt t x ≡ false ) ⇔ ( nothing ≡ tm t x )
 
-record HaltIsTM (ha : Halt) (utm : UTM) : Set where
-   field
-      htm : TM
-      htm-is-halt : (t : TM ) → (x : List Bool ) → (Halt.halt ha t x ≡ true ) ⇔ ( just true ≡ tm htm (encode utm t ++ x) )
-
 open Halt
 
-TNL : (halt : Halt ) → (utm : UTM) → HaltIsTM halt utm → HBijection (List Bool → Bool) (List Bool)
-TNL halt utm halt-is-tm = record {
+TNL : (halt : Halt ) → (utm : UTM) → HBijection (List Bool → Bool) (List Bool)
+TNL halt utm = record {
        fun←  = λ tm x → Halt.halt halt (UTM.utm utm) (tm ++ x)
      ; fun→  = λ h  → encode utm record { tm = h1 h } 
      ; fiso← = λ h →  f-extensionality (λ y → TN1 h y )
   } where
+     open ≡-Reasoning
      h1 : (h : List Bool → Bool) → (x : List Bool ) → Maybe Bool
      h1 h x with h x
      ... | true =  just true
      ... | false = nothing
+     tenc : (h : List Bool → Bool) → (y : List Bool) → List Bool
+     tenc h y = encode utm (record { tm = λ x → h1 h x }) ++ y
      h-nothing : (h : List Bool → Bool) → (y : List Bool) → h y ≡ false → h1 h y ≡ nothing
      h-nothing h y eq with h y
      h-nothing h y refl | false = refl
      h-just : (h : List Bool → Bool) → (y : List Bool) → h y ≡ true → h1 h y ≡ just true
      h-just h y eq with h y
      h-just h y refl | true = refl
-     TN1 :  (h : List Bool → Bool) → (y : List Bool ) → Halt.halt halt (UTM.utm utm) (encode utm (record { tm = h1 h }) ++ y) ≡ h y
+     TN1 :  (h : List Bool → Bool) → (y : List Bool ) → Halt.halt halt (UTM.utm utm) (tenc h y) ≡ h y
      TN1 h y with h y | inspect h y
      ... | true  | record { eq = eq1 } = begin
-        Halt.halt halt (UTM.utm utm)  (encode utm (record { tm = λ x → h1 h x }) ++ y) ≡⟨ proj2 (is-halt halt (UTM.utm utm) y1 ) (case1 (sym tm-y1)) ⟩
+        Halt.halt halt (UTM.utm utm)  (tenc h y) ≡⟨ proj2 (is-halt halt (UTM.utm utm) (tenc h y) ) (case1 (sym tm-tenc)) ⟩
         true ∎  where
-          open ≡-Reasoning
-          y1 : List Bool
-          y1 = encode utm (record { tm = λ x → h1 h x }) ++ y
-          tm-y1 = begin
-              tm (UTM.utm utm) (encode utm (record { tm = λ x → h1 h x }) ++ y)  ≡⟨  is-tm utm _ y ⟩
+          tm-tenc :  tm (UTM.utm utm) (tenc h y) ≡ just true
+          tm-tenc = begin
+              tm (UTM.utm utm) (tenc h y)  ≡⟨  is-tm utm _ y ⟩
               h1 h y ≡⟨ h-just h y eq1  ⟩
-              just true  ∎  where
+              just true  ∎  
      ... | false | record { eq = eq1 } = begin
-        Halt.halt halt (UTM.utm utm)  (encode utm (record { tm = λ x → h1 h x }) ++ y) ≡⟨ proj2 (is-not-halt halt (UTM.utm utm) y1 ) (sym tm-y1) ⟩
+        Halt.halt halt (UTM.utm utm)  (tenc h y) ≡⟨ proj2 (is-not-halt halt (UTM.utm utm) (tenc h y) ) (sym tm-tenc) ⟩
         false ∎  where
-          open ≡-Reasoning
-          y1 : List Bool
-          y1 = encode utm (record { tm = λ x → h1 h x }) ++ y
-          tm-y1 :  tm (UTM.utm utm) (encode utm (record { tm = λ x → h1 h x }) ++ y) ≡ nothing
-          tm-y1 = begin
-              tm (UTM.utm utm) (encode utm (record { tm = λ x → h1 h x }) ++ y)  ≡⟨  is-tm utm _ y ⟩
+          tm-tenc :  tm (UTM.utm utm) (tenc h y) ≡ nothing
+          tm-tenc = begin
+              tm (UTM.utm utm) (tenc h y)  ≡⟨  is-tm utm _ y ⟩
               h1 h y ≡⟨  h-nothing h y eq1 ⟩
-              nothing  ∎  where
+              nothing  ∎  
+     -- the rest of bijection means encoding is unique
+     -- fiso→ :  (y : List Bool ) → encode utm record { tm = λ x →  h1 (λ tm → Halt.halt halt (UTM.utm utm) tm  ) x } ≡ y