Turing jump

英語（米国） (en-US) 英語（イギリス） (en-GB)

名詞

(computing theory) In computability theory, an operation that assigns to each decision problem X a successively harder decision problem X′ with the property that X′ is not decidable by an oracle machine with an oracle for X.

日本語の意味

計算可能性理論において、与えられた決定問題Xに対して、より難易度の高い決定問題X′を割り当てる操作。ここで、X′はXをオラクルとして利用するオラクルマシンでは決定できないという性質を持つ。

英語の意味

(computing theory) In computability theory, an operation that assigns to each decision problem X a successively harder decision problem X′ with the property that X′ is not decidable by an oracle machine with an oracle for X.

このボタンはなに？

During the seminar, the researcher used an example to show how the Turing jump assigns to a decision problem X a successor X′ that cannot be decided by any oracle machine given X as an oracle.

セミナーで研究者は、チューリングジャンプが各決定問題Xに対して、Xをオラクルとして持ついかなるオラクル機械でも決定できない後続の問題X′を割り当てる仕組みを例を使って示した。

詳細

意味（1）

(computing theory) In computability theory, an operation that assigns to each decision problem X a successively harder decision problem X′ with the property that X′ is not decidable by an oracle machine with an oracle for X.

Turing jumps （ plural ）