チューリング還元について

Words near each other

Dictionary Lists

mini英和辞書

mini和英辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

チューリング還元：ミニ英和和英辞書

チューリング還元[ちゅーりんぐかんげん]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

・ー： [ちょうおん]
　(n) long vowel mark (usually only used in katakana)
・還元： [かんげん]
　 1. (n,vs) resolution　2. reduction　3. return to origins　
・元： [げん, もと, がん]
　 1. (n,n-suf,n-t) (1) origin　2. basis　3. foundation　4. (2) former　

チューリング還元：ウィキペディア日本語版

チューリング還元[ちゅーりんぐかんげん]
チューリング還元（チューリングかんげん、）は、計算量理論における還元の一種である。アラン・チューリングの名がつけられた還元であり、問題 ''A'' が問題 ''B'' にチューリング還元されるとは、''B'' が容易に解けると仮定したときに ''A'' が容易に解けることを意味する（Rogers 1967、Soare 1987）。より厳密に言えば、''B'' を神託として備えた神託機械によって''A''が計算可能であることである。チューリング還元は決定問題にも関数問題にも適用できる。
''A'' から ''B'' へのチューリング還元が存在するとき、''B'' を解くあらゆるアルゴリズムは ''A'' を解くアルゴリズムを作成するのに使うことが可能である。これは、 ''A'' を計算する神託機械が ''B'' に関する神託を質問する箇所に ''B'' のアルゴリズムを挿入することで実現される。しかし、この神託機械は何回も神託を訊ねる可能性があり、''A'' のアルゴリズムは時間的にも空間的にも ''B'' のアルゴリズムよりも計算資源を多く必要とする可能性がある。
アラン・チューリング（1939年）は、神託機械を用いて相対計算可能性（当時は相対還元可能性と称していた）に初めて形式的な定義を与えた。1943年と1952年、スティーヴン・コール・クリーネは同様の概念を帰納的関数を用いて定義した。1944年、エミール・ポストはこの概念を表すのに初めて「チューリング還元可能性（Turing reducibility）」という用語を使った。
== 定義 ==
2つの集合

A,B \subseteq \mathbb

に対して、

A

が

B

にチューリング還元可能（Turing reducible）であるとは、''B'' に関する神託を与えられた神託機械を使って ''A''の特性関数を計算可能であることをいう。これを
:

A \leq_T B

と書く。
他にも、''A'' は ''B''-帰納的（B-recursive）または ''B''-計算可能（B-computable）であるともいう。
''B''のオラクルを持つ神託機械があり、''A'' を定義域とする部分関数を計算可能であるとき、''A'' を ''B''-帰納的可算（B-recursively enumerable）または ''B''-計算可枚挙（B-computably enumerable）であるという。
$A$ が $B$ にチューリング同値（Turing equivalent）であることを $A \equiv_T B$ で表し、 $A \leq_T B$ と $B \leq_T A$ が共に成り立つ。チューリング同値な集合の同値類をチューリング次数（Turing degree）と呼ぶ。集合 $X$ のチューリング次数を $\textbf(X)$ と記述する。
$\mathcal \subseteq \mathcal(\mathbb)$ という集合があるとき、全ての $X \in \mathcal$ について $X \leq_T A$ なら、集合 $A \subseteq \mathbb$ を $\mathcal$ に対してチューリング困難（Turing hard）であるという。加えて $A \in \mathcal$ であるとき、 $A$ を $\mathcal$ に対してチューリング完全（Turing complete）であるという。'B''-帰納的（B-recursive）または ''B''-計算可能（B-computable）であるともいう。
''B''のオラクルを持つ神託機械があり、''A'' を定義域とする部分関数を計算可能であるとき、''A'' を ''B''-帰納的可算（B-recursively enumerable）または ''B''-計算可枚挙（B-computably enumerable）であるという。
$A$ が $B$ にチューリング同値（Turing equivalent）であることを $A \equiv_T B$ で表し、 $A \leq_T B$ と $B \leq_T A$ が共に成り立つ。チューリング同値な集合の同値類をチューリング次数（Turing degree）と呼ぶ。集合 $X$ のチューリング次数を $\textbf(X)$ と記述する。
$\mathcal \subseteq \mathcal(\mathbb)$ という集合があるとき、全ての $X \in \mathcal$ について $X \leq_T A$ なら、集合 $A \subseteq \mathbb$ を $\mathcal$ に対してチューリング困難（Turing hard）であるという。加えて $A \in \mathcal$ であるとき、 $A$ を $\mathcal$ に対してチューリング完全（Turing complete）であるという。
チューリング完全（Turing complete）であるという。

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「チューリング還元」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.