チューリング完全とは

チューリング完全という概念があり、プログラミングの常識の大前提になるものですが、あまり理解はされず、意識もされていません。少し言語化してみます。

Transcript

1. チューリング完全とは
2. チューリング完全 ある計算のメカニズムが万能チュー リングマシンと同じ計算能力をもつこ と。 •出典：Wikipedia
3. 完全チューリングマシン 1936年にアラン・チューリングが提示した計算機械。 現在のノイマン型コンピュータとは別設計。 あるプログラムが無限ループするかどうかを判定するプログラムが書けないことが数 学的に証明されたことで有名。
4. コンピューターの歴史 最初のコンピューターが稼 働したのは1946年
5. 何のために考案されたのか 数学の重要な問 題を解くため
6. 計算可能とは？ 同じ計算可能性を持つ • 帰納的関数 • ラムダ計算 • チューリングマシン • ノイマン型コンピュータ • 他いろいろ
7. ゲーデルの不完全性定理 • 初等的な自然数論を含むω無矛盾な公理的理論{¥displaystyle T}Tは不完全で ある，つまりそこで証明も反証もされない命題（決定不能命題(undecidable proposition)，あるいは独立命題）が存在する 第一不完全性定理 • 初等的な自然数論を含む理論{¥displaystyle T}Tが無矛盾ならば，{¥displaystyle T}Tの無矛盾性を表す命題 Con({¥displaystyle T}T) がその体系で証明できない 第二不完全性定理
8. 停止性問題とは 自然数論と同等の計算可能性 を持つ万能チューリンググマシ ンでの、不完全性定理の別解
9. 計算可能とは？ 同じ計算可能性を持つ • 帰納的関数 • ラムダ計算 • チューリングマシン • ノイマン型コンピュータ • 他いろいろ
10. 計算可能性が考慮しないこと 以下は考慮しない • 入力 • 出力 • 計算時間 • メモリ量など • 可読性 • 開発エコシステム
11. 計算可能性が同じであることは数学的に証明される • 言語2でできることはすべて言語1で書き換えられることが証明さ れている。 言語1 • 言語1でできることがすべて言語２で書き換えられることが証明さ れている。 言語2
12. 数学的証明の例 C言語 C言語から whileだけ 使えなくし たプログラ ム言語 whileをすべてif とgotoで書き換 えれば、すべて のプログラムは 書ける whileを使わなけ ればよい
13. チューリング完全 ある計算のメカニズムが万能チュー リングマシンと同じ計算能力をもつこ と。 •出典：Wikipedia
14. チャーチ・チューリングのテーゼ •「計算できる関数」という直観的な概念を、 帰納的関数と呼ばれる数論的関数のク ラスと同一視しようという主張である。 チャーチ・チューリングのテーゼ
15. チューリング完全なもの 自然数論 ラムダ演算 万能チューリン グマシン ほとんどのプロ グラミング言語 C Java SQL アセンブ リ言語 他 ほかいろいろ C++テン プレート X86の mov命令 HTML + CSS 解析機関
16. C++テンプレートはチューリング完全 こんなことが可能なライ ブラリが実装可能である ことが証明されている •コンパイル時に演算 •実行時の計算量は0 #include <fstream> using namespace std; int main() { // 中心(10,10,10)で半径5の球、 // 頂点(20,20,20)を持ち一辺10を持つ立方体を、 // レイトレーシングした画像を出力する。 ofstream("image.jpg") << Calculate< Sphere<10, 10, 10, 5>, Cube<20, 20, 20, 10>>::DATA; }
17. 最新のSQLはチューリング完全 PL/SQLとかじゃなくてSQLのみの話 レイトレーシングでも物理演算でもなんでも可能 人間に書けるとは言ってない 実行時間やメモリ量が現実的で済むとも言ってない
18. 意味 あるプログラミング言語で計算 できることは、他のプログラミン グ言語でも必ず計算できる。
19. ただし 以下は考慮しない • 入力 • 出力 • 計算時間 • メモリ量など • 可読性 • 開発エコシステム