翻訳と辞書 Words near each other ・ 計算リソース ・ 計算不能(症) ・ 計算不能(症)、失(計)算(症) ・ 計算主義 ・ 計算力 ・ 計算力・思考力検定 ・ 計算化学 ・ 計算可能ドキュメント形式 ・ 計算可能函数 ・ 計算可能性 ・ 計算可能性理論 ・ 計算可能理論 ・ 計算可能関数 ・ 計算問題 ・ 計算器 ・ 計算図、図表、ノモグラム ・ 計算図表 ・ 計算尺 ・ 計算尺式露出計 ・ 計算平均生物 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 計算可能性理論 ： ウィキペディア日本語版 計算可能性理論[けいさんかのうせいりろん] 計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。 == はじめに == 計算機科学の中心的課題の1つは、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処することである。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし、多大な計算資源を与えられたとしても、見たところ単純な問題を解くことでコンピュータの能力の限界を明確に示すことは可能である。 計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか？」である。この質問はやや難解なので、もう少し判り易く例を挙げる。まず、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。同様に、全ての回文の集合や、文字 'a' だけからなる全ての文字列の集合などが形式言語の例である。これらの例では、それぞれの問題を解くコンピュータの構築の容易さが言語によって異なることは明白である。 しかし、この観測された明白な違いはどういう意味で正確なのか？ ある特定の問題をコンピュータで解く際の困難さの度合いを定式化し定義できるか？ その質問に答えるのが計算可能性理論の目標である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「計算可能性理論」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.