A new reducibility between the recursive sets is defined,which is appropriate to be used in the study of the polynomial reducibility and the NP-problem.
It will be proved that given any noncappable r.e. degree a there are r.e.degrees a 0 and a 1 such that a 0,a 1a and [a 0∪a 1] is not local distributive,i.e.,there is an r.e.degree c such that [c][a 0∪a 1] and for an...It will be proved that given any noncappable r.e. degree a there are r.e.degrees a 0 and a 1 such that a 0,a 1a and [a 0∪a 1] is not local distributive,i.e.,there is an r.e.degree c such that [c][a 0∪a 1] and for any [u i][a i] and i=0,1,[c]≠[u 0]∨[u 1] where R/M is the quotient of the recursively enumerable degrees modulo the cappable degrees. Therefore, R/M is not distributive.展开更多
Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing ma...Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-＊ composition for some t-norm＊ （or NFTM＊, for short）, nondeterministic fuzzy Turing machine （or NFTM）, deterministic fuzzy Turing machine （or DFTM）, and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Turing machines are obtained. First, it is shown that NFTM＊, NFTM, and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm＊ does not satisfy finite generated condition, but are equivalent in the approximation sense. That is to say, we can approximate an NFTM＊ by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary r.e. languages and recursive languages. Second, we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM＊ on it with a given accuracy.展开更多
Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n>1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Low...Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n>1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Lowm r.e. degrees are not elementarily equivalent for n > m > 1.展开更多
In the study of cappable and noncappable properties of the recursively enumerable (r.e.) degrees, Lempp suggested a conjecture which asserts that for all r.e. degrees a and b, if a ≮ b then there exists an r.e. degr...In the study of cappable and noncappable properties of the recursively enumerable (r.e.) degrees, Lempp suggested a conjecture which asserts that for all r.e. degrees a and b, if a ≮ b then there exists an r.e. degree c such that c ≮ a and c ≮ b and c is cappable. We shall prove in this paper that this conjecture holds under the condition that a is high. Working below a high r.e. degree h, we show that for any r.e. degree b with h ≮ b, there exist r.e. degrees aO and al such that a0, al ≮ b, aO,a1 ≮ h, and aO and a1 form a minimal pair.展开更多
Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a] ≤[c]and [a] V [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that giv...Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a] ≤[c]and [a] V [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that given any nonzero [ c ] ∈ R/M, there are [ a ], [ d ]∈ R/M such that [d]<[a]≤[c] and[a] is locally noncuppable between [ c ] and[d].展开更多
基金Research partially supported by the Youth NSF grant of China.
文摘A new reducibility between the recursive sets is defined,which is appropriate to be used in the study of the polynomial reducibility and the NP-problem.
文摘It will be proved that given any noncappable r.e. degree a there are r.e.degrees a 0 and a 1 such that a 0,a 1a and [a 0∪a 1] is not local distributive,i.e.,there is an r.e.degree c such that [c][a 0∪a 1] and for any [u i][a i] and i=0,1,[c]≠[u 0]∨[u 1] where R/M is the quotient of the recursively enumerable degrees modulo the cappable degrees. Therefore, R/M is not distributive.
基金the National Natural Science Foundation of China (Grant No.10571112)"TRAPOYT" of China and the National 973 Foundation Research Program (Grant No.2002CB312200)
文摘Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-＊ composition for some t-norm＊ （or NFTM＊, for short）, nondeterministic fuzzy Turing machine （or NFTM）, deterministic fuzzy Turing machine （or DFTM）, and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Turing machines are obtained. First, it is shown that NFTM＊, NFTM, and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm＊ does not satisfy finite generated condition, but are equivalent in the approximation sense. That is to say, we can approximate an NFTM＊ by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary r.e. languages and recursive languages. Second, we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM＊ on it with a given accuracy.
文摘Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n>1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Lowm r.e. degrees are not elementarily equivalent for n > m > 1.
基金This reserch is supported by the National Natural Science Foundation of China (No.19971090).
文摘In the study of cappable and noncappable properties of the recursively enumerable (r.e.) degrees, Lempp suggested a conjecture which asserts that for all r.e. degrees a and b, if a ≮ b then there exists an r.e. degree c such that c ≮ a and c ≮ b and c is cappable. We shall prove in this paper that this conjecture holds under the condition that a is high. Working below a high r.e. degree h, we show that for any r.e. degree b with h ≮ b, there exist r.e. degrees aO and al such that a0, al ≮ b, aO,a1 ≮ h, and aO and a1 form a minimal pair.
基金This work was partially supported by the National Natural Science Foundation of China (Grant No. 19971090).
文摘Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a] ≤[c]and [a] V [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that given any nonzero [ c ] ∈ R/M, there are [ a ], [ d ]∈ R/M such that [d]<[a]≤[c] and[a] is locally noncuppable between [ c ] and[d].
