編集部が厳選した「いま、みんなに見てほしいまとめ」をイチオシとして紹介しています!グサッと刺さる良質まとめはこちら!

【第10回関西すうがく徒のつどい1日目】決定不能問題の話 #kansaimath

2017/09/16 第10回関西すうがく徒のつどい(#kansaimath)1日目 108教室(#kansaimath108) 決定不能問題の話 y. (@waidotto)
関西すうがく徒のつどい kansaimath 数学
1067view 1コメント
1
ログインして広告を非表示にする
使用したスライド
y. @waidotto
今日の講演で使ったスライドを修正して公開しました. iso.2022.jp #kansaimath
y. @waidotto
講演中で使用したTuring機械のシミュレーションはこれです turingmachinesimulator.com/shared/djexnjj… #kansaimath
講演の実況
alg_d @alg_d
実況的には明らかにBだが内容的にA聞いてみたい感 #kansaimath
最の低なひと @tenapyon
基礎論クラスタ意外といるなあ #kansaimath
ぴあのん@さよ朝宣伝bot @piano2683
「自己紹介しようと思ったが紹介するほどの自己がない」 #kansaimath #kansaimath108
(☝ ՞ਊ ՞)☝イイイィネ!!!bot @iiiiiiiiine_bot
突然ですが問題です。整数が素数かどうかを判定するにはどうすればよいか? #kansaimath #kansaimath108
(☝ ՞ਊ ՞)☝イイイィネ!!!bot @iiiiiiiiine_bot
あくまで「特定の数にたいしての判定法ではなく、統一的な判定法を与えよ」 という問題。 #kansaimath #kansaimath108
ぴあのん@さよ朝宣伝bot @piano2683
与えられた文字列に対して、Yes/Noで答える問題を決定問題という #kansaimath #kansaimath108
(☝ ՞ਊ ՞)☝イイイィネ!!!bot @iiiiiiiiine_bot
文字の集合(有限集合)をfixして、文字列(文字の限の有限列全体)を考えてる #kansaimath #kansaimath108
(☝ ՞ਊ ՞)☝イイイィネ!!!bot @iiiiiiiiine_bot
入力が有限の場合は、有限の場合分けを考えれば終わってしまうので、決定問題を考えるときは入力が無限にある場合を考えないと意味がない! #kansaimath #kansaimath108
ぴあのん@さよ朝宣伝bot @piano2683
「決定不能問題」はアルゴリズムが存在しないような決定問題を探せば良い。これには「アルゴリズム」の数学的定義が不可欠 #kansaimath #kansaimath108
(☝ ՞ਊ ՞)☝イイイィネ!!!bot @iiiiiiiiine_bot
決定問題のうち、それを解くアルゴリズムが存在しないようなものを探せばよいので「アルゴリズム」の数学的な定義を考える。 #kansaimath #kansaimath108
でぃぐ @fujidig
チューリング機械説明するの大変だよね #kansaimath #kansaimath108
ぴあのん@さよ朝宣伝bot @piano2683
使える文字をa,bとしたときに「与えられた文字列がa…ab…bの形をしているかどうか」を判定するTuring機械 #kansaimath #kansaimath108
残りを読む(95)

コメント

y. @waidotto 2017-09-17 13:48:14
Turing machine simulatorへのリンクを追加しました
ログインして広告を非表示にする
ログインして広告を非表示にする