Fixed point properties of oracle Turing machines
- From: Joachim Selke <mail@xxxxxxxxxxxxxxxx>
- Date: Thu, 13 Jul 2006 20:12:29 +0200
Hello,
while writing my master's thesis (about the notion of autoreducibility
from recursion theory) I came across the following problem.
As you know, Turing machines might be seen as "algorithmic descriptions"
of sets (of natural numbers). Every Turing machine completely describes
the set of input numbers on that it halts. Therefore every
semi-decidable set has an "algorithmic description" by a Turing machine.
I had the idea to consider oracle Turing machines. Every such machine M
can be interpreted as a operator M : P(N) -> P(N), where P(N) denotes
the class of all sets of natural numbers. If M is an oracle Turing
machine and A is a set of natural numbers then M(A) is defined to be the
set of all input numbers on that M halts when using oracle A.
Again, a set A can be "algorithmically described" if there is an oracle
Turing machine operator M having the *unique* fixed point A. Formally,
we have M(A) = A and M(B) != B for every set B != A. Then M might be
seen as a finite encoding of A.
I was not able to find anything in the literature about this definition
of sets by fixed points of oracle machines. But I think there must be
some work on this because it's a quite simple idea.
Do you know some papers that cover this topic?
Thank you!
Joachim
.
- Prev by Date: Re: Can the humanity fix the universe bug?
- Next by Date: Re: Two-dimensional pattern matching/compression
- Previous by thread: List of hard Problems with Transitions from underconstrained to overconstrained
- Next by thread: SQL query plan question
- Index(es):
Relevant Pages
|
Loading
