3
$\begingroup$

This wikipedia article

http://en.m.wikipedia.org/wiki/Computable_number#Properties

suggests that there is such a bijection. How does it look like? And how to map computable transcedentals like pi to a rational?

$\endgroup$
  • 1
    $\begingroup$ Computable number->a subset of Turing machine->a subset of string describing Turing machine->natural number->rationals. $\endgroup$ – Gina Jul 16 '14 at 23:56
  • 1
    $\begingroup$ How would a bijection between $\Bbb N$ and $\Bbb Q$ would look like? $\endgroup$ – Asaf Karagila Jul 17 '14 at 0:00
  • $\begingroup$ A bijection between Q and N comes from the ability to form a bijection between N x N and N. You can read more about it here. $\endgroup$ – beanshadow Jul 17 '14 at 0:40
  • $\begingroup$ @beanshadow: I wasn't asking for myself. I was asking in order to provoke some thought in the OP's mind, after all such a bijection must disregard any structure both sets have, and so the case is somewhat similar to this situation and the question of how to map $\pi$ into the rationals. $\endgroup$ – Asaf Karagila Jul 17 '14 at 13:14
  • $\begingroup$ Pi is computable only in the sense that there exists an algorithm for producing successive rational approximations of pi that monotonically improve (converge on pi). The algorithm never actually computes pi. From another perspective, the algorithm does not halt if asked to compute pi. An algorithm that doesn't halt isn't successfully computing anything: a computation has to terminate and produce a result. $\endgroup$ – Kaz Jun 3 '15 at 18:26
2
$\begingroup$

The only construction I know is really a brute-force sort of thing: I'm pretty sure anything that can be proved to be such a bijection cannot be computable.

Every computable real number has at least one program that computes it.

Every program can be expressed as a pattern of bits.

Every pattern of bits corresponds to a natural number.

Thus, there exists an injective function that maps computable real numbers to natural numbers.

The numbers in the image can be listed in order, which amounts to putting them in bijection with the set of all natural numbers.

There is a bijection between the set of all natural numbers with the set of rational numbers.

Thus, combining everything together shows the existence of a bijective map from computable reals

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Opps, nevermind. I think I made a mistake somewhere. $\endgroup$ – Gina Jul 17 '14 at 0:13
  • $\begingroup$ So, in the end you are saying that the mapping is given by the actual representation of the turing machine that computes it. In other words pi is nothing else but say the representation in integers of the underlaying program computing its digits. Is it really so? And as most of us know there could be lots of programs that compute pi with arbitrary precision. How to pick THE ONE? $\endgroup$ – cristian Jul 17 '14 at 0:26
  • $\begingroup$ @cristian: I didn't say "pi is nothing else but...", I said "there is a program that computes pi". Don't confuse the map with the territory! How to pick a particular program from the many choices? Any way you like! And invoke the axiom of choice to assert that you can choose for all computable reals. Or if you don't want to do that, pick the one that would give you the smallest natural number after you do that conversion. $\endgroup$ – user14972 Jul 17 '14 at 0:33
  • $\begingroup$ Thanks a lot every one. Things are more clear now. What took me by surprise in that article is that they are saying "rationals". I know that card(N) == card(Q) but since there is a bijection with the natural numbers what is the point mentioning rationals?... $\endgroup$ – cristian Jul 17 '14 at 0:41
  • $\begingroup$ @cristian: Tradition, probably. People like to compare the sizes of the reals and rationals and irrationals and algebraics and such, so whoever wrote the article probably thought "rationals" before any other alternative. And to some extent, the sizes of dense subsets of the reals are probably more interesting to think about. $\endgroup$ – user14972 Jul 17 '14 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.