アルゴリズム及びテューリング機械
-
Abraxas_Aeon
- 2228
- 0
- 1
- 0
-
- いいね！0
エリザバス
@jutaityu
あれ？じゃ受験ときにやってたのかな・・・？RT @lebesmann ユークリッド互除法による解法知ってると大学入試の整数問題に強くなれる。
2010-02-21 22:05:32
アブラクサス・アイオーン
@Abraxas_Aeon
ちなみにさっきのを文字にして一般化するとこうなる。(a,b)(a>b)を整数とする。aをbで割った商をq、余りをrとすると、a＝bq＋r(0≦r＜b)と書くことができる。aとbの最大公約数を(a,b)と記せば、(a,b)＝(b,r)となる。
2010-02-21 22:20:26
アブラクサス・アイオーン
@Abraxas_Aeon
「aとbの最大公約数」を求める代わりに、「bと余りrの最大公約数」を求めれば解答になる、とこういうわけである。@lebesmannさんが仰るとおり、大学入試にはこれ知ってると強いだろうなぁ・・・。
2010-02-21 22:27:51
アブラクサス・アイオーン
@Abraxas_Aeon
ユークリッド互除法を使うと、(3984/5976)－(5667/13223)＋(310/3255)＝？のような問題も簡単になる。
2010-02-21 22:51:05
アブラクサス・アイオーン
@Abraxas_Aeon
解法：5976と3984の最大公約数→1992、13223と5667の最大公約数→1889、3255と310の最大公約数→155。よって、3984/5976＝2/3、5667/13223＝3/7、310/3255＝2/21→（2/3）－（3/7）＋（2/21）＝1/3となる。
2010-02-22 00:36:45
アブラクサス・アイオーン
@Abraxas_Aeon
アルゴリズムは数学のいたるところに見出される。古典的なアルゴリズムといえるユークリッドの互除法は夥しいアルゴリズム的手続きの一つに過ぎない。しかしアルゴリズムが古代から存在していたにも関らず、一般的なアルゴリズムの概念がまとめられたのは1930年代、20世紀に入ってからである。
2010-02-26 19:18:41
アブラクサス・アイオーン
@Abraxas_Aeon
1930年代になされたその中でも最も直接的で説得力があり、歴史的に見ても重要なのは、〈テューリング機械〉と呼ばれる概念を用いるものだ。このテューリング「機械」について考察する際には、それが「抽象的な機械」であって、物理的物体ではないということをよく踏まえておかなければならない。
2010-02-26 19:27:23
アブラクサス・アイオーン
@Abraxas_Aeon
テューリング機械はイギリスの数学者テューリングが1935-36年に、「決定問題」と呼ばれる非常に広範な問題に取り組むために導入した。「決定問題」は、ドイツの大数学者ヒルベルトが提起したものである（部分的には1900年パリ国際数学会議、より完全形では1928年ボローニャ国際会議）。
2010-02-26 19:35:37
アブラクサス・アイオーン
@Abraxas_Aeon
ヒルベルトは、数学的問題を解決するための一般的なアルゴリズム的手続きについて（すなわちこのような手続きが存在するか否かという問いの答えについて）問うた。彼は、一挙に制定されるはずの公理と推論規則を備えた、間然するところのない健全な基礎の上に数学を据えるという計画を立てた。
2010-02-26 20:29:05
アブラクサス・アイオーン
@Abraxas_Aeon
『ヒルベルト計画』の詳細については『不完全性定理』にまとめてあるのでそちらを参照して欲しい。→http://togetter.com/li/4370
2010-02-26 20:30:42
アブラクサス・アイオーン
@Abraxas_Aeon
既にその項目では書いたことであるが、『ヒルベルト計画』はゲーデルの証明した定理によって頓挫し、終止符を打たれた形になっている。テューリングがヒルベルトの研究に取り掛かったときには『ヒルベルト計画』はそれによって既に大打撃を被っていた。
2010-02-26 20:54:52
アブラクサス・アイオーン
@Abraxas_Aeon
テューリングが関心を抱いたヒルベルトの「決定問題」は公理系を用いた数学の、どの特定の定式化をも越えるものだった。その問題は「〈原理的に〉数学のある適当な仕方ではっきり定義された部類に属する全ての問題を一つずつ解決できる一般的な機械的手続きは∃か？」というものだった。
2010-02-27 01:34:20
アブラクサス・アイオーン
@Abraxas_Aeon
「機械的手続き」が何を意味するかを決定すること、これはこの問いの答えを困難なものにしていることの一つである。テューリングは「機械」の働きを要素的な項目に分解し、機械の概念がどのように定式化できるかを推測した。彼にとっては人間の脳も「彼の言う意味での「機械」」の一例である。
2010-02-27 01:54:20
アブラクサス・アイオーン
@Abraxas_Aeon
テューリングの考えにおいては、数学の問題に取り組んでいるときに人間の数学者が遂行している活動は何であっても「機械的手続き」の見出しの下にまとめられるべきだということになっている。では、この「機械的手続き」に関する彼の考えは、どのようなものだったのだろうか。
2010-02-27 01:59:36
アブラクサス・アイオーン
@Abraxas_Aeon
タチコマちゃんにテューリングマシン以下だね！とか言われないように次にはテューリングマシンの続きをやりたい。
2010-03-07 01:39:52