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

y. @waidotto

今日の講演で使ったスライドを修正して公開しました． iso.2022.jp #kansaimath

y. @waidotto

講演中で使用したTuring機械のシミュレーションはこれです turingmachinesimulator.com/shared/djexnjj… #kansaimath

V-alg-d（ZZ） @alg_d

実況的には明らかにBだが内容的にA聞いてみたい感 #kansaimath

最の低なひと @tenapyon

基礎論クラスタ意外といるなあ #kansaimath

y. @waidotto

発表をします #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

y.くんの講演を聞きに来た #kansaimath #kansaimath108

ぴあのん @piano2683

決定不能問題の話（@waidotto） #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

紹介するほどの自己がない #kansaimath #kansaimath108

ぴあのん @piano2683

「自己紹介しようと思ったが紹介するほどの自己がない」 #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

実況するぞ〜〜〜 #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

突然ですが問題です。整数が素数かどうかを判定するにはどうすればよいか？ #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

あくまで「特定の数にたいしての判定法ではなく、統一的な判定法を与えよ」 という問題。 #kansaimath #kansaimath108

ぴあのん @piano2683

与えられた文字列に対して、Yes/Noで答える問題を決定問題という #kansaimath #kansaimath108

ぴあのん @piano2683

てかy. くんスライド挙げてないかな #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

文字の集合(有限集合)をfixして、文字列(文字の限の有限列全体)を考えてる #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

入力が有限の場合は、有限の場合分けを考えれば終わってしまうので、決定問題を考えるときは入力が無限にある場合を考えないと意味がない！ #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

疑問(その1) 「決定不能問題」は存在するか？ #kansaimath #kansaimath108

ぴあのん @piano2683

「決定不能問題」はアルゴリズムが存在しないような決定問題を探せば良い。これには「アルゴリズム」の数学的定義が不可欠 #kansaimath #kansaimath108

(☝ ՞ਊ ՞)☝ｲｲｲｨﾈ!!!bot @iiiiiiiiine_bot

決定問題のうち、それを解くアルゴリズムが存在しないようなものを探せばよいので「アルゴリズム」の数学的な定義を考える。 #kansaimath #kansaimath108

ぴあのん @piano2683

計算モデルのひとつとしてのTuring機械 #kansaimath #kansaimath108

ぴあのん @piano2683

Turing機械の定義と動作 #kansaimath #kansaimath108

でぃぐにゃん @fujidig

チューリング機械説明するの大変だよね #kansaimath #kansaimath108

ぴあのん @piano2683

使える文字をa,bとしたときに「与えられた文字列がa…ab…bの形をしているかどうか」を判定するTuring機械 #kansaimath #kansaimath108