株式会社極東書店トップ ＞ 商品一覧 ＞ Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees.
商品詳細
Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees.
・ISBN 978-1-4704-4162-3 paper US$ 85.00
￥19,915.- (税込) ※（※）価格はご注文時の参考価格となります。
納品価格につきましては書籍の入荷時点で確定となります。
版元の原価改定、外国為替の変動等により異なる場合がございますので、予めご了承下さい。
お気に入り
★★★
| 著者・編者 | Downey, Rodney G. / Ng, Keng Meng / Solomon, Reed, |
|---|---|
| シリーズ | Memoirs of the American Mathematical Society |
| 出版社 | (American Mathematical Society, US) |
| 出版年月 | 2021 |
| ページ数 | 90 pp. |
| 言語 | ENG |
| ニュース番号 | ＜M25-13295＞ |
解説
Two of the central concepts for the study of degree structures in computability theory are computably enumerable degrees and minimal degrees. For strong notions of reducibility, such as $m$-deducibility or truth table reducibility, it is possible for computably enumerable degrees to be minimal. For weaker notions of reducibility, such as weak truth table reducibility or Turing reducibility, it is not possible to combine these properties in a single degree.
This book considers how minimal weak truth table degrees interact with computably enumerable Turing degrees and obtain three main results. First, there are sets with minimal weak truth table degree which bound noncomputable computably enumerable sets under Turing reducibility. Second, no set with computable enumerable Turing degree can have minimal weak truth table degree. Third, no $\Delta^0_2$ set which Turing bounds a promptly simple set can have minimal weak truth table degree.
This book considers how minimal weak truth table degrees interact with computably enumerable Turing degrees and obtain three main results. First, there are sets with minimal weak truth table degree which bound noncomputable computably enumerable sets under Turing reducibility. Second, no set with computable enumerable Turing degree can have minimal weak truth table degree. Third, no $\Delta^0_2$ set which Turing bounds a promptly simple set can have minimal weak truth table degree.