recursively enumerabe sets

markvs_at_gmail.com
Date: 03/20/05 

Date: 19 Mar 2005 19:15:01 -0500

Let X be a recursively enumerable set of all positive values of a
polynomial f:Z^n-->Z with integer coefficients. For every y in X define
its cost as the minimal ||x|| such that f(x)=y. We say that a real
number r is good if for every y in X

y<r implies cost(y)<r.

Question: Is there a recursively enumerable but non-recursive set such
that the set of good numbers contains arbitrary long intervals?

If the set X is defined using a Turing machine T (instead of a
polynomial), one can define the cost similarly as the length of the
computation accepting y. Then one can ask the same question.

I have a feeling that the answer is "yes", and it should be known. So I
would appreciate any references. Clearly, the set of good numbers
cannot be recursively enumerable because otherwise X would be
recursive.

Mark Sapir

Relevant Pages

  • Re: Health and money purrs needed
    ... I have a feeling that when I fell, since I was airborne for a second and my right hand was the first part of my body to hit the cement, that I did more than just fracture and partially shatter my wrist bone. ... My new insurance only pays for preventative treatment up to a $1,500 deductible per year and then after that still only pays a portion of your cost. ... Some purrs for both my health and my pocket book would be greatly appreciated. ...
    (rec.pets.cats.anecdotes)
  • Re: SQL question
    ... I have a feeling that these statements will gonna take a lot of system resources. ... Remember as well that the total "cost" of having that process isn't just the performance cost of the application, but also the cost of maintaining it. ... I find that programs containing well written SQL, by compressing the file joining and selection logic into something that I find to be vastly more intuitively easy to understand than high-level language statements, ultimately are a lot faster to maintain. ...
    (comp.sys.ibm.as400.misc)
  • Re: OT - College Station, Texas - ??
    ... around "cost of living comparison" sites. ... show the cost of living in College Station if LESS than here in ... As I do more research into Bryan/College Station I'm feeling better ...
    (alt.support.stop-smoking)
  • Re: I got a embarassing feeling when I see Federer...
    ... Anyone else with that feeling? ... I guess that's the cost of knowing you're ... streets ahead of everyone else. ...
    (rec.sport.tennis)
  • Re: Autopsy pictures of my Sprint
    ... >> Any idea on the cost of a fresh motor? ... > Sadly more than it's worth. ... I had that feeling myself. ...
    (rec.motorcycles)
Quantcast