5 ms·

It's unfortunate there is no an equality decision procedure. If two numbers are equal you will see that the difference is zero no matter how much precision you

It's unfortunate there is no an equality decision procedure. If two numbers are equal you will see that the difference is zero no matter how much precision you request, but of you always see zero difference you will never know if the numbers are equal or you just have to keep searching. I know that such a decision procedure exists for algebraic number (i.e., you can allow roots of any orders and general polynomial root extraction), but I don't know about transcendental functions like exponential and logarithm. And frankly it smells a lot of undecidability. Computational things tend to become undecidable just a little bit after they become interesting, and sometimes even before.

Rerarom 4y ago
Yeah equality of computable reals is undecidable (basically the halting of a Turing machine can be encoded as a computable real being nonzero).
chriswarbo 4y ago
This technique can't be applied to equality, since equality "collapses" the entire decimal expansion down to a single bit: we can't make closer and closer approximations, since that first bit requires an infinite amount of work. In fact, talking about "Nth decimals" also requires an infinite amount of work. For example, what's the first digit of '0.99999... + 0.00000...'? Note that this is not the same as 'rounded to one significant digit'. Let's call the numbers x and y; there are a few possibilities: - If y = 0, then the sum is equal to x: - If x eventually has a non-9 digit, then the first digit is 0; e.g. if the third digit is a 3, then the result is 0.993... - If x repeats 9 forever, the first digit can be either 1 or 0, depending on taste - If y > 0, then the result depends on the relative magnitudes of y and (1 - x). The first digit could be 0 (if y < 1 - x), or 1 (if y > 1 - x). If these differences only occur after billions of decimal places, we must go that far through the calculation to determine whether the first digit is 0 or 1! Most computable real representations will actually calculate to within some epsilon, e.g. a power of 10 if we're rounding the final decimal when displaying the result. That ensures all of these problems disappear, but of course it introduces uncertainty. We can likewise ask whether two numbers are equal to some precision; but not necessarily in general. (There might be tricks/identities for the particular functions being used in this calculator; but the above applies to "computable reals" in the strictest sense; i.e. where each function is a Universal Turing Machine)
- zozbot234 4y ago
  > In fact, talking about "Nth decimals" also requires an infinite amount of work. This is known as the Table-maker's dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker%27s_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker%27s_dilem... The article is about rounding, but the exact same logic applies to other common ways of choosing "exact" approximations.
tyilo 4y ago
It is undecidable, see https://en.wikipedia.org/wiki/Richardson%27s_theorem https://en.wikipedia.org/wiki/Richardson%27s_theorem
- fdej 4y ago
  No, this is wrong. Richardson's theorem is about functions, not constants. Equality of constants constructed from exponentials and logarithms is decidable (assuming Schanuel's conjecture) by another theorem (and algorithm!) of Richardson.
