https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @kagamilove0707 @kmizu 横レス失礼します。execution traceにマッチする文法が書ける、というだけだとあまりチューリング完全とは言わないのでは。文法がチューリング完全というと「入力文字列が文法にマッチするかの判定が決定不能」という印象を受けます。 | |
| @kagamilove0707 @kmizu 与えられた文法が空集合かの判定問題などがチューリング完全とは言えますが、これはMacroじゃない普通のPEGが既にそう（チューリングマシンのexecution traceを表現できることが知られている）なのでどうしようもなさそう。 | |
| @kagamilove0707 @kmizu はい、[Ford04] https://t.co/rgm0IJgQ92 の6頁目左のundecidabilityの定理です。証明ではPCP(Postの対応問題)からの帰着ですが、PCPがチューリングマシン書けるのは色んな教科書とかに。 | |
| @kagamilove0707 @kmizu はい、issueで触れられていた一階述語論理で言うと、証明として妥当かを検証するのに必要な能力は、命題が証明可能かどうかの判定能力より弱くて済むというところに相当すると思います。 | |
| @kagamilove0707 @kmizu 後者はyesです。前者は、"言語が決定可能である" https://t.co/T1DEgv3ezm という用語は"ある文字列が属するかを決定できる"を意味するので、noです。"言語L(G)の空性の判定は決定可能でない"ならばyesです | |
| @kmizu @kagamilove0707 あ、はい、それは自分でも書いてて思ったのですが、まあ他の意味に解釈される心配はなかろうと思って適当にしてしまいました… | |
| 空集合、海集合 |