チューリング第3弾です。今回は「チューリングの論文は無限に長いテープを準備するところから始まった」「まだこの世にないコンピュータの限界を示した」「無限ループを検出することは原理的に不可能」など、チューリングの主要な功績である「決定問題」の論文についてゆるく解説しました。

【目次】

00:00 「ブラックボックスはお前だ」と言い合う闇の回は仕方なかった

01:28 チューリングの論文は「無限に長い機械」から始まる

05:36 チューリングマシンあるある「だから何？」

12:59 この機械は以前に出てきた「アレ」と同じ

18:49 論文のスゴさは「コンピュータの限界」を示したこと

28:10 「アルゴリズムで書けない」って何？

31:41 「ブラックボックスはお前だ」と停止性問題

39:24 次回テーマは「チューリングの功績の原体験」

【参考文献】

○『エニグマアラン・チューリング伝（上）』

○『エニグマアラン・チューリング伝（下）』

https://amzn.to/3zNBs5t

→この世で一番詳しいチューリングの伝記。上下巻で1000ページぐらいある。どうしてもチューリングについて詳しく知りたければこちらを。

○『暗号解読（上・下）』

→世界一おもしろいサイエンスライター（私見）であるサイモン・シンが書いた、超エキサイティングな暗号の歴史と仕組みの本。歴史ドラマは熱いし、仕組み解説は好奇心をくすぐられます。最高。

○『チューリングの計算理論入門』

→安定のブルーバックス。チューリングマシンについてざっくり理解したいならオススメ。なんとなく雰囲気が分かります。

○『チューリングを読むコンピュータサイエンスの金字塔を楽しもう』

→チューリングの論文を全文引用しながら丁寧に読解する本。難しいがおもしろい。この手の骨太本には珍しく、うんちく力が高い。前提知識の説明でうんちくメモを取りまくった。

【サポーターコミュニティ加入はこちらから】

【親チャンネル：ゆる言語学ラジオ】

【おたよりフォーム】

※皆様からの楽しいおたよりをお待ちしています！

【お仕事依頼はこちら！】

【堀元見プロフィール】

慶應義塾大学理工学部卒。専門は情報工学。WEBにコンテンツを作り散らかすことで生計を立てている。現在の主な収入源は「アカデミックに人の悪口を書くnote有料マガジン」。

【水野太貴プロフィール】

名古屋大学文学部卒。専門は言語学。某大手出版社で編集者として勤務。言語学の知識が本業に活きてるかと思いきや、そうでもない。

コンピュータの限界は「テープを読み書きする機械」で分かる。チューリングマシンはすごい【チューリング3】#34

ゆるコンピュータ科学ラジオ