Follow

9月になりました.決定不能問題ギャラリー第9弾は「文脈自由言語の普遍性判定問題」です!
iso.2022.jp/math/undecidable-p
プッシュダウンオートマトンは「Turing機械の計算の履歴である」ことを検査する能力を持たない一方で,「計算の履歴でない」ことは検査できることを見ます.
mathtod.online/media/gBI_iby-Y mathtod.online/media/N6P74cUfe mathtod.online/media/kf5eKU1oS mathtod.online/media/cgZG-ROTX

主定理でSipserを\citeするのを忘れていたので慌てて追加した

Sign in to participate in the conversation
Mathtodon

■ Post mathematical formulae on Mathtodon. / 数式が書けるSNS、ついに登場。 This is a Mastodon instance named Mathtodon, where you can post toots with mathematical formulae in TeX/LaTeX style. Let's enjoy mathematical talks, mathematical discussions, and mathematical jokes in Mathtodon! Please join us! 数式が書けるMastodon、その名もMathtodonです! (˃̵ᴗ˂̵ ζ) 数式は TeX, LaTeX 形式です。数学の情報発信や数学の議論や数学ギャグの投稿など、様々に楽しみましょう〜! ■ Donation / ご寄付について Thankfully I'm getting many inquiries about donation. Although I of course spend some amount of my pocket money such as server fee and domain fee, I think that using your brains to create a gentle world of mathematics is very valuable and is the best donation. If you still want to make a donation, please use here 1AhmL4t7aqgQzs4ZG1PPcS2uY8Bz39DRQv (Bitcoin). ありがたくも「寄付はどうすればいい?」というお言葉を数多くいただいています。 もちろんサーバ代・ドメイン代などポケット予算より費やしておりますが、今はそれよりも「数学が好きな人の集まる優しい世界」を構築することに、皆様の頭脳と貴重な時間とほんの少しずつ分けていただければそれが最高の donation だと思います。(←決まった!) それでもなお donation をお考えという奇特な方は、 1AhmL4t7aqgQzs4ZG1PPcS2uY8Bz39DRQv (Bitcoin) か、あるいはAmazonの謎のリンクをご覧ください。