【第12回関西すうがく徒のつどい2日目】Friedberg-Muchnikの定理と有限害優先論法 #kansaimath
2019/03/30
第3回関東すうがく徒のつどい(#kantomath)2日目
303
Friedberg-Muchnikの定理と有限害優先論法
y. (@waidotto)
-
- いいね！0
関東すうがく徒のつどい
@kantotsudoi
決定不能性の証明の多くは「考えている決定問題を判定するアルゴリズムの存在を仮定し，停止問題を判定するアルゴリズムを構成できる」というスタイルで行われる #kansaimath303
2019-10-27 14:55:43
ぴあのん
@piano2683
決定不能問題だが「停止問題の決定性に帰着する方法」で示せないものが存在（Friedberg-Muchnikの定理） #kansaimath #kansaimath303
2019-10-27 14:56:46
ぴあのん
@piano2683
字幕こんな感じ #kansaimath #kansaimath303 pic.twitter.com/izieLdI8xb
2019-10-27 14:58:33
拡大
関東すうがく徒のつどい
@kantotsudoi
有限なデータは符号化することによりある自然数の2進展開だと思える #全ての有限な概念は自然数である #kansaimath303
2019-10-27 15:00:19
ぴあのん
@piano2683
決定問題は、「自然数集合ωの部分集合」もしくは「特性関数f: ω→{0,1}」を計算するアルゴリズムの存在問題と言い換えられる #kansaimath #kansaimath303
2019-10-27 15:02:29
関東すうがく徒のつどい
@kantotsudoi
A⊂ωについて，「Aが決定可能⇔Aの特性関数を計算するアルゴリズムが存在」という換言ができる #kansaimath303
2019-10-27 15:03:00