Prev: Theorem 4.6. The class of box perfect graphs is in co-NP.
Next: [Port%d] \\.\HCD%d
From: cplxphil on 20 Oct 2009 18:08

Hi all,

I recently formulated the following paradox relating to oracles and
oracle machines. Comments on how to resolve it would be appreciated
(I am still puzzled).

Consider the class of all "describable languages." This is defined as
the set of all languages whose behavior can be described in logical or
set-theoretic terms, and includes all decidable languages and many
undecidable languages. For example, the set of instances of the
halting problem for which the answer is yes is a describable language.

Now consider an oracle set for all members of the class of describable
languages.

Finally, consider oracle TMs that can have access to any oracle from
the oracle set described immediately above. The paradoxical question
is: Can these oracle TMs decide the halting problem for their own
class? In other words, if we alter the model of computation so that
now TMs can solve any describable language with an oracle, is the
halting problem for this new computation model solvable using TMs
within that model?

We can prove that they cannot, using Turing's standard proof that any
model of computation is incapable of solving its own halting problem.
And yet, at the same time, because the notion of describability is
itself formally describable, we have that this version of the halting
problem is describable. Thus, we can surely decide the halting
problem for these oracle TMs by simply querying an oracle for the
problem!

What is the resolution to this?

For those curious, the inspiration for this paradox is the
philosophical paradox, "If God is all-powerful, can God create a stone
so large that not even he can lift it?" I tried to adapt it to, "If
an oracle is so powerful that it can decide any describable language,
can it give rise to a describable decision problem that it cannot
decide?"

Thanks for any comments and/or solutions!

-Phil
From: Robert Israel on 20 Oct 2009 18:45
cplxphil <cplxphil(a)gmail.com> writes:

>
> Hi all,
>
> I recently formulated the following paradox relating to oracles and
> oracle machines. Comments on how to resolve it would be appreciated
> (I am still puzzled).
>
> Consider the class of all "describable languages." This is defined as
> the set of all languages whose behavior can be described in logical or
> set-theoretic terms, and includes all decidable languages and many
> undecidable languages. For example, the set of instances of the
> halting problem for which the answer is yes is a describable language.

Can you clarify what "described" means?

> Now consider an oracle set for all members of the class of describable
> languages.
>
> Finally, consider oracle TMs that can have access to any oracle from
> the oracle set described immediately above. The paradoxical question
> is: Can these oracle TMs decide the halting problem for their own
> class? In other words, if we alter the model of computation so that
> now TMs can solve any describable language with an oracle, is the
> halting problem for this new computation model solvable using TMs
> within that model?
>
> We can prove that they cannot, using Turing's standard proof that any
> model of computation is incapable of solving its own halting problem.
> And yet, at the same time, because the notion of describability is
> itself formally describable, we have that this version of the halting
> problem is describable. Thus, we can surely decide the halting
> problem for these oracle TMs by simply querying an oracle for the
> problem!
>
> What is the resolution to this?

How is the notion of describability formally describable?

> For those curious, the inspiration for this paradox is the
> philosophical paradox, "If God is all-powerful, can God create a stone
> so large that not even he can lift it?" I tried to adapt it to, "If
> an oracle is so powerful that it can decide any describable language,
> can it give rise to a describable decision problem that it cannot
> decide?"

