-
Notifications
You must be signed in to change notification settings - Fork 0
/
Computation.agda
63 lines (50 loc) · 1.84 KB
/
Computation.agda
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
module Computation where
open import Data.Prim.Coinduction
open import Data.Bool
open import Data.Bool.Operations
open import Data.False
open import Data.Fin
open import Data.Nat
open import Data.Nat.Operations
open import Data.Nat.Relations
open import Data.Stream
open import Data.Product
open import Data.PropositionalEquality
import Data.Stream.Operations as StreamOps
open import Data.Vector
open import Functions renaming (_^_ to _^^_)
Memory : (n : Nat) → Set
Memory n = Vector Bool n
CPU : (n : Nat) → Set
CPU n = Memory n → Memory n
ExecutionTrace : {n : Nat} → (cpu : CPU n) → (start : Memory n) → Stream (Memory n)
ExecutionTrace {n} cpu start = start ∷ (♯ (ExecutionTrace cpu (cpu start)))
all-zeroes : (n : Nat) → Memory n
all-zeroes 0 = []
all-zeroes (suc n) = false ∷ (all-zeroes n)
my-CPU : CPU 256
my-CPU (a ∷ as) = (not a) ∷ as
my-mem-config : Memory 256
my-mem-config = all-zeroes 256
my-trace : Stream (Memory 256)
my-trace = ExecutionTrace my-CPU my-mem-config
{-# NON_TERMINATING #-}
loop : Stream (Memory 256) → ⊥
loop state = loop (StreamOps.tail state)
{-# NON_TERMINATING #-}
main : ⊥
main = loop my-trace
{-
How should `main` be compiled if `my-CPU` actually models my CPU?
If `my-CPU` actually models my CPU, then `my-trace` is the stream of
states that my CPU will go through when starting in the memory configuration
`my-mem-config`. `main` is a non-terminating computation that actually
goes through each state. We can make my CPU do that by initializing my
memory configuration to `my-mem-config`.
-}
{-
CPU-attractors : {n : Nat} → (cpu : CPU n) → (state : Memory n) → ∃ k ∈ Nat , (∃ r ∈ Nat , ((k ≤ (2 ^ n)) ∧ (k > 0) ∧ (r ≤ (2 ^ n)) ∧ (r > 0) ∧ ((m : Nat) → ((cpu ^^ (k + (m * r))) state) ≡ ((cpu ^^ k) state))))
CPU-attractors {n} cpu state = proof
where
proof
-}