PR_(計算複雑性理論)

ウィキペディア

PR (計算複雑性理論)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/13 14:48 UTC 版)

計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。

原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。

PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である（チューリングマシンの停止問題が決定不能であるため）。すなわち、PR は構文的クラスであり、R は意味論的クラスである。

一方、任意の帰納的可算集合（REも参照）を原始再帰関数を次のように使って枚挙可能である。入力 (M, k) を与えたとき（M はチューリングマシン、k は整数）、M が k ステップ以内に停止するなら M を出力するものとする。そうでない場合は何も出力しない。すると (M, k) の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する M の集合に他ならない。

関連項目

• 原始再帰関数

Weblio日本語例文用例辞書

「PR (計算複雑性理論)」の例文・使い方・用例・文例

• 貴方は、駅前でPR紙を配り、お店の宣伝をして下さい。
• キャシーはABCモーターズからPRマネージャーとして正式雇用するというオファーレターを受け取った。
• 益回りは株式収益率（PRR）の逆数である。
• 中野印刷有限会社の営業一課のPR担当の石川と申します。
• 必要に応じて（医師が処方を書く際に、PRNを使う）
• EPROMという,コンピューターの記憶装置
• PROLOGという,プログラミング言語
• ヒット曲｢PRIDE｣を歌う予定だ。
• 隠し砦(とりで)の三悪人　THE LAST PRINCESS
• そのため，日本鰻輸入組合は台湾産ウナギをPRしている。
• ―日本の田舎町を世界にPRするカナダ人
• 現在，田辺市の魅力を世界にPRするために尽力している。
• 同庁は，外国人観光客の旅行先として日本をPRすると同時に，他の省庁と観光事業関連の政策や規定を調整していく。
• 2006年から，魚卸業者らが10月10日を｢魚の日｣としてPRしており，魚の消費を促すイベントが魚市場や鮮魚店で開催されてきた。
• ｢きな子電車｣で映画をPR
• 武将たちはまた，名古屋の観光をPRするために他の都市でもパフォーマンスを行っている。
• 島民たちは「我々の島の魅力をPRするには，島の風景と調和したアート作品が必要だ。」と考えた。
• 熊本県をPRするキャンペーンで2010年３月にデビューした。
• 蒲島知事は，「くまモンは熊本県をPRするのに大変役立っている。」と語った。