Property |
Value |
dbo:abstract
|
- 計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である(チューリングマシンの停止問題が決定不能であるため)。すなわち、PR は構文的クラスであり、R は意味論的クラスである。 一方、任意の帰納的可算集合(REも参照)を原始再帰関数を次のように使って枚挙可能である。入力 (M, k) を与えたとき(M はチューリングマシン、k は整数)、M が k ステップ以内に停止するなら M を出力するものとする。そうでない場合は何も出力しない。すると (M, k) の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する M の集合に他ならない。 (ja)
- 計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である(チューリングマシンの停止問題が決定不能であるため)。すなわち、PR は構文的クラスであり、R は意味論的クラスである。 一方、任意の帰納的可算集合(REも参照)を原始再帰関数を次のように使って枚挙可能である。入力 (M, k) を与えたとき(M はチューリングマシン、k は整数)、M が k ステップ以内に停止するなら M を出力するものとする。そうでない場合は何も出力しない。すると (M, k) の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する M の集合に他ならない。 (ja)
|
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 782 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-ja:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- 計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である(チューリングマシンの停止問題が決定不能であるため)。すなわち、PR は構文的クラスであり、R は意味論的クラスである。 一方、任意の帰納的可算集合(REも参照)を原始再帰関数を次のように使って枚挙可能である。入力 (M, k) を与えたとき(M はチューリングマシン、k は整数)、M が k ステップ以内に停止するなら M を出力するものとする。そうでない場合は何も出力しない。すると (M, k) の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する M の集合に他ならない。 (ja)
- 計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である(チューリングマシンの停止問題が決定不能であるため)。すなわち、PR は構文的クラスであり、R は意味論的クラスである。 一方、任意の帰納的可算集合(REも参照)を原始再帰関数を次のように使って枚挙可能である。入力 (M, k) を与えたとき(M はチューリングマシン、k は整数)、M が k ステップ以内に停止するなら M を出力するものとする。そうでない場合は何も出力しない。すると (M, k) の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する M の集合に他ならない。 (ja)
|
rdfs:label
|
- PR (計算複雑性理論) (ja)
- PR (計算複雑性理論) (ja)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageDisambiguates
of | |
is dbo:wikiPageWikiLink
of | |
is owl:sameAs
of | |
is foaf:primaryTopic
of | |