5 ms·

In case someone is wondering about your wording. A computable number is one whose decimal approximation can be computed to arbitrary precision with a finite, t

by skh 8y ago

In case someone is wondering about your wording. A computable number is one whose decimal approximation can be computed to arbitrary precision with a finite, terminating algorithm. All algebraic numbers and some transcendental numbers are computable. Thus being irrational does not imply not being computable. One more pedantic note. There are algebraic formulas for solving polynomials of higher degree than 4. For instance, you can find a formula to solve x^n = 0 for n a positive integer. You can’t find a general, algebraic formula to solve polynomial equations of degree n where n > 4.

malmsteen 8y ago
Is there "not computable" numbers ? Example ?
- wetmore 8y ago
  There are "more" non-computable numbers than computable one. Chaitlin's constant is an example.
- skh 8y ago
  I can give you many more examples of specific computable numbers than I can of noncomputable numbers. This is a bit surprising when one learns that the set of noncomputable numbers is much larger than computable ones. Most of the numbers you’ve dealt with are computable. Every noncomoutable is close to a computable number where close means as close as you want. There is also the notion of definable numbers which is different than computable. There are people who study these things and the implications they have in mathematics and computer science. I’m not one of these people so beyond what I’ve said I don’t dare comment.
- lacker 8y ago
  In math, infinite sets have different sizes. The number of computer programs is "countably infinite". The number of real numbers is "uncountably infinite". Since there are more numbers than computer programs, some numbers must be uncomputable. for more info see: https://en.wikipedia.org/wiki/Countable_set https://en.wikipedia.org/wiki/Countable_set
  - DoctorOetker 8y ago
    Let's consider the plattitude that math appears in printed books, and books contain characters, and the character set or symbol alphabet is finite, and books are finite. Hence the set of all possible books on mathematics is countable. Then how is there a difference between books and programs? Now consider the following program or function: f_epsilon(x) (return x + epsilon;) where epsilon is a number from a set S. Then if the set S is considered countable for pragmatic reasons like representing epsilon in the form of bits etc then everyone agrees it is countable in practice. I.e. aren't there uncountably many functions f(x) above if we allow epsilon to be drawn from an uncountable set?
    - lacker 8y ago
      I agree that the set of all math books is countable, and I agree that there are uncountably many f_epsilon functions if epsilon comes from an uncountable set. However, f(x) = x + epsilon is not a computable function when epsilon is not a computable number. So not all of the f_epsilon family of functions is computable.
    - Dylan16807 8y ago
      There is no important difference between books and functions. Let me present a challenge to you: Pick a uniformly random number between 1 and 2. Now tell me what it is. No 'coincidences', like getting exactly 1.34 or the square root of three. It has to be properly random. The odds are 100% that you picked a 'normal' number that goes on forever with no pattern. A number that cannot be specified in finite space. In other words, a number that can't be computed.
      - DoctorOetker 8y ago
        I fully agree with you. We can also consider a similar function f_epsilon(x) that returns the sum of x and a uniformly random number between 1 and 2 chosen at compile time, but constant at run time. I agree it can't be specified in finite space. The dichotomy is the computational model, from a utilitarian perspective we consider every conceptual computer to be a huge but finite finite-state-machine. One could abstractly (and less down-to-earth usefully) define/conceive of a computer that can store arbitrary variables representing uncountable objects (like real numbers etc)
- rntz 8y ago
  The Halting Number. The i'th digit after the decimal point of the Halting Number is 0 if the i'th Turing Machine halts given an empty tape, and 1 otherwise. (The integral part of the Halting Number is 0.) This number is not computable; if it were, you could solve the halting problem.
- gnulinux 8y ago
  Construct a real number by gluing BB(i) where BB is the busy beaver function.
- betterunix2 8y ago
  Yes. First, fix a programming language; for example, C. Now, the halting problem asks for a given C program and a given stdin, will the program terminate. For simplicity, let's just say that we close stdin and give the program an empty input. It turns out no algorithm can solve the halting problem for all C programs. The explanation is that, if you had such an algorithm, you could write a C program that applies the algorithm to itself (this is a special quine), and then does the opposite of whatever the halting algorithm says the program would do (if it says the program halts, the program will just enter an infinite loop; if it says it does not halt, the program calls exit). Now, imagine a list of all valid C programs in alphabetical order, beginning with the empty string (which, oddly enough, is a valid C program). Consider a number where the Nth digit after the decimal point is 0 if the Nth C program halts, and 1 if it does not; for example, the first digit, corresponding to the empty string, is 0, while a few digits later, the digit corresponding to "int main() {main(); return 0;}" will be 1. Putting it all together, we know there are C programs for which we cannot compute the solution to the halting problem, and we have a number whose digits are determined by the solution to the halting problem for every C program. So that number is not computable (because we cannot compute every digit, so we cannot compute it to arbitrary precision).
throwawaymath 8y ago
These are good points. To expand a bit for even further nomenclature: > All algebraic numbers and some transcendental numbers are computable. Thus being irrational does not imply not being computable. Yes, there is a distinction to be made about set computability and element computability. The real numbers (rationals and irrationals) are not computable because they are uncountable. Hence floating point numbers only approximate the reals, but they are not real representations themselves. But individual real numbers are frequently computable in a finite number of steps, including irrationals. For example, any given digit of Pi or the sqrt(2) is computable in a finite number of steps. But Chaitan's constant is an uncomputable real number. Likewise, transcendental functions - such as logarithms - are not generally computable as a set even though individual instances can be computed. This is why an inequality including an expression with logarithmic exponents might be reducible in Mathematica, but when you set those exponents to be the ceiling or floor functions of those logarithms it suddenly becomes insoluble. > You can’t find a general, algebraic formula to solve polynomial equations of degree n where n > 4. Yes, and the terminology for something with no general algebraic formula is that there's no closed form solution for it. Mathematica's documentation specifically states it can solve any expression with exponents of 4 of less, but it cannot do so with exponents of greater than 4.