orlp 4y ago
I would just like to note that this is a moot point, as the computable reals are a subset of the reals, thus by extension equality of the reals is also undecidable. This fact is always given as an argument against computable analysis, while completely ignoring the reals suffer from the exact same issue. It bothers me greatly that the mathematical objects we generally refer to as "numbers" have no constructive basis. I really wish the reals were phased out as the default "number" object as a mathematical curiosity (like the surreals are), and that the default interpretation of "number" is replaced by a computational foundation. The idea of an "non-computable number" seems completely silly to me, as the fundamental property for something to be called a number, to me, is the ability to do arithmetic with it. If I can't add with it, multiply by it, or even know its digits, why are we calling it a number (e.g. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant)? Note that I have no problems with undecidability in general, I am well familiar with it and the above does not stem from ignorance. I am not rejecting the reals as a mathematical concept entirely, not at all. They are perfectly valid mathematical objects to study. I simply reject the current definition we have for a "number" as the correct mathematical object for the job.
- jostylr 4y ago
  If you have not heard of Norm Wildberger, you may enjoy some of what he has delved into. Here is one video in which he explains some of his difficulties with current mathematics: https://cosmolearning.org/video-lectures/difficulties-with-real-numbers-infinite-decimals-i/ https://cosmolearning.org/video-lectures/difficulties-with-r... He dislikes the idea of presenting infinity as a complete thing. And that one objection leads to a lot of different new directions to pursue. His rational trigonometry does trigonometry entirely without transcendental functions. It can involve square roots at times, but it is kept to a minimum. Everything else is entirely rational based. He has several videos that delve into the problems of each of the standard formulations of real numbers. He also argues for a more practical and computational version of the Fundamental Theorem of Algebra. An interesting demonstration of the difficulty of real number arithmetic, relevant to some other comments here, is multiplying 1/9 by itself. For fractions, it is trivial as it is 1/81 and this can be converted into a repeating decimal, of course. But try multiplying the decimal form of 1/9 by itself. It is all 1's in the multiplication so it should be easy, right? If you write it down, essentially, the n+1th place is generated by summing n 1s. That is, it is .0123456789(10)(11)(12).... where I put in parentheses the sum of that columns digits. So one has to carry and as it goes further out, one is carrying over many digits; when out a trillion places, we are carrying across 12 places, which is larger than the repeating pattern. Just carrying that first 10 leads to .01234567900(11)(12)... And .012345679 is the basic pattern of 1/81 but it is hard to see feeling confident about that if one only had the infinite decimal to work with. The point is that something with a non-repeating pattern such as computing sqrt(2)pie seems difficult enough that it verges on the vacuous. He does point out the difference for his criticism applying to Pure Mathematics rather than Applied Mathematics. Approximations are fine for applications and what Wildberger is really saying is he wants a Pure Mathematics that really supports that explicitly by focusing on rational numbers as much as possible. For example, he introduces differential calculus with polynomials by considering transforming p(x) to q(x) = p(x+r), collecting powers of x, and then translating back to p(x) = q(x-r) which is just replacing x with x-r. If expanded out, all the r's cancel, but if one leaves them and then truncates the different powers, one gets the different polynomial approximations. While neat in avoiding limts, the real nice thing is applying this technique to algebriac curves. For example, we can view the unit circle as the solution to 0= p(x,y) = x^2 + y^2 - 1. We can do the same trick above computing p(x+r, y+s), expand, and then retranslate and truncate. This can give us the approximations to the unit circle at a given point on the circle. This sidesteps having to compute the derivative of the square root function to get the tangent lines to the unit circle. An example of an alternate work flow is multiplying two complex numbers on the unit circle. The traditional approach is to say "compute the angles and then add the angles". But the computing of the angles is impossibly hard to do in a precise fashion (approximate is fine, of course). But there is a perfectly fine accurate procedure. Take the points z and w on the unit circle and draw a line through them. Draw a parallel line through 1. The line will intersect the circle at z*w. As a quick example of this, if you multiply a+bi and -a+bi, this becomes -a^2 -b^2 = -1. Geometrically, the line through these two points is horizontal and the horizontal line through 1 intersects at -1. You can see that with angles, but it feels less intuitive to me that that is how it will work out. Even the set of Natural Numbers being called infinite is something he questions. He used the term "unending" which I like as well. And by understanding that "most" natural numbers cannot be represented in this universe (assuming it is a finite universe), then it leads to questions such as what numbers can be represented? We have islands of simplicity such as 10^10^10^10^10^10^10 + 23. How dense are they in the larger numbers? Can we do anything useful with those islands? These questions are less prompted when we simply think of the natural numbers as this one big set of sameness. But if we demand that being able to do the computations is actually an important requirement, then we can investigate many more interesting ideas. And Wildberger's point is that this should be in the domain of Pure Mathematics with it being taught to future mathematicians instead of it being relegated to Applied Mathematics.
zozbot234 4y ago
Even without complete decidability, a good CAS implementation can give you "yes/no/not sure" answers that are more than "good enough" for practical use.
fdej 4y ago
There is an algorithm by Richardson to prove equality of real and complex numbers composed from exponentials and logarithms. (It doesn't have a complete proof of correctness, but it never returns a wrong result: it will loop forever iff it encounters a counterexample to Schanuel's conjecture.) It can also be extended to higher transcendental functions, but it gets harder to guarantee termination. I have a library for exact reals/complexes with an incomplete implementation of Richardson's algorithm: https://fredrikj.net/calcium/ https://fredrikj.net/calcium/

