Relation between the Usual Order and the Enumeration Orders of Elements of r.e. Sets

Details Relation between the Usual Order and the Enumeration Orders of Elements of r.e. Sets Relation between the Usual Order and the Enumeration Orders of Elements of r.e. Sets

2009-04-23

arxiv.org/abs/0904.3607v1

Computer Science

Formal Languages and Automata Theory

15 pages; submitted to Mathematical Logic Quarterly

Scientific paper

In this paper, we have compared r.e. sets based on their enumeration orders with Turing machines. Accordingly, we have defined novel concept uniformity for Turing machines and r.e. sets and have studied some relationships between uniformity and both one-reducibility and Turing reducibility. Furthermore, we have defined type-2 uniformity concept and studied r.e. sets and Turing machines based on this concept. In the end, we have introduced a new structure called Turing Output Binary Search Tree that helps us lighten some ideas.

Affiliated with

Also associated with

No associations

Rating

Relation between the Usual Order and the Enumeration Orders of Elements of r.e. Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Relation between the Usual Order and the Enumeration Orders of Elements of r.e. Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relation between the Usual Order and the Enumeration Orders of Elements of r.e. Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-408759