6 found
  1.  81
    Recursive in a Generic Real.Juichi Shinoda & Theodore A. Slaman - 2000 - Journal of Symbolic Logic 65 (1):164-172.
    There is a comeager set C contained in the set of 1-generic reals and a first order structure M such that for any real number X, there is an element of C which is recursive in X if and only if there is a presentation of M which is recursive in X.
    Direct download (9 more)  
    Export citation  
    Bookmark   1 citation  
  2.  20
    A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs.Asae Mochizuki & Juichi Shinoda - 1996 - Annals of the Japan Association for Philosophy of Science 9 (1):17-21.
  3.  5
    Preface.Juichi Shinoda & Tosiyuki Tugué - 1991 - Annals of Pure and Applied Logic 52 (1-2):1.
  4.  8
    Inhomogeneity of the P-s-Degrees of Recursive Functions.Asae Mochizuki & Juichi Shinoda - 2000 - Mathematical Logic Quarterly 46 (3):385-392.
    The structure of the p-s-degrees of recursive functions is shown to be inhomogeneous. There are two p-s-degrees a and b above 0 such that [0, a] is distributive and [0, b] is nondistributive. Moreover, we will investigate how the number of values of each function reflects on its degree.
    Direct download (4 more)  
    Export citation  
  5.  10
    On MODkP Counting Degrees.Masamitsu Ozaki & Juichi Shinoda - 1999 - Mathematical Logic Quarterly 45 (3):327-342.
    For a prime k, the embeddability of finite lattices are discussed for various kind of the MODkP degrees of recursive sets. In particular, all finite lattices are embeddable into the MODkP Turing degrees, whereas the non distributive lattice M3 is embeddable into the MOD2P many-one degrees but N5 is not.
    Direct download (3 more)  
    Export citation  
  6.  13
    Strong Polynomial-Time Reducibility.Juichi Shinoda - 1997 - Annals of Pure and Applied Logic 84 (1):97-117.
    The degree structure of functions induced by a polynomial-time reducibility first introduced in G. Miller's work on the complexity of prime factorization is investigated. Several basic results are established including the facts that the degrees restricted to the sets do not form an upper semilattice and there is a minimal degree, as well as density for the low degrees, a weak form of the exact pair theorem, the existence of minimal pairs and the decidability of the Π2 theory of the (...)
    Direct download (4 more)  
    Export citation