Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive sets and recursive numbers: relationship?

  1. May 2, 2015 #1
    Given the two standard definitions
    (1) A computable set is a set for which there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set.
    (2) A computable number is a number which can be approximated to any degree of accuracy by a computable function
    I am tempted to say that a computable number is one that corresponds to a computable set, but
    (a) I am not sure this is correct, and
    (b) even if it is correct, I am not sure what "corresponds to" would mean. There are ways to make any subset of the natural numbers correspond to a real number, but I am not sure whether these would be appropriate.
    Thanks.
     
  2. jcsd
  3. May 3, 2015 #2
    It would make sense that a computable number belongs in a computable set. I would agree.
     
  4. May 3, 2015 #3
    Thanks, +Jace90+, but that's not quite right. A computer number does not necessarily belong in a computable set -- that is, it doesn't have to be a member of a computable set. A computable set is a set of natural numbers, whereas a computable number need not be a natural number. For example, pi is computable, but is not in a computable set. The idea is that each computable set of natural numbers corresponds to a single computable real number. {1,3,5} might correspond to 0.010101 or something like that.Since both the set of the computable numbers and the set of the computable sets are countable, there exists a 1-1 correspondence, but would this correspondence correspond to a section of an explicit one-to-one correspondence between ℝ and P(ℕ) that was not simply set up artificially in order to work backwards? This was the intent of my question; sorry for not making it clearer the first time.
     
  5. May 4, 2015 #4

    Svein

    User Avatar
    Science Advisor

    Check out "Gödel, Escher, Bach" for a long discussion of FLoop vs. BLoop.
     
  6. May 4, 2015 #5
    Thanks, Svein. I read the book a long time ago (in fact, I have met Hofstadter, and I know well the official translator of GEB to Russian): it's very good, and the Floop (primitive recursive functions) and Bloop (recursive functions) programs are a nice way to make his point that Gloop (a program to solve the halting problem) is impossible, but I am afraid that I do not see that this answers my question. Could you be more explicit?
     
  7. May 4, 2015 #6

    Svein

    User Avatar
    Science Advisor

    Sorry, I just thought I should point you in that direction. Since you already have read it, I don't have anything else to add (my thesis was in function algebras, not in mathematical logic).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Recursive sets and recursive numbers: relationship?
  1. Transfinite recursion (Replies: 5)

Loading...