by skh 8y ago

malmsteen 8y ago

Is there "not computable" numbers ? Example ?

wetmore 8y ago
There are "more" non-computable numbers than computable one. Chaitlin's constant is an example.
skh 8y ago
I can give you many more examples of specific computable numbers than I can of noncomputable numbers. This is a bit surprising when one learns that the set of noncomputable numbers is much larger than computable ones. Most of the numbers you’ve dealt with are computable. Every noncomoutable is close to a computable number where close means as close as you want. There is also the notion of definable numbers which is different than computable. There are people who study these things and the implications they have in mathematics and computer science. I’m not one of these people so beyond what I’ve said I don’t dare comment.
lacker 8y ago
In math, infinite sets have different sizes. The number of computer programs is "countably infinite". The number of real numbers is "uncountably infinite". Since there are more numbers than computer programs, some numbers must be uncomputable. for more info see: https://en.wikipedia.org/wiki/Countable_set https://en.wikipedia.org/wiki/Countable_set
- DoctorOetker 8y ago
  Let's consider the plattitude that math appears in printed books, and books contain characters, and the character set or symbol alphabet is finite, and books are finite. Hence the set of all possible books on mathematics is countable. Then how is there a difference between books and programs? Now consider the following program or function: f_epsilon(x) (return x + epsilon;) where epsilon is a number from a set S. Then if the set S is considered countable for pragmatic reasons like representing epsilon in the form of bits etc then everyone agrees it is countable in practice. I.e. aren't there uncountably many functions f(x) above if we allow epsilon to be drawn from an uncountable set?
  - lacker 8y ago
    I agree that the set of all math books is countable, and I agree that there are uncountably many f_epsilon functions if epsilon comes from an uncountable set. However, f(x) = x + epsilon is not a computable function when epsilon is not a computable number. So not all of the f_epsilon family of functions is computable.
  - Dylan16807 8y ago
    There is no important difference between books and functions. Let me present a challenge to you: Pick a uniformly random number between 1 and 2. Now tell me what it is. No 'coincidences', like getting exactly 1.34 or the square root of three. It has to be properly random. The odds are 100% that you picked a 'normal' number that goes on forever with no pattern. A number that cannot be specified in finite space. In other words, a number that can't be computed.
    - DoctorOetker 8y ago
      I fully agree with you. We can also consider a similar function f_epsilon(x) that returns the sum of x and a uniformly random number between 1 and 2 chosen at compile time, but constant at run time. I agree it can't be specified in finite space. The dichotomy is the computational model, from a utilitarian perspective we consider every conceptual computer to be a huge but finite finite-state-machine. One could abstractly (and less down-to-earth usefully) define/conceive of a computer that can store arbitrary variables representing uncountable objects (like real numbers etc)
rntz 8y ago
The Halting Number. The i'th digit after the decimal point of the Halting Number is 0 if the i'th Turing Machine halts given an empty tape, and 1 otherwise. (The integral part of the Halting Number is 0.) This number is not computable; if it were, you could solve the halting problem.
gnulinux 8y ago
Construct a real number by gluing BB(i) where BB is the busy beaver function.
betterunix2 8y ago
Yes. First, fix a programming language; for example, C. Now, the halting problem asks for a given C program and a given stdin, will the program terminate. For simplicity, let's just say that we close stdin and give the program an empty input. It turns out no algorithm can solve the halting problem for all C programs. The explanation is that, if you had such an algorithm, you could write a C program that applies the algorithm to itself (this is a special quine), and then does the opposite of whatever the halting algorithm says the program would do (if it says the program halts, the program will just enter an infinite loop; if it says it does not halt, the program calls exit). Now, imagine a list of all valid C programs in alphabetical order, beginning with the empty string (which, oddly enough, is a valid C program). Consider a number where the Nth digit after the decimal point is 0 if the Nth C program halts, and 1 if it does not; for example, the first digit, corresponding to the empty string, is 0, while a few digits later, the digit corresponding to "int main() {main(); return 0;}" will be 1. Putting it all together, we know there are C programs for which we cannot compute the solution to the halting problem, and we have a number whose digits are determined by the solution to the halting problem for every C program. So that number is not computable (because we cannot compute every digit, so we cannot compute it to arbitrary precision).

throwawaymath 8y ago

These are good points. To expand a bit for even further nomenclature: > All algebraic numbers and some transcendental numbers are computable. Thus being irrational does not imply not being computable. Yes, there is a distinction to be made about set computability and element computability. The real numbers (rationals and irrationals) are not computable because they are uncountable. Hence floating point numbers only approximate the reals, but they are not real representations themselves. But individual real numbers are frequently computable in a finite number of steps, including irrationals. For example, any given digit of Pi or the sqrt(2) is computable in a finite number of steps. But Chaitan's constant is an uncomputable real number. Likewise, transcendental functions - such as logarithms - are not generally computable as a set even though individual instances can be computed. This is why an inequality including an expression with logarithmic exponents might be reducible in Mathematica, but when you set those exponents to be the ceiling or floor functions of those logarithms it suddenly becomes insoluble. > You can’t find a general, algebraic formula to solve polynomial equations of degree n where n > 4. Yes, and the terminology for something with no general algebraic formula is that there's no closed form solution for it. Mathematica's documentation specifically states it can solve any expression with exponents of 4 of less, but it cannot do so with exponents of greater than 4.