Rerarom 4y ago

Yeah equality of computable reals is undecidable (basically the halting of a Turing machine can be encoded as a computable real being nonzero).

chriswarbo 4y ago

This technique can't be applied to equality, since equality "collapses" the entire decimal expansion down to a single bit: we can't make closer and closer approximations, since that first bit requires an infinite amount of work. In fact, talking about "Nth decimals" also requires an infinite amount of work. For example, what's the first digit of '0.99999... + 0.00000...'? Note that this is not the same as 'rounded to one significant digit'. Let's call the numbers x and y; there are a few possibilities: - If y = 0, then the sum is equal to x: - If x eventually has a non-9 digit, then the first digit is 0; e.g. if the third digit is a 3, then the result is 0.993... - If x repeats 9 forever, the first digit can be either 1 or 0, depending on taste - If y > 0, then the result depends on the relative magnitudes of y and (1 - x). The first digit could be 0 (if y < 1 - x), or 1 (if y > 1 - x). If these differences only occur after billions of decimal places, we must go that far through the calculation to determine whether the first digit is 0 or 1! Most computable real representations will actually calculate to within some epsilon, e.g. a power of 10 if we're rounding the final decimal when displaying the result. That ensures all of these problems disappear, but of course it introduces uncertainty. We can likewise ask whether two numbers are equal to some precision; but not necessarily in general. (There might be tricks/identities for the particular functions being used in this calculator; but the above applies to "computable reals" in the strictest sense; i.e. where each function is a Universal Turing Machine)

zozbot234 4y ago
> In fact, talking about "Nth decimals" also requires an infinite amount of work. This is known as the Table-maker's dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker%27s_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker%27s_dilem... The article is about rounding, but the exact same logic applies to other common ways of choosing "exact" approximations.

tyilo 4y ago

It is undecidable, see https://en.wikipedia.org/wiki/Richardson%27s_theorem https://en.wikipedia.org/wiki/Richardson%27s_theorem

fdej 4y ago
No, this is wrong. Richardson's theorem is about functions, not constants. Equality of constants constructed from exponentials and logarithms is decidable (assuming Schanuel's conjecture) by another theorem (and algorithm!) of Richardson.

orlp 4y ago

I would just like to note that this is a moot point, as the computable reals are a subset of the reals, thus by extension equality of the reals is also undecidable. This fact is always given as an argument against computable analysis, while completely ignoring the reals suffer from the exact same issue. It bothers me greatly that the mathematical objects we generally refer to as "numbers" have no constructive basis. I really wish the reals were phased out as the default "number" object as a mathematical curiosity (like the surreals are), and that the default interpretation of "number" is replaced by a computational foundation. The idea of an "non-computable number" seems completely silly to me, as the fundamental property for something to be called a number, to me, is the ability to do arithmetic with it. If I can't add with it, multiply by it, or even know its digits, why are we calling it a number (e.g. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant)? Note that I have no problems with undecidability in general, I am well familiar with it and the above does not stem from ignorance. I am not rejecting the reals as a mathematical concept entirely, not at all. They are perfectly valid mathematical objects to study. I simply reject the current definition we have for a "number" as the correct mathematical object for the job.

