## 29 Replies - 12422 Views - Last Post: 31 July 2016 - 06:13 AM

### #16

## Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 08:20 AM

Clojure solution is on the way - just writing up some "test" cases to demonstrate functionality in the face of actual infinity.

### #17

## Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 11:39 AM

Here's the original function I wrote in Haskell that prompted this challenge. It's not very reader friendly or well written but it's what I clobbered together when first thinking about how to do this. In case anyone was wondering this can show up in practice because it showed up in practice for me!

Spoiler

This post has been edited by **ishkabible**: 22 July 2016 - 11:47 AM

### #18

## Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 01:15 PM

I was originally thinking of using C# yield calls, but I couldn't think of how to prevent stalling on empty lines. I may have to use Queue<T> instead to represent the lines. At least with that I can peek to see if the line is empty.

### #19

## Re: Challenge: Help out St. Peter

Posted 22 July 2016 - 04:31 PM

Will Queue<T> work? How do you make it infinite? This is a real question on my part not me trying to guide you away from it. I'm not familiar enough with C# to know the answer.

Also you should be able to use yield/IEnumerator still but it's tricky for multiple reasons

Also you should be able to use yield/IEnumerator still but it's tricky for multiple reasons

Spoiler

This post has been edited by **ishkabible**: 22 July 2016 - 04:34 PM

### #20

## Re: Challenge: Help out St. Peter

Posted 24 July 2016 - 05:08 AM

### #21

## Re: Challenge: Help out St. Peter

Posted 24 July 2016 - 12:04 PM

ishkabible: .NET Framework Queue<T> are just like all the other .NET Framework containers: They'll keep on going until they run out of memory.

AdamSpeight2008: Thank you for that link. I'd been setting aside learning about the Reactive Framework, so it was very satisfying for me to go and try to catch up and learn what the framework is all about.

Spoiler

AdamSpeight2008: Thank you for that link. I'd been setting aside learning about the Reactive Framework, so it was very satisfying for me to go and try to catch up and learn what the framework is all about.

Spoiler

### #22

## Re: Challenge: Help out St. Peter

Posted 26 July 2016 - 05:29 PM

Now that I'm back from vacation:

Spoiler

### #23

## Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 11:28 AM

Hm, am I missing something?

Spoiler

### #26

## Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 12:07 PM

BetaWar, on 28 July 2016 - 06:28 PM, said:

Hm, am I missing something?

Spoiler

Every person has a finite position in their line and that line has a finite position amongst the other lines. It is generally not considered proper to take something that is countably infinite and describe it as 2 positions separated by an infinite amount of positions. Basically, you have no knowledge of the "last" line because there is no "last" line. Any line you are able to select will have a finite amount of lines between it and the starting line. Thus the proposed solution will work. You can pick any person and we can calculate when they will be processed. Since we can calculate when anyone will be processed that means everyone will be processed.

### #27

## Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 12:22 PM

That pre-supposes that you aren't in a scenario where there are infinite lines _before_ the given person you want to determine if they will ever get let through.

It is like saying that between lines 0 and infinity, you know that line 87 will eventually be hit, but that doesn't take into account the infinity between 0 and 1.

Now, practically there may be a solution, but mathematically I don't believe there is.

It is like saying that between lines 0 and infinity, you know that line 87 will eventually be hit, but that doesn't take into account the infinity between 0 and 1.

Now, practically there may be a solution, but mathematically I don't believe there is.

### #28

## Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 12:37 PM

BetaWar, on 28 July 2016 - 09:22 PM, said:

That pre-supposes that you aren't in a scenario where there are infinite lines _before_ the given person you want to determine if they will ever get let through.

Assuming the number of universes is countably infinite, that's a given. Though admittedly I don't think that requirement was stated explicitly.

Note that in practical terms, any kind of enumerator/iterator/stream/lazy datastructure that can exist in a program will at most be countably infinite.

### #29

## Re: Challenge: Help out St. Peter

Posted 28 July 2016 - 01:02 PM

Quote

It is like saying that between lines 0 and infinity, you know that line 87 will eventually be hit, but that doesn't take into account the infinity between 0 and 1.

This is an uncountably infinite scenario so it is irrelevant to the problem. There is line 0 and line 1. These two lines are consecutive and have no lines between them, much less infinite lines between them.

Quote

That pre-supposes that you aren't in a scenario where there are infinite lines _before_ the given person you want to determine if they will ever get let through.

As I described above this line of thinking is not permitted. To simplify the issue, suppose I just start counting 1,2,3,4... and so on. So long as I am capable of counting endlessly I will reach every positive integer. To prove it, for any number you select we can tell when it will be counted. Can you point to a number that will not be counted? Based on your objection, you basically point to "infinity+1" and claim that number will not be counted. Unfortuneately, that is not a number so it fails to disprove that every number will be counted. Any number you can point to will be counted, therefore every number will be counted.

