|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 計 ： [けい] 1. (n,n-suf) plan ・ 計算 ： [けいさん] 1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast ・ 可 ： [か] 1. (n,n-suf) passable ・ 可能 ： [かのう] 1. (adj-na,n) possible 2. practicable 3. feasible ・ 可能性 ： [かのうせい] 【名詞】 1. potentiality 2. likelihood 3. possibility 4. availability ・ 能 ： [よく, のう] 1. (adv,n,vs) being skilled in 2. nicely 3. properly 4. well 5. skillfully 6. thoroughly
計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。 == はじめに == 計算機科学の中心的課題の1つは、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処することである。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし、多大な計算資源を与えられたとしても、見たところ単純な問題を解くことでコンピュータの能力の限界を明確に示すことは可能である。 計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか？」である。この質問はやや難解なので、もう少し判り易く例を挙げる。まず、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。同様に、全ての回文の集合や、文字 'a' だけからなる全ての文字列の集合などが形式言語の例である。これらの例では、それぞれの問題を解くコンピュータの構築の容易さが言語によって異なることは明白である。 しかし、この観測された明白な違いはどういう意味で正確なのか？ ある特定の問題をコンピュータで解く際の困難さの度合いを定式化し定義できるか？ その質問に答えるのが計算可能性理論の目標である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「計算可能性理論」の詳細全文を読む スポンサード リンク
|