コンピュータの限界は「テープを読み書きする機械」で分かる。チューリングマシンはすごい【チューリング3】#34
HTML-код
- Опубликовано: 28 июл 2024
- チューリング第3弾です。今回は「チューリングの論文は無限に長いテープを準備するところから始まった」「まだこの世にないコンピュータの限界を示した」「無限ループを検出することは原理的に不可能」など、チューリングの主要な功績である「決定問題」の論文についてゆるく解説しました。
【目次】
00:00 「ブラックボックスはお前だ」と言い合う闇の回は仕方なかった
01:28 チューリングの論文は「無限に長い機械」から始まる
05:36 チューリングマシンあるある「だから何？」
12:59 この機械は以前に出てきた「アレ」と同じ
18:49 論文のスゴさは「コンピュータの限界」を示したこと
28:10 「アルゴリズムで書けない」って何？
31:41 「ブラックボックスはお前だ」と停止性問題
39:24 次回テーマは「チューリングの功績の原体験」
【参考文献】
○『エニグマ アラン・チューリング伝（上）』
amzn.to/3vuR3o
○『エニグマ アラン・チューリング伝（下） 』
amzn.to/3zNBs5t
→この世で一番詳しいチューリングの伝記。上下巻で1000ページぐらいある。どうしてもチューリングについて詳しく知りたければこちらを。
○『暗号解読（上・下）』
amzn.to/3BJHi9m
→世界一おもしろいサイエンスライター（私見）であるサイモン・シンが書いた、超エキサイティングな暗号の歴史と仕組みの本。歴史ドラマは熱いし、仕組み解説は好奇心をくすぐられます。最高。
○『チューリングの計算理論入門』
amzn.to/3BLQIkF
→安定のブルーバックス。チューリングマシンについてざっくり理解したいならオススメ。なんとなく雰囲気が分かります。
○『チューリングを読む コンピュータサイエンスの金字塔を楽しもう』
amzn.to/3Q3piv6
→チューリングの論文を全文引用しながら丁寧に読解する本。難しいがおもしろい。この手の骨太本には珍しく、うんちく力が高い。前提知識の説明でうんちくメモを取りまくった。
【サポーターコミュニティ加入はこちらから】
yurugengo.com/support
【親チャンネル：ゆる言語学ラジオ】
/ @yurugengo
【おたよりフォーム】
forms.gle/BLEZpLcdEPmoZTH4A
※皆様からの楽しいおたよりをお待ちしています！
【お仕事依頼はこちら！】
yurugengo@gmail.com
【堀元見プロフィール】
慶應義塾大学理工学部卒。専門は情報工学。WEBにコンテンツを作り散らかすことで生計を立てている。現在の主な収入源は「アカデミックに人の悪口を書くnote有料マガジン」。
Twitter→ / kenhori2
noteマガジン→note.com/kenhori2/m/m125fc452...
個人RUclips→ / @kenhorimoto
【水野太貴プロフィール】
名古屋大学文学部卒。専門は言語学。
某大手出版社で編集者として勤務。言語学の知識が本業に活きてるかと思いきや、そうでもない。
#チューリング #ゆるコンピュータ科学ラジオ #チューリングマシン
【参考文献】
○『エニグマ アラン・チューリング伝（上）』
amzn.to/3G0Zzje
○『エニグマ アラン・チューリング伝（下） 』
amzn.to/3zNBs5t
→この世で一番詳しいチューリングの伝記。上下巻で1000ページぐらいある。どうしてもチューリングについて詳しく知りたければこちらを。
○『暗号解読（上・下）』
amzn.to/3BJHi9m
→世界一おもしろいサイエンスライター（私見）であるサイモン・シンが書いた、超エキサイティングな暗号の歴史と仕組みの本。歴史ドラマは熱いし、仕組み解説は好奇心をくすぐられます。最高。
○『チューリングの計算理論入門』
amzn.to/3BLQIkF
→安定のブルーバックス。チューリングマシンについてざっくり理解したいならオススメ。なんとなく雰囲気が分かります。
○『チューリングを読む コンピュータサイエンスの金字塔を楽しもう』
amzn.to/3Q3piv6
→チューリングの論文を全文引用しながら丁寧に読解する本。難しいがおもしろい。この手の骨太本には珍しく、うんちく力が高い。前提知識の説明でうんちくメモを取りまくった。
【サポーターコミュニティ加入はこちらから】
yurugengo.com/support
【親チャンネル：ゆる言語学ラジオ】
ruclips.net/channel/UCmpkIzF3xFzhPez7gXOyhVg
【おたよりフォーム】
forms.gle/BLEZpLcdEPmoZTH4A
※皆様からの楽しいおたよりをお待ちしています！
社内MTG時、上司の「クライアントのここがブラックボックスになりがちなので注意しないとね」に
「ブラックボックスなのはお前だ！」って返しそうになって危なかった。
チューリングにしろ、ガロアにしろ、ウィトゲンシュタインにしろ、
「ここからは解けないよ」って
限界を明示できる人好き。
なんか、戦っているレイヤーが違うよな
「例え話は誤解の嵐」
韻を踏んでて良い言葉
察しが良い人は台本をぶっ壊すため忌避され、迂闊に話しすぎる人はラクに話せるため歓迎される直感を裏切る謎の空間
「屈指のひどい回」の心当たりが多過ぎて答えられない水野
プリン
プリン
プリン
個人的には「大泉」
シグルイ
今までの話が一つの束にまとまってく感じで面白かった！
つまり、トランジスタやチューリングマシンの手続きを組み合わせることによって巨大なプリンが焼き上げられるってことなんですね！
数学では無限大という概念がかなり厳密に定義されて、高校数学でも扱える程度にまで普遍的な存在として認められているわけなのですが、物理学では無限という概念をあまり安易に使わない傾向にあります。その代わりに「十分に」という表現を使います。例えば「無限に長い」ではなくて「十分い長い」という言い方をします。簡単に言うと、どこまでテープの上を移動するかわからないけど、テープの端っこまで行っちゃってはみ出ることはないとしようね、ってことです。個人的には、その問題を突き詰めるとややこしい話になるので、とりあえずその問題については考えないことにしましょう、という約束事だと思っています。
物理学者はこういう問題の先送り的なことを頻繁に行うのですが、数学者は必ずそこで引っ掛かります。つまり、数学者は、はしごが安全なことを確かめてからでないと、そのはしごを登ろうとしないのですが、物理学者は、安全かどうかわからないはしごを、とりあえず登ってみようとします。登ったうえで考える価値がありそうな問題であれば、それからはしごの安全性についての議論が始まります。この点を理解しておかないと、物理学者と数学者とのあいだで不毛な議論が始まることになります。お互いにとってなにが重要なのか、を正確に把握しておくことは意外と重要です。
@@vonneumann6161 無限ホテルのパラドックスは、有限の世界で培った直観が無限に対してそのまま通用しないことを示す教訓話とみるべきで、本当の意味のパラドックスではなく、「そのまま扱うとおかしくなる事の喩え」ではないと思います。論理的矛盾が生じているわけではないので。
また、現在の数学で有限の立場を貫いている分野はほぼ無いように思います。それぞれに実無限にあたるものを導入したりして理論を構築しているように思いますが、いかがでしょうか
形式科学か、自然科学かの違いじゃない？
工学畑から見ると
物理学者も形式科学的ではしごを登らない人種に見えるので面白いもんですね
白黒決めれるものではなく、グラデーションだからね。
9:34のルールのPはprint(書き込む)という意味です。
原論文でも "P" stands for "prints". と書かれています。
専門家降臨
こんなところにもプリンが！？
4:53 無限そのものは古代インドなどの時点で知られていた概念ですが、無限にも"大小"があるということは19世紀末のカントールまで知られていませんでした。
無限ホテルが考案された1924年時点でも、例えば連続体仮説の真偽(後にZFCからは証明も反証もできないことがわかる)すら不明だったので、20世紀の話だからと言って様々なことが既に分かっているかというと(特に計算機科学や基礎論などは)実はそんなこともなかったりします。
アルゴリズムやデカルトやトランジスタ等今までの積み合わせが実を結ぶとても良いテーマで好き。
チューリングマシンが偉大と思うところのひとつは、結局、他の計算可能性概念（λ計算可能性、帰納的関数）と計算可能性の範囲が一致し、これがチャーチ＝チューリングの提唱（「計算可能」という概念の提唱）に結びついたところですね。
「計算できる」という（漠然とした）一般的な概念がチューリングマシンで表現でできてしまうというのは、最初に知ったときには驚きでした。
これ水野さんが言った「時間をかければできる気がする」結構重要な観点で、一見複雑そうな問題も
「細分化して支配」すれば、アルゴリズム自体の構成が間違ってない限りは、答えを導き出せる、って言うコンピューターそのものへの言及なんだよな。
掛け算のやつを愚直にプログラミングしてみたら、再帰呼び出し多すぎて「スタック領域不足です」ってなりました
#タランチューニング #御茶女問題 # #水野の低姿勢問題 などの様々な言語をすぐに生み出すから水野さんめっちゃ言語得意な人だ。
今はもう縁が切れましたが、コンピュータの初期の歴史はテープが必ずからんできますね。トランク一杯のパンチカードを紙の鑽孔テープに打ち直し、直径20センチもあるロールを電算室に持ち込めば、中には2つの磁気テープがぐるぐる回るストレージが何台も立ち並び、今のHDレコーダーの3倍もある箱形の「フロッピーディスク」をがしゃりとはめて・・はいはい石器時代のお話ですｗ
定期的に大きいプリンで虐待される堀元さん好き
堀本さん、聞き手としての能力高いし話の引き出しも沢山あって頭いい人なんだな〜って思うけど、例え話だけが激烈にセンスなくてほんとに面白い
コンピュータ科学の教科書と同じだ！
知識量が多くて、聞き手として優秀なのは同意しますが、たとえ話だけでなく、説明がグダグダで話し手としては全体としてダメダメでしょう。ビジネス書１００冊読むライブは面白いのに。数学的センスはあるのにITや物理はからきしな水野さんと同じく不思議です。
具体→抽象のプロセスを普遍的にやってるから、そのノリでその逆を実行しようとするとバグが発生してショートする堀元さん
具体 抽象
い ↘
ろ ↘
ん →まとめ
な ↗
例 ↗
良例
良例
良例 まとめ
悪例↗
良例
抽象化は上手いのに具体化でそれ選ぶかぁ…笑
ロボット手術において触覚の再現がかなり難しい。なぜなら物を触れた時に潰しすぎないために、停止と作動という反する動作を同時におこなう必要があるためだ。
これを聞いて、そんなに難しいのかなぁともやもやしてましたが、停止性問題の概念を聞いてカタルシスしました。ありがとうございます。
この話の後にある、算術的階層の話が、「アルゴリズムがあるとかないとかってなんやねん」の疑問の答えになっててとても良いんだよな
6:53 嘘では…？ 有限状態オートマトンによって記述できるアルゴリズムによって解ける問題の集合は、チューリングマシンによって記述できるアルゴリズムによって解ける問題の集合より真に小さいはずです(ちなみに、無限状態オートマトンはむしろ(計算不可能なものを含む)任意の問題を解けてしまうので、「計算」のモデルとしては全然正しくないです)。というか、「オートマトン」という「問題のサイズによらず固定された数の有限状態しか取れない」装置に、「無限に長いテープ」という外部記憶装置をつけることで、「使えるメモリ自体は有限だが後からいくらでもメモリを追加できる」ようにしたのがチューリングマシンで、これによってテープを含むマシン全体の状態数は可算無限まで上がっているので、マシン全体の状態数が有限に固定されるオートマトンとは計算力が違うと思います。
@おび太 プッシュダウン・オートマトンは等価ではないと思います。「スタック」=「いくらでも大量の文字を記憶できる記憶装置だが、最後に記憶した文字しか読み出せず、最後に記憶した文字を削除して初めて最後から2番目に記憶した文字を読み出すことができる記憶装置」が「1個」ついたオートマトンがプッシュダウン・オートマトンで、「1個」だけではチューリングマシンほどの計算能力は持てないので。
とはいえ、スタックが2個付いたオートマトンは確かにチューリングマシンと等価、というかそれはほとんどチューリングマシンそのものです。なので確かに考えたんですよね。「不正確」として取り下げるべきじゃないかと。
ですが、プッシュダウンオートマトンって「外部記憶装置付きオートマトン」で、「外部記憶装置付きのオートマトン」って言ったらチューリングマシン自身がそうなんですよね。「外部記憶装置付きオートマトンもオートマトンだ」…というのは普通の考え方ではあるのですが、その考え方をするとオートマトンとチューリングマシンを別物扱いする理由がなくなって、チューリングマシンがオートマトンの一種ということになっちゃいます。
「チューリングマシンはオートマトンの一種」なら「チューリングマシンはオートマトンと等価」という言葉そのものが意味不明になるので、「オートマトン」という言葉はチューリングマシンを含まないような意味で使われていると考えるほかない、と考えました。そうするとプッシュダウン・オートマトンもオートマトンとは呼べないと思ったので、取り下げとかはせずにそのままにする方が良いかな、と考えたんですよね。
17:50 「細かいことをつみあわせて」
30:49 「グーテンターク問題」かわいい
コンピュータが誕生する前からRUclipsとかゲームとか天気予報とかを実現するアルゴリズムさえ考えれば必ずこのマシンで実現可能だと証明したって言えば感動だよね
33:15 掘元さんのたとえが成功するか問題
水野さん「それはわかる」
視聴者「それはわかる」
掘元さん「わからないなぁ〜」
楽しみに待ってました
31:00
厳密な議論ではありませんが、計算可能=証明可能 はざっくり以下のように説明できます。
チューリングマシンの挙動(テープに書かれた文字を読み、状態を更新しながらテープを書き換える)は
人間の数学者の挙動(ノートに書かれた文字を読み、考えを更新しながらノートに書き込んでいく)と等価なので
数学者にできることとチューリングマシンにできることは等価です。
よって、証明可能=人間が証明をノートに書ける=チューリングマシンで計算可能、となります。
(厳密には、証明可能という言葉の定義や数学者の定式化から議論を始める必要があります)
チューリングマシーン 基本情報にでてくる機械語命令のアレだったのか……
チューリングマシンはGoogleがチューリング生誕100周年の時に出した体験ゲームみたいなのが面白かったです。
24:30 くらいからの件で水野さんがぴんと来てない感じだったけど、研究に応用されている例だと分かりやすいと思います。
URLはヨビノリさんの学術対談です。紹介されている研究では、熱力学的な状態をアルゴリズムと1対1で対応させることで、熱平衡化についての問題を停止性問題に落とし込んでいます。”アルゴリズムがあるなら解ける”、”停止するかどうかは判断できない”の二つを合わせて使うと強力な武器になるっていう印象です。
ruclips.net/video/OSYc21aEcDY/видео.html
ここ2週間、チューリングってどこかで聞いたことあるなぁとモヤモヤしていましたが、先程思い出しました！チューリングテストでした！！
無限の濃度に関する数学的議論の始まりはカントールという数学者にあるといえますが、カントールはガロアよりも後に生まれています。それくらいに無限については分かっていませんでした。 ヒルベルトプログラムの一問目も無限の濃度に関する問題です。このことからヒルベルトは確実に無限について頭を悩ませていたと思います。無限を軽率に扱っている二人には無限について本格的に学んで無限にシバかれてほしいと思います。私は大学1年生にシバかれました。
選択公理を認めるべきか否か......
歯車とか機構でチューリングマシンつくれました！ → まって、真空管ってやつでもチューリングマシン作れんじゃね？ → 半導体ってやつでも同じことできるっぽいわ → コンピュータ=半導体だよね←いまココ
34:09 足らん・チューニング（アラン＝チューリングと掛けた超絶面白ダジャレ）
チューリングマシンの話なら、チューリング完全(チューリングマシンと 等価と見做せる)である意外なもの、というのがうんちく的に面白いかも
6:42 オートマトンがチューリング完全な世界線、queueでも積んでいるのか…?
チューリングマシンも(広義の)オートマトンの一種、と定義する流儀もあるので、そっちの世界線かもしれません
11:08 機械アレルギーで急に嘔吐する水野氏
無限ホテルの理解についてはあってます。 この場合パラドックスという言葉使いがナイーブで、無限ってこんなに非常識だよ！って意味の”パラドックス”であって、数学の問題として「論理的推論の結果矛盾が生じる」の方のパラドックスとは違う意味合いです。
堀元マシーンと水野マシーンを入れ子構造にして動かしたら、外側のマシーンが内側に干渉して（茶々いれて）、本来の問題から脱線するから別の意味で停止性が保証できない
チューリングマシーンの場合と違うのは、
出力「ブラックボックスなのはお前だ」が無限ループを示唆する 有力な手がかりであること
24:30 「アルゴリズムがある問題ならば必ず解ける」と言われると水野さんの言う通りトートロジーに聞こえますが、ここで大切なのは「アルゴリズムがある問題ならば、"この論文の冒頭で定義したマシンは"必ず解ける」ということなのでしょうか？そう表現されるとトートロジーではないことを言っていると思います。
チューリングが示した有限個の種類の操作さえあれば、将来「このアルゴリズムを実行するにはこういう操作もできるように機能追加しないといけない」ということが絶対に起きないということなので。
水野さんの言う「だってチューリングマシンがやっていること自体がアルゴリズムなんだから」は論点先取なのでは？
どんなアルゴリズムも必ず実行できるために必要な操作を挙げろと言われたとき、チューリングが挙げた有限個の種類の操作で十分であるというのは「そりゃそうでしょ」というレベルの話ではないと思います。
おっしゃるとおり、トートロジーじゃないと思います
堀元さんが「ある問題にアルゴリズムがある ならば その問題はチューリングマシンで必ず解ける」と主張したところ、
水野さんはその逆の「ある問題がチューリングマシンで解ける ならば その問題にアルゴリズムがある」と誤解して、あたりまえじゃーんと反応したんですね
検索候補にカラメルも出てくるように何回も検索してみようかな。
チューリングマシンの説明聞いてラングトンのアリっぽいな、と思って調べたらまんまそれだった
「無限ホテル」に対応する物理現象は存在して、ABJ anomalyと呼ばれます。
これは中性パイオンが2つの光子に崩壊することに関係する、量子的な対称性の破れです。
簡単のためこれを空間1次元で考えると、まさに無限ホテルと同じことが起きていることがわかります。
無限に深い「ディラックの海」から粒子をギューッと数珠つなぎのように上に引きだしても、ディラックの海は依然として引き出す前と変わらず（ホテルは無限に埋まってるから）、これがABJ anomalyに重要です。
さらにこの破れはトポロジカルな性質をもち、数学的に非常に面白いです。
31:50
低姿勢問題のとこ地味に好き
24:45 彼の言っている、「アルゴリズムが存在する関数すべてはTurning Machineで解けるか」という命題はChurch-Turing Thesisで提唱されているものだと思う。実はこれはただの"Thesis"であって、"Theorem"ではないため、証明されたわけではない。今でもこの命題は証明されていないが、反例が無いというのも事実で、コンピュータサイエンティストの間では、（一般的には）このThesisは正しいものだと、意見が一致している。
たとえ話は誤解の嵐って急に韻を踏み始めておぉーってなっている
アルゴリズムがあってれば必ず正しい答えが導き出されるっていう証明をしてくれたチューリングは、心理的瑕疵に多大な影響を与えてる
無限ループを検出できないので苦肉の策がウォッチドッグタイマー
例えが合っているかわからないけど、行きたい目的地があって、そこまでのルートが示せるなら、どれだけ複雑であっても目的地まで辿り着くことができる。
しかし、目的地だけ示されて「ここに辿り着けますか？」という質問にはどうあがいても答えられないってことでいいのかな。
チューリングマシンにできないことを言及したのであって、別の概念で補完できる可能性がある
チューリングマシン、「だから何？」というものを生み出して重要性を説いたチューリングは私とは別の世界を見ているんだろうなぁ
完全にSFの話になってしまいますが、もし停止性問題が肯定的に解かれた、つまり「このアルゴリズムは将来どこかで停止するか？」という命題をチューリングマシンが判別できたとすると、別の数学未解決問題である「ゴールドバッハの予想」も解決できるんですよね。
まずあるアルゴリズムが停止するかどうか判別するチューリングマシンをHとします。
そして、ゴールドバッハの予想とは「4以上のすべての偶数は2つの素数の和で表せる」という主張です。
ここで、ある偶数が2つの素数で表せるか検証するアルゴリズムを作り、更にそれに4, 6, 8, ...と偶数を無限に入力していくアルゴリズムを作ります。
あとはこのアルゴリズムをHに入力して、停止すると評価されれば上記予想は否定的に解かれるし、停止しないと評価されれば肯定的に解かれる、つまりゴールドバッハの予想は正しかったということになります。
「タランチューニング」良いですね。授業中生徒に言いたい場面が割とあるんですが、言ったところでただの痛い数学教員という印象だけ残して終わりそうなので心の中でだけにしておきます。
チューリングのチューリングマシンについての論文とゲーデルの不完全性定理とヴィトゲンシュタインの論理哲学論考は、前提には差があるものの、基本的に同じことを表現してますよねえ
数学の論文で機械の話って凄いですね
ゆるコンピュータ科学ラジオのロゴの色はプリンの色だ。
訂正:ロゴ ×
アイコン ⚪︎
確かにループしてる手順で計算すれば勿論ループしてるからそれが計算不能であることは分かるけど、計算前にそれがループしているかはどうやっても分からないって直感的に正しそうって思っても証明するのはどうすれば良いか分からないな
というか実際に計算した時にその計算がループしているかを確認するプログラムすら作るのは難しそう
14:35 学生時代のメールアドレスをイジられた時の反論に使える大きいプリンの例え
デカルトじゃなくてパスカルが微分計算機「パスカリーヌ」を発明してた気がする
17:09
【このアルゴリズム】は停止しない
という出力が得られることは無い
チューリング「何でもはできないわ。できることだけ」
37:22 ナチュラルに中指を立ててしまう水野さん
33:09 今回のプリン
無限ホテルのパラドックスはよびのりさんがしっかり水野さんと同じ説明をしてた気がするので大丈夫だと思います。
6:34
オートマトンとチューリング機械が論理的に等価という話
有限オートマトンってチューリング機械よりも狭い範囲の問題しか解けないんじゃありませんでしたっけ？
言語学で想定されるオートマトンはもう少しリッチなのでしょうか…？
チューリングマシンを広義のオートマトンの一種とする流儀もあるので、オートマトンの定義による、という感じかなと
形式言語でも、チューリング機械はオートマトンよりも制限の緩い文法により生成される言語を受理した(つまり高機能だった)と思います
ググってみたんですがのんべえおじさんの言うとおり単にオートマトンというと有限／プッシュダウン／線形拘束オートマトンに加えてチューリング機械を含む機構を指すみたいですね
とすればそれはそれでより広い集合と等価であるというのもアレがアレな気もしますが...
@@nb-mr はい、細かく言うと、チョムスキー言語階層のタイプ０はチューリングマシンで半決定可能な言語のクラスなので、決定可能な言語のクラスより真に大きいです。まさに上２つでおっしゃっているとおりです
堀元さんはきっと、機構そのものは水野さんの見たことあるヤツだよと言いたかったのでしょうね。堀元さんがどのオートマトンとのどんな等価性を思い浮かべていたのかわかりませんが、変な表現になっちゃってる感じに思えますね
プリン、ラムダさんにも擦られてたの大層草なんだよな
どの動画かわかりますか？
@@mayaing475 Twitterにあります
動画化したかはわかりません
@@tenkawakiirobou ありがとうございます！
無限ホテルのパラドックスって可算無限のお話ですよね
オートマトンとチューリングマシンって受理できる言語のクラスが等価じゃなかったような...？(学部生の曖昧な理解)
チューリングマシンも広義のオートマトンの一種とする流儀もあるので、オートマトンの定義による、という感じかなと
@@ojisan0303 なるほど ありがとうございます
巨大数の世界に出てくる計算不可能関数、停止性の証明は不可能だが、出力結果は有限の値になるというヤバいやつを思い出した
じきにプリンのTシャツが販売されるな
・アルゴリズムがあるものはコンピュータで解ける
・「アルゴリズムがあるか判定する」アルゴリズムはない
と理解しました。アルゴリズム探しの旅は終わらないんだな
停止性問題は近年物理学にも応用されていて、最近ではShiraishi & Matsumotoの「量子多体系の熱化は非決定性問題である」という証明が話題になりました。
量子多体系を万能チューリングマシンにmapし、熱化するか否かを停止性問題に落とし込むことで、熱化が非決定的であることを証明しています。
しかしこれ、物理学界隈でもその結果をどう捉えていいかわからない、また誤って解釈している人がいる気がします（ちなみに私はわかってません）。
停止性問題も、分野外の人間には誤解の多い話なのだと思います。
物流業界なら積み合わせってありますね
チューリングマシンは、無限に長いテープを用意するんじゃなくて、用意したテープが仮に無限の長さでも扱うことができる…だと思ってたんで調べたんですけど、どっちなのか判断つかんかったです…
チューリングマシンは無限の長さのテープがあるマシンのことなので、前者が正しいです。
チューリングマシンの「テープが無限」は、チューリングマシン君が働く時にテープ切れを心配する必要がない、ということなので、用意したテープが無限である必要はありますね。「仮に無限でも扱うことができる」だと「有限より無限の方がチューリングマシン君は困る」みたいですが、実際には「無限より有限の方がチューリングマシン君は困る」ので、どっちかというと「仮に有限でも、テープがないところにチューリングマシンが移動しようとするたびに空白のテープをどんどんくっつけて追加するなら扱うことができる」の方が正しい…。
なんか今回話が散らかってたので、停止性問題だけで1回取り上げてもよかったかもしれませんね。
9:34 見方がよくわからないです。例えば状態1なら、今読んでいるところがスペースならそこに0をかきこんで上書きして右に移動して状態2に遷移する、って意味ですか？スペースじゃなかったらどう動くかもわかんないです。
その意味で合ってると思います
全部空白のテープを初期状態として与えることを前提にしているようなので、スペース以外の動作はどう定義してあっても構わないから省略されていると考えれば大丈夫そうです
カントの分析的判断と綜合的判断のちがいと同じなのか…違うのか…
ブラックボックスの下りはさすがに寒すぎるから、もう引きずらない方がいい…笑
「プリン」が「言語学ガチ勢」と同レベルの攻撃力を持ちました。
初恋はアルゴリズムがないのかもしれないけど、食パン咥えて走ればあるいは・・
イミテーションゲームを見てチューリングが作った機械にクリストファーと呼んでいてキリストを運ぶ者かーと思ったのと
これが彼の初恋なのかなと思った。
「アルゴリズム」を超える物が出てくることは絶対にないのだろうか。。。
以前、マリオメーカー(自分で作ったコースをマリオに遊ばせられるゲーム)で、簡易電卓作ってる方がいて、あれチューリングマシンだったのかな？と思いました
ニコニコに｢マリオメーカーはチューリング完全である｣というド真ん中の証明動画がありますよ！今回の動画とオーバーラップする部分も多いので是非
低姿勢問題噴いた
32:30 「クレタ人は（みな嘘つき)だ」の逆は「クレタ人は（みな嘘つき)ではない」になるから，実はパラドクスは成立していないというお話。
チョムスキー回の予告？回想？階層？
重箱の隅をつつくようだけどお茶女は身体が男子でも受かるで、時代やなぁ
おもしろ雑学
2017年にはマリオメーカー学会でマリオメーカーがチューリング完全であると発表。
あとマジックザギャザリングもチューリング完全。
無限に長い直線導線（マシな例）
オートマトンとチューリングマシンって等価だっけ？
35:14 「停まるかどうかは機械的に判断できない」
っていうのは、「プログラムAが停まったあとにプログラムAが停まったことをプログラムAが出力することが出来ない」って感じの解釈で合ってるんですかね？
人が死んだあとに「死にました」と言えないのとおんなじ感覚で
ちょっとややこしいのですが、
「答えがYesかNoのいずれかに決まっている問題（の入力x）に対してプログラムAを走らせたときに、プログラムAが必ず停止してYesかNoかを返す」か、
「問題に対してプログラムAを走らせたときに計算が終わらない」かのどちらが成立するかを、
「xとプログラムAの組を入力として使って正しく計算するプログラム」は存在しないって意味です（A自身が止まったことに気づかないとかの話ではないです）。
もっと端的にいうなら、「あるプログラムを走らせたときに、その計算が有限時間で終わるか終わらないか」を（別のプログラムの）計算で正しく答えることはできないって感じです（伝われ〜〜！）
志望大学に出願できることは教えてくれるけど、浪人無限ループに陥るかもしれないことは教えてくれないってことかぁ
エクセルにおいて、循環式を警告されるのは、別な話なのでしょうか？
無限ループが検出できない話は、どんなアルゴリズムのどんな種類の無限ループも確実正確に検出できる単一のアルゴリズムは存在しないという話なので
対象範囲を絞ったり確実性や正確性を犠牲にするなどすれば（例; エクセル計算式のこういう種類の循環参照だけ検出する)、検出できる場合もあるということだと思います
本質とは全然関係ないのですが、9:30 の水野さんの何気ない発言のおかげで、数学でよく使われる「点P」の"P"がなぜPなのか、その由来が分かった気がしてとてもスッキリしました
点はpointでは？
@@gamma9472 ご指摘ありがとうございます、調べてみたところPointが由来のようですね！
専門の人たちから間違って理解されているたとえ話を募集して全部駆逐しても良いかもしれないですね
例え話の誤解を駆逐する回、きっとサムネは進撃の巨人のパロディでしょうね
フォレスト・ガンプ・ミズノ
初恋の同級生は高校1年で脳腫瘍でおなくなりになった。
コンピュータには検出できない無限ループを人間が目で見て見つけることができるのは何故ですか...??
コンピュータも、特定のプログラムに対して停止するかどうか判定することは可能です。
ここで言っているのは、任意のプログラムに対して停止するかどうか判定するようなプログラムは存在しない、ということです。
これは人間にとっても結構難しい課題ではないでしょうか？
「おめでとうございます！ 元気な男の子です」
「なら女子大は無理か……」
嫌すぎる
出典: フリー百科事典『ウィキペディア（Wikipedia）』
特別 *積合せ* 貨物運送（とくべつ *つみあわせ* かもつうんそう）は自動車を用いた貨物運送の一形態で、地域ごとに仕分けを行う拠点を用意し、拠点間を結ぶ定期的な運送便に貨物を積み合わせて運送する方法。貨物自動車運送事業法の第2条6項に規定されており、単に特別積合せあるいは特積みと呼ぶことが多い。身近な例として宅配便が該当するが、料金体系などの差から宅配便を除外する（いわゆる路線便を指す）場合も多い。
チューリングルールの状態２と状態４は必要なの？素人目からみると、状態１と状態３の繰り返しで０・１交互に書くマシン成立しそうだが、、、
"ひとつ飛ばし"に書くために、状態1と状態3でそれぞれ空白を入れているのだと思います
33:30