我是Agda的新手,需要幫助瞭解Decidable函數和Dec類型。 我想定義一個一階邏輯謂詞,我想用證明編碼某種布爾值。我發現這樣做的方法是使用Dec類型.. 現在,據我所知,能夠做到這一點,我必須重新定義所有邏輯運算符的類型是可判定的,而不是類型集。這樣做,我有點嵌入成新的類型,這是我這樣做是爲了和運營商: data _∧_ (A B : Set) : Set where
_&_ :
類型謂詞生成運行時證明我使用此類型推理可以在其上進行可判定的解析字符串: data Every : (a -> Type) -> List a -> Type where
Nil : {P : a -> Type} -> Every P []
(::) : {P : a -> Type} -> P x -> Every P xs -> Every P (x::xs)
例如,
L = { <M> | M is a Turing machine over {0, 1}, and <M>||<M> (not in) L(M)}
如何證明L不可識別?有任何想法嗎? 我已經證明了L compliment是可識別的: Set Turing machine to J
1. Run J on input <M>||<M>
2. TM J accepts then accept