In our scenario, the people in the lines can be enumerated and then we count through them to process all people just as we can count every integer.

### #30

## Re: Challenge: Help out St. Peter

Posted 31 July 2016 - 06:13 AM

This is exactly the kind of discussion I was hoping would come up. Dealing with these notions of infinity and finally understanding them is really interesting IMO. I'm going to try to clear up some confusion here. What sepp2k has been saying is all correct. What mojo666 said about position and having no "last" is correct.

1) There is no uncountability going on here. That's in fact what this exercise proves in a sense! That is if you have an infinity of infinities you don't actually have a greater infinity! These programs, if proven correct, actually prove that any product of countable/finite sets will be at most countably infinite (and at least if one of the things in the product was infinite).

2) I didn't specify what kind of ordinal we were indexing these streams by (statment explained below). I unfortunately took that ordinal to be the natural numbers without clarifying. I assumed it would be clear. Going forward if someone talks about an infinite data structure they're probably refereeing to the sort that can be indexed by natural numbers in someway (be it an infinite tree, list etc...). In this context "line" was supposed to convey that but it doesn't really do that does it? For instance BetaWar mentions "what about the last person" or "what if an infinity came before that?". So this gets tricky. The infinity we are dealing with here is that of the natural numbers, sometimes called omega when in the right set theoretic contexts. These other sorts of infinity BetaWar refers to are in fact consistent notions of infinity called ordinals. If there is 1 last guy in line? that's omega + 1, if theres an infinity before an infinity? that's 2*omega. In a certain sense (read "not actully correct what is to follow but a good intuition") what I asked to occur here was for you to inductively define a map over omega * omega (and a lot of other stuff because I asked for jagged lines) into omega.

I was about to say that had I asked you to do this with omega + 1 or 2*omega that this would not have bene possible. That would be the case had I demanded streams be the representation because while mathematically a stream of length 2*omega makes sense a computer represented stream of such a length does not. But this doesn't mean we can't make a new data structure that represents this! We can, computability, define functions from higher ordinals to objects and map them bijectively into functions from lower ordinals to the same objects. If you guys are interested in working with streams index by higher ordinals I'd bake up another challenge.

3) as hinted at, you should basically think of streams as functions from natural numbers to objects. Of course streams end sometimes and functions from naturals do not end. With a bit of tweaking you can work out the same structure purely in terms of functions however. That's the take away here. You can understand and cope with these notions of infinity by having the right type be the domain of a function.

1) There is no uncountability going on here. That's in fact what this exercise proves in a sense! That is if you have an infinity of infinities you don't actually have a greater infinity! These programs, if proven correct, actually prove that any product of countable/finite sets will be at most countably infinite (and at least if one of the things in the product was infinite).

2) I didn't specify what kind of ordinal we were indexing these streams by (statment explained below). I unfortunately took that ordinal to be the natural numbers without clarifying. I assumed it would be clear. Going forward if someone talks about an infinite data structure they're probably refereeing to the sort that can be indexed by natural numbers in someway (be it an infinite tree, list etc...). In this context "line" was supposed to convey that but it doesn't really do that does it? For instance BetaWar mentions "what about the last person" or "what if an infinity came before that?". So this gets tricky. The infinity we are dealing with here is that of the natural numbers, sometimes called omega when in the right set theoretic contexts. These other sorts of infinity BetaWar refers to are in fact consistent notions of infinity called ordinals. If there is 1 last guy in line? that's omega + 1, if theres an infinity before an infinity? that's 2*omega. In a certain sense (read "not actully correct what is to follow but a good intuition") what I asked to occur here was for you to inductively define a map over omega * omega (and a lot of other stuff because I asked for jagged lines) into omega.

I was about to say that had I asked you to do this with omega + 1 or 2*omega that this would not have bene possible. That would be the case had I demanded streams be the representation because while mathematically a stream of length 2*omega makes sense a computer represented stream of such a length does not. But this doesn't mean we can't make a new data structure that represents this! We can, computability, define functions from higher ordinals to objects and map them bijectively into functions from lower ordinals to the same objects. If you guys are interested in working with streams index by higher ordinals I'd bake up another challenge.

3) as hinted at, you should basically think of streams as functions from natural numbers to objects. Of course streams end sometimes and functions from naturals do not end. With a bit of tweaking you can work out the same structure purely in terms of functions however. That's the take away here. You can understand and cope with these notions of infinity by having the right type be the domain of a function.