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

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

【目次】

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

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

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

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

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

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

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

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

【参考文献】

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

https://amzn.to/3G0Zzje

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

https://amzn.to/3zNBs5t

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

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

https://amzn.to/3BJHi9m

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

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

https://amzn.to/3BLQIkF

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

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

https://amzn.to/3Q3piv6

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

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

https://yurugengo.com/support 

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

https://www.youtube.com/channel/UCmpkIzF3xFzhPez7gXOyhVg

【おたよりフォーム】

https://forms.gle/BLEZpLcdEPmoZTH4A

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

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

yurugengo@gmail.com

【堀元見プロフィール】

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

Twitter→https://twitter.com/kenhori2note

マガジン→https://note.com/kenhori2/m/m125fc4524aca 

個人YouTube→https://www.youtube.com/channel/UCYJ335HO_qLZDr7TywpI0Gg

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

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