Presumably the resolution is that either the oracle or the problem can't exist.
--
Robert Israel israel(a)math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
From: cplxphil on 20 Oct 2009 20:16
On Oct 20, 6:45 pm, Robert Israel
<isr...(a)math.MyUniversitysInitials.ca> wrote:
> cplxphil <cplxp...(a)gmail.com> writes:
>
> > Hi all,
>
> > I recently formulated the following paradox relating to oracles and
> > oracle machines.  Comments on how to resolve it would be appreciated
> > (I am still puzzled).
>
> > Consider the class of all "describable languages."  This is defined as
> > the set of all languages whose behavior can be described in logical or
> > set-theoretic terms, and includes all decidable languages and many
> > undecidable languages.  For example, the set of instances of the
> > halting problem for which the answer is yes is a describable language.
>
> Can you clarify what "described" means?  
>
>
>
>
>
> > Now consider an oracle set for all members of the class of describable
> > languages.
>
> > Finally, consider oracle TMs that can have access to any oracle from
> > the oracle set described immediately above.  The paradoxical question
> > is:  Can these oracle TMs decide the halting problem for their own
> > class?  In other words, if we alter the model of computation so that
> > now TMs can solve any describable language with an oracle, is the
> > halting problem for this new computation model solvable using TMs
> > within that model?
>
> > We can prove that they cannot, using Turing's standard proof that any
> > model of computation is incapable of solving its own halting problem.
> > And yet, at the same time, because the notion of describability is
> > itself formally describable, we have that this version of the halting
> > problem is describable.  Thus, we can surely decide the halting
> > problem for these oracle TMs by simply querying an oracle for the
> > problem!
>
> > What is the resolution to this?
>
> How is the notion of describability formally describable?
>
> > For those curious, the inspiration for this paradox is the
> > philosophical paradox, "If God is all-powerful, can God create a stone
> > so large that not even he can lift it?"  I tried to adapt it to, "If
> > an oracle is so powerful that it can decide any describable language,
> > can it give rise to a describable decision problem that it cannot
> > decide?"
>
> Presumably the resolution is that either the oracle or the problem can't exist.
> --
> Robert Israel              isr...(a)math.MyUniversitysInitials.ca
> Department of Mathematics        http://www.math.ubc.ca/~israel
> University of British Columbia            Vancouver, BC, Canada

Thanks for the reply. Admittedly, I was doing a bit of hand-waving
there. Let me try to be a little bit more precise...

When I say that a language is "describable," the intuitive meaning of
what I am saying is that the language can be defined by a human being
in mathematical terms...perhaps "definable" would be a better term?

I am struggling a little bit to come up with a formal definition...but
below is a tentative one (I reserve the right to alter it later if it
ends up not serving its purpose well and I can think of a better one
that does).

Without loss of generality, assume a binary alphabet for languages.
Any logical sentence in Peano arithmetic (or perhaps ZFC would be
better? I'm very weak in formal logic, so I'm not sure which would be
better suited) that can be defined with a free variable x constitutes
the "definition" of a language. A language defined by a sentence
corresponds to the set containing every natural number x (expressed as
a binary string) that satisfies the sentence.

So, for example, we could specify a sentence that holds true iff the
free variable x is accepted by a particular Turing machine. In this
manner, we can specify/define/describe every decidable language.
Additionally, we can describe/define the halting problem, by
expressing a sentence that holds true only when x is a number that
can, when operated on in a particular way, yield a TM M and an input i
such that <M,i> halts in a finite number of steps n. The basic idea
is that we are "logically" defining a language, rather than being
forced to give a TM that accepts it.

As far as describability being describable...if you were to formalize
the above definition of describability, you could come up with a
sentence that holds true for x only when x is a valid sentence that
itself describes a language. I believe that it's as simple as
checking to make sure that the sentence in question that you claim is
describing a language is well-formed.

I think you are right that the resolution must be one of the two
options that you mentioned; I just don't know how to come to terms
with either solution in a logical fashion. Perhaps there are limits
on what sorts of problems can be solved with an oracle? For some
reason that I can't quite understand, I have a weird hunch that this
has something to do with Russell's paradox.

Do you have any other thoughts, or does anyone else?

Thanks,
Phil
From: tchow on 20 Oct 2009 21:49
In article <37bc267f-e7f8-4af3-8db1-739f48186dd8(a)r31g2000vbi.googlegroups.com>,
cplxphil <cplxphil(a)gmail.com> wrote:
>When I say that a language is "describable," the intuitive meaning of
>what I am saying is that the language can be defined by a human being
>in mathematical terms...perhaps "definable" would be a better term?

Without going through your argument in detail, I suspect that you are
rediscovering Richard's paradox (Google it). Most likely, if you write
down a fully precise definition of "describable" your paradox will evaporate.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Tim Little on 20 Oct 2009 21:58
On 2009-10-21, cplxphil <cplxphil(a)gmail.com> wrote:
> A language defined by a sentence corresponds to the set containing
> every natural number x (expressed as a binary string) that satisfies
> the sentence.

What exactly do you mean by "satisfies", in the case that the sentence
is undecidable? For example in ZFC, suppose the sentence with free
natural-number variable x is "aleph_(x+1) = 2^(aleph_x)" (related to
the Continuum Hypothesis).


- Tim
 |  Next  |  Last
Pages: 1 2
Prev: Theorem 4.6. The class of box perfect graphs is in co-NP.
Next: [Port%d] \\.\HCD%d