Skip to main content
added 39 characters in body
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Once we look at computational content, rather than constructive content, things are easier to answer. When we work on the level of individual reals, all the representations are equivalent - a real is computable in one sense if and only if it is computable in the others. However, some of the conversions are not uniform (i.e. there is not usually an algorithm that can convert arbitrary reals from one representation to another). This lack of uniformity also presents issues in a constructive context.

A very thorough treatment of the uniformity issue was given by Jeffry L. Hirst, "Representations of reals in reverse mathematics", Bulletin of the Polish Academy of Sciences, Mathematics 55 (2007), 303–316 (PDF, eudml). Hirst summarized the known relationships and verified several relationships that had not been treated in the literature.

Here is a table from the paper. It shows the subsystem of second-order arithmetic necessary to (provably) convert a sequence of reals of one form to a sequence of reals of a second form. The use of sequences is a stand-in for uniformity, and has close connections to constructive analysis.

table of relationships between kinds of reals

The representations are:

  • $\rho$: rapidly converging Cauchy sequence
  • $\delta$: decimal expansion
  • $\lambda$: Dedekind cut
  • $\sigma$: open Dedekind cut

I suspect that similar kinds of results are in the literature on Weihrauch-style computable analysis, but I don't have a particular reference.

Once we look at computational content, rather than constructive content, things are easier to answer. When we work on the level of individual reals, all the representations are equivalent - a real is computable in one sense if and only if it is computable in the others. However, some of the conversions are not uniform (i.e. there is not usually an algorithm that can convert arbitrary reals from one representation to another). This lack of uniformity also presents issues in a constructive context.

A very thorough treatment of the uniformity issue was given by Jeffry L. Hirst, "Representations of reals in reverse mathematics", Bulletin of the Polish Academy of Sciences, Mathematics 55 (2007), 303–316 (PDF). Hirst summarized the known relationships and verified several relationships that had not been treated in the literature.

Here is a table from the paper. It shows the subsystem of second-order arithmetic necessary to (provably) convert a sequence of reals of one form to a sequence of reals of a second form. The use of sequences is a stand-in for uniformity, and has close connections to constructive analysis.

table of relationships between kinds of reals

The representations are:

  • $\rho$: rapidly converging Cauchy sequence
  • $\delta$: decimal expansion
  • $\lambda$: Dedekind cut
  • $\sigma$: open Dedekind cut

I suspect that similar kinds of results are in the literature on Weihrauch-style computable analysis, but I don't have a particular reference.

Once we look at computational content, rather than constructive content, things are easier to answer. When we work on the level of individual reals, all the representations are equivalent - a real is computable in one sense if and only if it is computable in the others. However, some of the conversions are not uniform (i.e. there is not usually an algorithm that can convert arbitrary reals from one representation to another). This lack of uniformity also presents issues in a constructive context.

A very thorough treatment of the uniformity issue was given by Jeffry L. Hirst, "Representations of reals in reverse mathematics", Bulletin of the Polish Academy of Sciences, Mathematics 55 (2007), 303–316 (PDF, eudml). Hirst summarized the known relationships and verified several relationships that had not been treated in the literature.

Here is a table from the paper. It shows the subsystem of second-order arithmetic necessary to (provably) convert a sequence of reals of one form to a sequence of reals of a second form. The use of sequences is a stand-in for uniformity, and has close connections to constructive analysis.

table of relationships between kinds of reals

The representations are:

  • $\rho$: rapidly converging Cauchy sequence
  • $\delta$: decimal expansion
  • $\lambda$: Dedekind cut
  • $\sigma$: open Dedekind cut

I suspect that similar kinds of results are in the literature on Weihrauch-style computable analysis, but I don't have a particular reference.

Source Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

Once we look at computational content, rather than constructive content, things are easier to answer. When we work on the level of individual reals, all the representations are equivalent - a real is computable in one sense if and only if it is computable in the others. However, some of the conversions are not uniform (i.e. there is not usually an algorithm that can convert arbitrary reals from one representation to another). This lack of uniformity also presents issues in a constructive context.

A very thorough treatment of the uniformity issue was given by Jeffry L. Hirst, "Representations of reals in reverse mathematics", Bulletin of the Polish Academy of Sciences, Mathematics 55 (2007), 303–316 (PDF). Hirst summarized the known relationships and verified several relationships that had not been treated in the literature.

Here is a table from the paper. It shows the subsystem of second-order arithmetic necessary to (provably) convert a sequence of reals of one form to a sequence of reals of a second form. The use of sequences is a stand-in for uniformity, and has close connections to constructive analysis.

table of relationships between kinds of reals

The representations are:

  • $\rho$: rapidly converging Cauchy sequence
  • $\delta$: decimal expansion
  • $\lambda$: Dedekind cut
  • $\sigma$: open Dedekind cut

I suspect that similar kinds of results are in the literature on Weihrauch-style computable analysis, but I don't have a particular reference.