Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Does infinity exist?

plus.maths.org

Post reply on HN
Print view View original

31–40 of 127 posts

Re: Does infinity exist?

#31

Post by plusplus »

damoncali wrote: post #17
Cushman wrote: post #13

Earlier quoted context omitted.

No, those guests now stay in room n+2.

I don't get it. Can't I just as easily say that n+2 is also occupied? After all, they're all occupied by definition, aren't they? For example. All blocks are either red or blue. You have an infinite number of blocks that are all red. Do you have any blue blocks? No. Where is the mistake in my logic?

You do it for all natural numbers n=1, 2, 3 , ... (those are countably infinately many numbers).

Because every natural number n has a successor n+1, you can do it for all of them.

Each n except 1 has a predecessor n-1 from which guests where moved to n. Nobody moved into 1, therefore you can put the new arrivals there.

After that, there are still (countably) infinite many guests. They are just matched up differently with the rooms/numbers.

Because you have infinitely many rooms, you were able to accomodate one more by matching them up differently. That's sort of the point :-)

Re: Does infinity exist?

#32

Post by mistercow »

I find this question very perplexing. I can't tell if it arises from a misunderstanding of the concept of "existence" or just a misunderstanding of how important infinities are in a massive number of real world applications. I mean, two doesn't really "exist"; but we sure as hell need it if we want to get any work done.

Re: Does infinity exist?

#33

Post by [deleted] »

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…

[deleted]

Re: Does infinity exist?

#34

Post by Dove »

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, enumerate the ones that can be coded. This shouldn't even be difficult--let's just do it alphabetically.

Now, suppose I have a strong AI called Sal. My first input to Sal is to describe the program enumeration strategy, and instruct her to respond to any string which contains a number by looking up the program on the table corresponding to that number, inputting all the input she has received so far, and then giving a response different than what it would give.

A strong AI can certainly do this.

Sal is not programmable.

Re: Does infinity exist?

#35

Post by ajanuary »

leviself wrote: post #23
damoncali wrote: post #11

Earlier quoted context omitted.

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

Yes. The statement as given doesn't work out. If you say "an infinite number of guests and an infinite number of rooms" it works. But when every room is endowed with the property of being occupied there is no room for more guests.

It brings up an interesting point, though. If I have an infinite number of rooms and an infinite number of guests, then one might intuit that every room is occupied.

There is a mapping of every guest to a room: guest n is in room n. Yet somehow there exists a room that has no guest, despite being able to model both rooms and guests with the same infinite set.

Re: Does infinity exist?

#36

Post by damoncali »

plusplus wrote: post #31
damoncali wrote: post #17

Earlier quoted context omitted.

I don't get it. Can't I just as easily say that n+2 is also occupied? After all, they're all occupied by definition, aren't they? For example. All blocks are either red or blue. You have an infinite number of blocks that are all red. Do you have any blue blocks? No. Where is the mistake in my logic?

You do it for all natural numbers n=1, 2, 3 , ... (those are countably infinately many numbers). Because every natural number n has a successor n+1, you can do it for all of them. Each n except 1 has a predecessor n-1 from which guests where moved to n. Nobody moved into 1, therefore you can put the new arrivals there. After that, there are still (countably) infinite many guests. They are just matched up differently…

You cannot move someone to a full room. All of the rooms are full. Explain that part.

Re: Does infinity exist?

#37

Post by quacker »

Dove wrote: post #28
drblast wrote: post #5

My favorite thought experiment that I think is relevant here is to try to pick a truly random number. If you think about it, this is impossible, because the act of picking a number limits you to a finite set of numbers that you have considered. Put another way, you can't pick numbers from an infinite sample space because you can't create an infinite sample space. This has all sorts of odd implications, like the two e…

The ability to pick a truly random integer from a uniform distribution is just a practical one. Consider: How many digits does a "typical" integer have? The answer is that it is unbounded. For any value you choose, it is easy to show that there are far more integers with more digits than with less. So indeed, even writing down your choice of a random integer would take a long time. But I don't think the two envelope…