jostylr 4y ago
If you have not heard of Norm Wildberger, you may enjoy some of what he has delved into. Here is one video in which he explains some of his difficulties with current mathematics: https://cosmolearning.org/video-lectures/difficulties-with-real-numbers-infinite-decimals-i/ https://cosmolearning.org/video-lectures/difficulties-with-r... He dislikes the idea of presenting infinity as a complete thing. And that one objection leads to a lot of different new directions to pursue. His rational trigonometry does trigonometry entirely without transcendental functions. It can involve square roots at times, but it is kept to a minimum. Everything else is entirely rational based. He has several videos that delve into the problems of each of the standard formulations of real numbers. He also argues for a more practical and computational version of the Fundamental Theorem of Algebra. An interesting demonstration of the difficulty of real number arithmetic, relevant to some other comments here, is multiplying 1/9 by itself. For fractions, it is trivial as it is 1/81 and this can be converted into a repeating decimal, of course. But try multiplying the decimal form of 1/9 by itself. It is all 1's in the multiplication so it should be easy, right? If you write it down, essentially, the n+1th place is generated by summing n 1s. That is, it is .0123456789(10)(11)(12).... where I put in parentheses the sum of that columns digits. So one has to carry and as it goes further out, one is carrying over many digits; when out a trillion places, we are carrying across 12 places, which is larger than the repeating pattern. Just carrying that first 10 leads to .01234567900(11)(12)... And .012345679 is the basic pattern of 1/81 but it is hard to see feeling confident about that if one only had the infinite decimal to work with. The point is that something with a non-repeating pattern such as computing sqrt(2)pie seems difficult enough that it verges on the vacuous. He does point out the difference for his criticism applying to Pure Mathematics rather than Applied Mathematics. Approximations are fine for applications and what Wildberger is really saying is he wants a Pure Mathematics that really supports that explicitly by focusing on rational numbers as much as possible. For example, he introduces differential calculus with polynomials by considering transforming p(x) to q(x) = p(x+r), collecting powers of x, and then translating back to p(x) = q(x-r) which is just replacing x with x-r. If expanded out, all the r's cancel, but if one leaves them and then truncates the different powers, one gets the different polynomial approximations. While neat in avoiding limts, the real nice thing is applying this technique to algebriac curves. For example, we can view the unit circle as the solution to 0= p(x,y) = x^2 + y^2 - 1. We can do the same trick above computing p(x+r, y+s), expand, and then retranslate and truncate. This can give us the approximations to the unit circle at a given point on the circle. This sidesteps having to compute the derivative of the square root function to get the tangent lines to the unit circle. An example of an alternate work flow is multiplying two complex numbers on the unit circle. The traditional approach is to say "compute the angles and then add the angles". But the computing of the angles is impossibly hard to do in a precise fashion (approximate is fine, of course). But there is a perfectly fine accurate procedure. Take the points z and w on the unit circle and draw a line through them. Draw a parallel line through 1. The line will intersect the circle at z*w. As a quick example of this, if you multiply a+bi and -a+bi, this becomes -a^2 -b^2 = -1. Geometrically, the line through these two points is horizontal and the horizontal line through 1 intersects at -1. You can see that with angles, but it feels less intuitive to me that that is how it will work out. Even the set of Natural Numbers being called infinite is something he questions. He used the term "unending" which I like as well. And by understanding that "most" natural numbers cannot be represented in this universe (assuming it is a finite universe), then it leads to questions such as what numbers can be represented? We have islands of simplicity such as 10^10^10^10^10^10^10 + 23. How dense are they in the larger numbers? Can we do anything useful with those islands? These questions are less prompted when we simply think of the natural numbers as this one big set of sameness. But if we demand that being able to do the computations is actually an important requirement, then we can investigate many more interesting ideas. And Wildberger's point is that this should be in the domain of Pure Mathematics with it being taught to future mathematicians instead of it being relegated to Applied Mathematics.

zozbot234 4y ago

Even without complete decidability, a good CAS implementation can give you "yes/no/not sure" answers that are more than "good enough" for practical use.

fdej 4y ago

There is an algorithm by Richardson to prove equality of real and complex numbers composed from exponentials and logarithms. (It doesn't have a complete proof of correctness, but it never returns a wrong result: it will loop forever iff it encounters a counterexample to Schanuel's conjecture.) It can also be extended to higher transcendental functions, but it gets harder to guarantee termination. I have a library for exact reals/complexes with an incomplete implementation of Richardson's algorithm: https://fredrikj.net/calcium/ https://fredrikj.net/calcium/