5 ms·

In math, infinite sets have different sizes. The number of computer programs is "countably infinite". The number of real numbers is "uncountably infinite". Sinc

by 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)
    - Dylan16807 8y ago
      How many f_epsilon functions do you set up at compile time? If it's countable, then your computer can now reflect the previously-computable numbers across these epsilons, and give you new numbers, but you're still only covering 0% of the reals. If it's uncountable, covering a range, then you just moved the problem back a step. On top of that, such a computer doesn't even have to do real work. You can spend 20 seconds using grade school arithmetic to map the input range to the entire set of reals, 1:1. But mapping a range of reals into a bigger range of reals is a pretty lousy definition of "computable".

by lacker 8y ago

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)
  - Dylan16807 8y ago
    How many f_epsilon functions do you set up at compile time? If it's countable, then your computer can now reflect the previously-computable numbers across these epsilons, and give you new numbers, but you're still only covering 0% of the reals. If it's uncountable, covering a range, then you just moved the problem back a step. On top of that, such a computer doesn't even have to do real work. You can spend 20 seconds using grade school arithmetic to map the input range to the entire set of reals, 1:1. But mapping a range of reals into a bigger range of reals is a pretty lousy definition of "computable".