Does infinity exist? • Hacker News Board

Re: Does infinity exist?

#61

Post by Bakkot » Sat, Sep 15, 2012, 4:53 PM UTC

inportb wrote: post #43

damoncali wrote: post #11

Earlier quoted context omitted.

Aren't there already guests in room n+1?

Right, so the occupants of n+1 would have to move to n+2 , the occupants of n+2 would have to move to n+3 , and so on. Somewhere, the occupants of n+infinity-1 and n+infinity would have to share a room, but I guess everyone accepts this issue because you'd never actually reach rooms n+infinity-1 and n+infinity by counting/visiting. I'm no mathematician, but this seems to be an edge phenomenon that everyone is willing…

Infinity is not a number.

There is no room 'n+infinity'. There's just not such a room, anywhere, even in principle. Each guest n can move to room n+1 because the guest there is moving to n+2. This works. That's the point.

And you couldn't, in fact, tell the guests to run down the hallway to find an empty room: There is no empty room until you move everyone.

Infinity is counterintuitive, you say? Well, yes, that's the point of this illustration.

Re: Does infinity exist?

#62

Post by tikhonj » Sat, Sep 15, 2012, 4:54 PM UTC

alok-g wrote: post #46

tikhonj wrote: post #27

The idea of different infinities is very important to programmers. In particular, they are the underlying reasons for undecidable problems. You can write any valid computer program as a string of finite length from a finite alphabet. This means the set of programs is countable. (This should not be surprising--everything is ones and zeroes, after all, so you always end up mapping your program to a really large natural…

If a computer cannot have infinite memory, then it cannot go beyond discrete finite automata (DFA) itself. Undecidable problems are several steps more complex than what a DFA can solve. In other words, the theoretical capability of a computer with finite memory is way less than a computer that can solve all but undecidable problems.

That's complicated. While a computer cannot, strictly speaking, have an infinite amount of memory (unless my understanding of physics is off-kilter, which is entirely plausible), computers do have an arbitrary amount of memory. Put another way, I don't know how much memory any given computer can access; for any computer you give me, I could imagine a computer with more memory. (Again, physics intercedes, so this is also something of a thought experiment.) So you can think of Turing-completeness as the limit of what a computer can do as you increase its memory.

To illustrate this fairly viscerally, a modern computer can access the internet and use an obscene amount of memory which will only go up in the future. We don't know how far up it will go, so modelling it as infinite makes sense.

Also, as another thought experiment, what if the universe is infinite? And what if it contains an infinite--or at least quickly expanding--amount of matter? Then a computer could effectively have infinite memory. Unfortunately, I really can't comment because I know even less about physics than I do about math :P.

Re: Does infinity exist?

#63

Post by ced » Sat, Sep 15, 2012, 4:55 PM UTC

tikhonj wrote: post #27

The idea of different infinities is very important to programmers. In particular, they are the underlying reasons for undecidable problems. You can write any valid computer program as a string of finite length from a finite alphabet. This means the set of programs is countable. (This should not be surprising--everything is ones and zeroes, after all, so you always end up mapping your program to a really large natural…

Nice post.

the number of programs we can write is countable; the number of functions we can write over interesting domains (like natural numbers or integers) is not countable

You should edit and rewrite "the number of functions we can write over interesting domains" as "the number of functions that exist over interesting domains" - it tripped me up.

So we have managed to show, in a fairly simple way, that there have to exist undecidable problems.

I don't think that this is correct. I had to check Wikipedia on decidability:

There are two distinct senses of the word "undecidable" in mathematics and computer science. The first of these is the proof-theoretic sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. The second sense, which will not be discussed here, is used in relation to computability theory and applies not to statements but to decision problems, which are countably infinite sets of questions each requiring a yes or no answer. Such a problem is said to be undecidable if there is no computable function that correctly answers every question in the problem set.

I don't believe that you're talking about the first meaning, from formal logic. As for the second meaning, it does not apply either, since your "problem set" is not countably infinite.

Re: Does infinity exist?

#64

Post by Evbn » Sat, Sep 15, 2012, 4:56 PM UTC

Bakkot wrote: post #59

Dove wrote: post #34

Earlier quoted context omitted.

I'd never thought about that before. I think you could use that argument to prove that strong AI is impossible. --------------- Consider an AI to be a chat program which maps strings to strings -- all the strings of its input over time to all the strings of its output. There are, by the argument above, an uncountable number of such mapping programs, only a countable number of which can actually be coded. So, enumerat…

> A strong AI can certainly do this. A strong AI can say something different than the thing it's about to say? That's a neat trick. Not a part of any definition of strong AI I've ever heard, though. Could a human do it?

No, a human could not. Similarly, No human nor computer can name all the real numbers.

Luckily, it turns out that there were only ever be a finite number of questions ever asked, which require only finite answers. Similarly, the halting problem is solvable on finite memory machines, aka the only kind that exist.

Re: Does infinity exist?

#65

Post by joshzayin » Sat, Sep 15, 2012, 4:57 PM UTC

DenisM wrote: post #47

tikhonj wrote: post #27

The idea of different infinities is very important to programmers. In particular, they are the underlying reasons for undecidable problems. You can write any valid computer program as a string of finite length from a finite alphabet. This means the set of programs is countable. (This should not be surprising--everything is ones and zeroes, after all, so you always end up mapping your program to a really large natural…

Your explanation of why a powerset of a countable set is not countable didn't make intuitive sense to me, but wikipedia concurs ( http://en.wikipedia.org/wiki/Cantor%27s_Theorem ): ...the power set of a countably infinite set is uncountably infinite... You've made an excellent and entirely counter-intuitive observation, sir.

Here's perhaps an easier to understand proof.

Let A be a countable set. Now, suppose that there was a surjective function (one that hits every element of P(A)) f: A -> P(A). (Note that f takes elements of A, and produces subsets of A.)

Now, define Y ⊆ A as follows: For all x in A, x is in Y if and only if x is not in f(x).

Thus, Y, which is in P(A), is distinct from every output of f, and so f is not actually surjective.

This means that no surjective function f: A -> P(A) exists.

This is a generalization of Cantor's Diagonal Argument (http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument).

Re: Does infinity exist?

#66

Post by gjm11 » Sat, Sep 15, 2012, 4:59 PM UTC

tikhonj wrote: post #27

The idea of different infinities is very important to programmers. In particular, they are the underlying reasons for undecidable problems. You can write any valid computer program as a string of finite length from a finite alphabet. This means the set of programs is countable. (This should not be surprising--everything is ones and zeroes, after all, so you always end up mapping your program to a really large natural…

This shows that, e.g., there are uncomputable functions, uncomputable sets of natural numbers, etc.

But I don't think it's reasonable to say that this shows that there are undecidable problems, because for something to be called a "problem" it has to be something you can actually state -- and there are only countably many of those, for exactly the same reason as there are only countably many programs that might solve them.

It's true, none the less, that there are undecidable problems; for instance, "given a computer program in such-and-such a language, does it always terminate in finite time whatever input you give it?". But you need a more sophisticated argument to show that.

Similarly, there are only countably many properties of natural numbers that you can write down in any formal language, and this sort of cardinality-counting argument won't let you prove that any of those are uncomputable. Some of them are, but again you need a more complicated argument to prove it.

Re: Does infinity exist?

#67

Post by tikhonj » Sat, Sep 15, 2012, 5:00 PM UTC

sp332 wrote: post #54

tikhonj wrote: post #27

The idea of different infinities is very important to programmers. In particular, they are the underlying reasons for undecidable problems. You can write any valid computer program as a string of finite length from a finite alphabet. This means the set of programs is countable. (This should not be surprising--everything is ones and zeroes, after all, so you always end up mapping your program to a really large natural…

I think you have confused two terms: countable and finite . In the simplest example, the natural numbers 1, 2, 3, 4, 5... are countable but infinite. So it's not really a mapping between two countably infinite sets, it's a mapping between two finite sets.

Rather, I habitually confuse the countable with countably infinite. For example, I said the set of computer programs is countable when I really meant countably infinite. Moreover, the set of inputs (which are also finite strings over a finite alphabet) is similarly countably infinite. So we can't write programs for every possible function from strings to strings.

Re: Does infinity exist?

#68

Post by gjm11 » Sat, Sep 15, 2012, 5:01 PM UTC

Dove wrote: post #34

tikhonj wrote: post #27

The idea of different infinities is very important to programmers. In particular, they are the underlying reasons for undecidable problems. You can write any valid computer program as a string of finite length from a finite alphabet. This means the set of programs is countable. (This should not be surprising--everything is ones and zeroes, after all, so you always end up mapping your program to a really large natural…

I'd never thought about that before. I think you could use that argument to prove that strong AI is impossible. --------------- Consider an AI to be a chat program which maps strings to strings -- all the strings of its input over time to all the strings of its output. There are, by the argument above, an uncountable number of such mapping programs, only a countable number of which can actually be coded. So, enumerat…

What exactly do you mean by "strong AI"?

The usual meaning is something like "a computer or similar system that does all the same things a human mind does, or better".

I think you're taking it to mean something like "a computer or similar system that can correctly answer absolutely any question you put to it". So far as I know, no one thinks that's possible.

Re: Does infinity exist?

#69

Post by sp332 » Sat, Sep 15, 2012, 5:02 PM UTC

tikhonj wrote: post #67

sp332 wrote: post #54

Earlier quoted context omitted.

I think you have confused two terms: countable and finite . In the simplest example, the natural numbers 1, 2, 3, 4, 5... are countable but infinite. So it's not really a mapping between two countably infinite sets, it's a mapping between two finite sets.

Rather, I habitually confuse the countable with countably infinite . For example, I said the set of computer programs is countable when I really meant countably infinite . Moreover, the set of inputs (which are also finite strings over a finite alphabet) is similarly countably infinite. So we can't write programs for every possible function from strings to strings.

OK I guess what I'm missing is how finite strings over a finite alphabet are infinite? Edit: never mind I was confusing "finite" as meaning "bounded".

Re: Does infinity exist?

#70

Post by tikhonj » Sat, Sep 15, 2012, 5:03 PM UTC

Dove wrote: post #34

tikhonj wrote: post #27

The idea of different infinities is very important to programmers. In particular, they are the underlying reasons for undecidable problems. You can write any valid computer program as a string of finite length from a finite alphabet. This means the set of programs is countable. (This should not be surprising--everything is ones and zeroes, after all, so you always end up mapping your program to a really large natural…

I'd never thought about that before. I think you could use that argument to prove that strong AI is impossible. --------------- Consider an AI to be a chat program which maps strings to strings -- all the strings of its input over time to all the strings of its output. There are, by the argument above, an uncountable number of such mapping programs, only a countable number of which can actually be coded. So, enumerat…

I think the core issue is what constitutes "strong AI". This is a philosophical question--after all, all philosophy seems to deal with is arguing about the definitions of stuff (I kid, I kid).

I've always taken "strong AI" to mean something fairly non-mathematical--an AI that is at least as intelligent as a human, except ideally faster and less quirky. This is obviously possible as humans exist! (Maybe it requires some nigh magical hardware, but that's a different story.)

What exactly do you consider "strong AI" to mean? (I'm genuinely curious and not trying to argue against anything you've said, to be perfectly clear.)