But I don't think the two envelope paradox has anything to do with that practical impossibility. It is about the rules of symbol manipulation and modeling.

Exactly this. The two envelopes paradox is a paradox only because using a fallacious argument leads to the wrong result, and the Wiki page proposes numerous resolutions to the problem as well. I like this way of stating it (from http://en.wikipedia.org/wiki/Two_envelopes_problem#Non-proba...):

1. Let the amount in the envelope chosen by the player be A. By swapping, the player may gain A or lose A/2. So the potential gain is strictly greater than the potential loss.

2. Let the amounts in the envelopes be X and 2X. Now by swapping, the player may gain X or lose X. So the potential gain is equal to the potential loss.

In the first case, A and A/2 are actually referring to the same amount of money. You have to condition on what A is: If A is the larger value, the second envelope cannot contain 2A; A/2 is equal to the smaller amount. If A is the smaller amount, then the second envelope cannot contain A/2; A is equal to the smaller amount. So your potential gain and loss are both equal to the smaller amount of money, and you have no logical reason to swap.

Re: Does infinity exist?

#38

Post by masklinn »

ajanuary wrote: post #21
recursive wrote: post #7

Earlier quoted context omitted.

The classic approach is to move all the existing guests from room n to n+1 and put the new party in room 1.

I can see how that works if you have an infinite number of rooms and an infinite number of guests, because you still have an unoccupied room to move them up into. But how does that work when you've stated that all rooms are occupied? I'm really struggling to square up my understanding of how the former problem works with my intuition that if every room is in an occupied state, you can't magic up some in an unoccupied…

> I'm really struggling to square up my understanding of how the former problem works with my intuition that if every room is in an occupied state, you can't magic up some in an unoccupied state.

That's the problem with infinites. Consider the number of all positive integers. Let's call it a1.

Now consider the number of all even positive integers. Let's call it a2.

Each even integer can be directly mapped to an integer and the other way around by multiplying or dividing by 2, right? All integers can be multiplied by 2, and all even integers can be divided by 2.

So a1 = a2, the number of integers is the same as the number of even integers, even though you'd intuit the number of integers to be twice the number of even integers.

Just as it does when reaching the infinitely small (0.999… is precisely equal to 1), intuition breaks down when reaching into the infinitely big.

Re: Does infinity exist?

#39

Post by alok-g »

davmre wrote: post #15
drblast wrote: post #5

My favorite thought experiment that I think is relevant here is to try to pick a truly random number. If you think about it, this is impossible, because the act of picking a number limits you to a finite set of numbers that you have considered. Put another way, you can't pick numbers from an infinite sample space because you can't create an infinite sample space. This has all sorts of odd implications, like the two e…

Put another way, you can't pick numbers from an infinite sample space because you can't create an infinite sample space. That's not true; there's nothing wrong with infinite sample spaces. It's just that there's just no such thing as a uniform distribution over an infinite space. For example, suppose you flip a fair coin repeatedly until the first time it comes up Heads. The number of flips you end up making could be…

How about generating an infinite sequence of bits to generate any positive integer (in binary) with uniform probability? Sure it will take infinite time, but so may the method in your note. As another comment here points out, it would take infinite time to write down a purely random number anyways.

Re: Does infinity exist?

#40

Post by nhaehnle »

billswift wrote: post #29
leviself wrote: post #23

Earlier quoted context omitted.

Yes. The statement as given doesn't work out. If you say "an infinite number of guests and an infinite number of rooms" it works. But when every room is endowed with the property of being occupied there is no room for more guests.

That's the sort of thing that happens when semantics meets mathematics; Swizec screwed up his statement of the problem. Swizec and the people agreeing that the answer is yes are confusing the problem's literal statement with the common statement of similar problems.

I am thoroughly confused as to what your point is. What is the problem with Swizec's wording in your view? Should s/he have written "Can you make room for more guests?". I agree that you could argue that right now there is no room free, and that the answer should be No because of that. However, given that you can easily make one room free by having every guest go to the next room, that just seems overly nit-picky to me, and like you are intentionally trying to miss the point.
Post reply on HN