Comment by nwhitehead | Hacker News Reader

Comment by nwhitehead | Hacker News Reader

Parent Full thread

For each fixed length there are a finite number of programs of that length. If we use 8-bit bytes for the alphabet, there are 256^N programs of length N. The set of ALL programs is infinite (we don't limit the length of programs), but it is countable.

The "countable" part means we can put the set into one-to-one correspondence with the natural numbers. The correspondence starts with 0 mapping to the empty program, then 1-256 mapping to programs of a single byte, then 257-65793 mapping to the programs of two bytes, and so on. This mapping will hit each program exactly once, and it will hit every program because every individual program has a finite length.

Different types of infinities are not intuitive so don't feel bad if the concepts are confusing. These issues troubled lots of very smart mathematicians for decades. The existence of irrational numbers was hugely troubling to Pythagoreans. The existence of uncountable infinities discovered by Cantor was shocking [1].

[1]: http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_the...

In some sense, the existence of irrational numbers with no pattern in their digits is an illusory artifact of the number system. We can talk about them collectively because decimals are not required to have an end, and we have to postulate them to fill in the gaps in the number line, but such numbers lack any description or means of being separated as individuals.

But then, is any mathematical abstraction real? I guess it's all beside the point.

This is wrong. The square root of two was identified as irrational by the ancient Greeks, when considering the length of the diagonal of the unit square. The proof has nothing to do with decimal fractions (they didn't use decimal fractions at all).

I'm referring to irrational numbers with no pattern. Square roots can be described and the digits can be enumerated by an algorithm. The diagonalization argument shows that there can't be a description for all irrational numbers.

Just to be clear: you think that there are many irrational numbers that exist independently of which number system you use, but that there are infinitely many that do depend on the number system you use? Is that right?

Irrational numbers, by definition, include decimal numbers that have infinitely many digits after the decimal point, and there are no rules about what those digits have to be. This is powerful enough to represent any irrational number regardless of the number base. However, if you're talking about number systems, not all number systems have equal ability to represent irrational numbers. Whatever the system, to represent all the irrationals, it would have to be capable of going on forever. I think the part of my point that you're asking about is my statement that they're a side effect of decimal numbers. Irrational numbers like sqrt(2) and e have concise representations as the limits of Taylor series. Only when converted into decimals do they appear to have infinite amounts of information. So if we used Taylor series as the number system instead of decimals, simple irrationals would look simple, and we might be less inclined to treat them the same as numbers that have no finite descriptions at all.

I was under the impression that irrational numbers are numbers that simply can't be represented as a ratio. This is independent of the number system used. I'm not familiar with the Taylor series: can you use it as a number system? Isn't it simply a representation of functions (in which case, you might as well just write "sqrt(2)" as invoke anything else)?

It's tough to Google for "Taylor series number system" as you just get pages about the guitars. ;-)

I don't know if you're still reading this, but... Using Taylor series as a number system is just a hypothetical. Any systematic way of describing numbers could be a number system. Irrationals can't be represented as ratios, but beyond that, some have other finite representations, and others have none.

Take a look at this.

http://en.wikipedia.org/wiki/Definable_number

> In some sense, the existence of irrational numbers with no pattern in their digits is an illusory artifact of the number system.

But irrational numbers remain irrational in any integer number base. Therefore no, they aren't illusory at all, nor are they an artifact of the "number system".

> ... such numbers lack any description or means of being separated as individuals.

Also false. Many irrational numbers are easy to identify unambiguously. For example, the square roots of numbers that are not perfect squares are irrational, but they can be easily identified by squaring them.

While we're on the topic, the terms in the running sum of odd numbers are all perfect squares:

    0 + 1 =  1
    1 + 3 +  4
    4 + 5 =  9
    9 + 7 = 16
   16 + 9 = 25

As is often true in mathematics, this is easier to explain with a picture:

http://arachnoid.com/example/#Math_Example

> But then, is any mathematical abstraction real?

Certainly. Consider general relativity. It's a mathematical abstraction, and it's also real.

"Many irrational numbers are easy to identify unambiguously."

Absolutely. Cantor proved that an infinite number of others can't be identified at all, because they outnumber all possible descriptions. Some numbers can only be described by an infinitely long list of digits, one that can't be produced by a Turing machine and contains an infinite amount of irreducible information. The Kolmogorov complexity is infinite.

Newton's equations describe a mathematical model of the universe that agrees well with measurements taken under familiar conditions. Einstein's equations describe a different mathematical model, one that has good agreement with experiment over a much wider range of conditions than Newton's. But general relativity has well-known problems. Its equations give nonsense solutions under some circumstances, e.g. singularities. Physical theories are models that predict the outcomes of experiments. They're reductionist out of necessity. It's unknown and probably unknowable as to whether a perfect model is possible, but there are likely things that can't be reduced.

> Cantor proved that an infinite number of others can't be identified at all, because they outnumber all possible descriptions.

I'm tempted to say that that definition places those examples in a unique set, thus at least unambiguously identifying the set to which they belong.

You can identify the set of numbers with infinite Kolmogorov complexity. But you can't separate out an individual from the set.

Turing machines might not capture all numbers that can be described, but, interestingly, descriptions and Turing machines have the same cardinality.

This appears to be exactly the concept I was talking about. Maybe I read about these numbers some time ago and forgot that they already had a name.

http://en.wikipedia.org/wiki/Definable_number

> But then, is any mathematical abstraction real? I guess it's all beside the point.

I actually think the reality of mathematical abstractions is hugely important because of... computer programs! In a real way, programs are the embodiment of mathematics. I want my programs to work so I need the underlying math to work as well.

That's why I'm a constructivist. I reject the law of the excluded middle because proofs that use it don't translate into real programs; they translate into programs that ask an omnipotent oracle to decide which branch to take. Constructive proofs translate into working programs.

It also ties into philosophy. I am a skeptic, so when someone tells me either A or not A must be true even if we can never know which one, I ask for proof or justification of that fact. The justifications that I get are remarkably similar to logical "proofs" that god exists, and just as fallacious. This isn't to say that there couldn't be an ultimate truth about A or a god, just that it is not logically necessary.

Interesting. I'm not all that up on philosophy, and I had to look up constructivism and the law of the excluded middle. Computers can only deal directly with discrete math, so that eliminates quite a bit of mathematics. Moreover, despite being regarded as Turing machines, you could in reality count all the states that a computer could be in, by counting the bits of memory, and you will find that it's a finite number. So computers are, in fact, only finite state machines. It's often overlooked that what makes a Turing machine a Turing machine is the infinitely-long tape. So computers occupy a fairly small sliver of the infinite universe of math.

Philosophically, my worldview is like that of science: the way to know something is by making observations and formulating and testing hypotheses. What we can observe is limited, and hypotheses are only models that are tested by successive approximations. I'm not sure I understand what you mean that that statement isn't required to have an ultimate truth. Presumably a statement like that has an answer, but the fact that something is knowable in principle doesn't mean that there's any way to get the answer. For instance, the Hubble telescope can see far away galaxies that we can never get an up close look at. The question of whether there's life somewhere else in the universe must have an answer, but we can't know what's in those galaxies; even with a better telescope, we'd be seeing what they looked like a billion years ago. Many things will never be known.

Reply on news.ycombinator.com