A twist on the switch problem

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

A twist on the switch problem

Postby sfwc » Tue Apr 05, 2011 8:50 pm UTC

This is a variant on a classic problem. That classic problem has been discussed here many times, but the variant has not (so far as I can tell). If you are familiar with the standard puzzle, please take the time to see why this is not it.

You have been told that 100 prisoners (whose identities are concealed from you and from each other) are about to be locked up. As well as the cells for the prisoners, the prison has a room called the switch room, containing a single switch, which will initially be left in the `off' position. At sporadic and unpredictable times during his or her confinement, each prisoner will be taken to the switch room, and allowed to either flick the switch or leave it as it is. At any time, any prisoner may claim that all prisoners have visited the switch room. If they are right, all prisoners will go free, but if they are wrong all prisoners will be killed, and you (who are not a prisoner) will also be killed.

The prisoners may not confer with one another to produce a strategy. Instead, you can compose an email outlining a strategy for them, which will be sent to all the prisoners (and also read by the malicious warden, who decides who goes into the switch room when). You may assume that no prisoner will ever be left to languish in their cell forever without the possibility of further visits to the switch room. Can you come up with a strategy guaranteeing their release?

Here's why the standard strategy for these problems won't work:
Spoiler:
The standard strategy relies on one prisoner having a special role, but since you don't know the prisoners, you can't distinguish between them so as to assign that role to just one of them. Standard strategies without this asymmetry typically rely on the prisoners having extra information, for example that just one prisoner visits the switch room each day.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: A twist on the switch problem

Postby redrogue » Tue Apr 05, 2011 9:37 pm UTC

Unfortunately this won't work with a malicious warden, but here's the general strategy for solving it without a specified counter.

Spoiler:
Each prisoner has a count that starts at zero.

If they enter the room and the light bulb is on, they flip it off and increment their count by one.
If they enter and the bulb is off AND their count is more than one, decrement their count by 1 (to a minimum of zero) and switch the bulb on (If their count was zero, do nothing).

Once someone hits the limit, they announce.

Note that this works if all of the prisoners have to announce, too. After a prisoner announces, they switch strategies and perform no action if the bulb is on... only slowly decrease their count if it is off.
Is 'no' your answer to this question?

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: A twist on the switch problem

Postby skeptical scientist » Wed Apr 06, 2011 5:17 am UTC

redrogue wrote:
Spoiler:
Each prisoner has a count that starts at zero.

You mean 1.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: A twist on the switch problem

Postby redrogue » Wed Apr 06, 2011 4:42 pm UTC

Indeed I do. :oops:

This is a little better, since only one person needs to announce:
Spoiler:
Everyone starts at one.

If the light bulb is on AND their count is 1 or more, flip it off and increment their count by one.
If the bulb is off AND their count is 1 or more, decrement their count by 1 (to a minimum of zero) and switch the bulb on (If their count was zero, do nothing).

The (second) bolded change ensures that once a prisoner hits zero, they stop being a counter and their count will stay in the pool.


What it needs is:
Spoiler:
A means of making prisoners with positive counts stop counting and start returning their counts to the pool. I'd say flip a coin, or make a set of prison dice out of toilet paper, but the warden might outlaw those items.

Something like, "If you get bored, just ignore the bulb if it is on, and give back counts one at a time until you are out." ... but replace 'If you get bored' with criteria within the confines of the problem.
Is 'no' your answer to this question?

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

Re: A twist on the switch problem

Postby EricH » Wed Apr 06, 2011 6:35 pm UTC

The malicious warden :evil: would most easily break redrogue's scheme by sending in each prisoner twice in a row.

I've been considering whether we can substitute 'same' and 'different' positions for 'on' and 'off' and it's not enough.
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: A twist on the switch problem

Postby sfwc » Wed Apr 06, 2011 8:00 pm UTC

Some interesting ideas so far, and one approach which sort-of works:

redrogue wrote:What it needs is:
Spoiler:
A means of making prisoners with positive counts stop counting and start returning their counts to the pool. I'd say flip a coin, or make a set of prison dice out of toilet paper, but the warden might outlaw those items.

Something like, "If you get bored, just ignore the bulb if it is on, and give back counts one at a time until you are out." ... but replace 'If you get bored' with criteria within the confines of the problem.

Yeah, I was trying to set the problem up so as to exclude that sort of thing. Remember, I want to know if there is a strategy which is guaranteed to work, so
Spoiler:
Using random number generators, for example tossing coins, isn't helpful. Your strategy has to work whatever way the coins come down. In the technical jargon, for those who know it, I'm not just asking whether there is a strategy which almost surely works but whether there is one which surely works.

I may well not have been smart enough to set it up so as to exclude this sort of trickery entirely, but since that was my intent let's all just pretend that I succeeded.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A twist on the switch problem

Postby Yakk » Wed Apr 06, 2011 8:41 pm UTC

Papers:
Spoiler:

The first attack I'd try is to try to get a distinguished prisoner. Problem: 1000 years after the game starts, you first walk into a room and see the lightbulb on. Are you the 2nd prisoner ever? Or has everyone already tried to massively negotiate and fail to get anywhere?

Ie, in order to pick out a distinguished prisoner, you need to know if every prisoner has had a chance to communicate, which already solves the problem.

We could try making micro-distinguished prisoners.

Ie: if the first time you enter the room, you see a 0, you set it to 1. You are now a prisoner of type A.
If the first time you enter the room, you see a 1, you set it to 0. You are now a prisoner of type B.

That gives a way to create some kind of distinguished properties of prisoners. Still doesn't help, but ...
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: A twist on the switch problem

Postby redrogue » Wed Apr 06, 2011 9:22 pm UTC

Think I got it: Don't got it.

Spoiler:
You must always decrease your count if the light is off (and your count is > 0). Do so by switching the light on.
You may only increase your count if the light is on, your count is > 0, and you saw the light was on the last time you entered the room. Do so by switching the light off.

If your count is zero, do nothing.
If the light was off last time you entered, do nothing.

This should (relatively) rapidly decrease the number of counters, since they must wait a round, as well as prevent the warden from 'toggling' count among a small number of prisoners.


Edit: This won't work, since the warden can just send everyone into the room 3 times in a row, round robin style.
Is 'no' your answer to this question?

User avatar
dedalus
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

Re: A twist on the switch problem

Postby dedalus » Mon Apr 11, 2011 12:35 am UTC

So here's my thinking:
Spoiler:
Every prisoner starts off on a count of 1. They also have another counter i, which starts at 2. Each prisoner can be in one of two states. The first state is similar to that suggested by redrogue - if the light is off, the prisoner turns it on and decreases their count by 1. If the light is on, the prisoner turns it off and decreases their count by 1. A prisoner with a count of zero is a 'null prisoner' so to speak (or a third state) - they don't do anything.

As well as this, prisoners in state 1 keep track of the maximum number times they have obtained any given count during this phase of state 1. When this number goes over i, they increment i by 1, and enter state 2. In state 2, they don't do anything until they've entered the room i times, at which point in time they go back to state 1, perform the appropriate action, *then* restart the tracking of the maximum number of times they have obtained any given count, and go again.

E.g. Prisoner 1 enters the room first. They see the light off, so they turn it on and become null.
Prisoner 2 enters the room second. They see the light turned on, so they turn it off and now have a count of zero.
If the warden now sends Prisoner 2 back in twice, Prisoner 2 will then have had a count of 2 twice, and enter state 2, with i=3. If he then enters the room 3 more times, on the third time he will flick the light back off, decrease his count to 1, but this move won't count towards the maximum number of times he has seen a count of 1.

This requires repeatedly sending a prisoner in n number of times (where n is constantly increasing), so I think that necessitates more then one prisoner going to a count of zero, but I'm pretty sure it can still be looped (for example, if there are only 2 prisoners left with count > 0). I think if we invented some more states we could get around this though (E.G. a prisoner with a count greater then 50 does not turn the light on and decrement their count).
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: A twist on the switch problem

Postby gcoope » Mon Apr 11, 2011 6:22 pm UTC

I think I have a solution to this, mega post incoming, would definitely like someone to check it!

Spoiler:
The warden can always screw the prisoners.

The strategy is deterministic, and the same for all the prisoners. Furthermore each prisoners strategy on each go is uniquely determined by the state of the switches he has seen before.

Assume such a strategy exists for any order of prisoners determined by the warden.

Lemma: the strategy will not involve toggling a switch back and forward if no change has been seen.

i.e. if a prisoner leaves or switches the switch on and the next time they come back it is still on, they will never need to switch it off on that turn and vice-versa. To see this note that since the strategy must work with any order of prisoners the warden selects, it must in particular work with the same order with a repetition of that same prisoner.

Hence there is a strategy such that if a prisoner is brought back multiple times in a row by the warden, they will not alter the switch after the first visit, if at all, let's consider this strategy from now on to show it cannot exist.

if 0 is off and 1 is on
let P = P1, P2, P3 ... be the binary sequence where Pn is the state the prisoner will move the switch to on their nth visit to the room, if they have entered the room and the switch be set to 0 every time
let Q = Q1, Q2, Q3 ... be the binary sequence where Qn is the state the prisoner will move the switch to on their nth visit to the room, if they have entered the room and the switch be set to 1 every time

for instance P = 1, 0, 0, 0, ... would indicate that if a prisoner entered the room for the first time ever and the switch was off they would turn it on, if they then entered the room for the second time ever and the switch was off again they would leave it off, note that P says nothing about what would happen if they entered the room for a second time and the switch was on, their behaviour from then on is not described by P or Q.

note from our Lemma that if Pk = 0 for some k then Pn = 0 for all n>k
if Qk = 1 for some k then Qn = 1 for all n>k

so P is a sequence of 1s followed by all 0s and Q is a sequence of 0s followed by all 1s

let s be the smallest number s.t. Ps = 0 if such an s exists
let t be the smallest number s.t. Qt = 1 if such a t exists

consider four prisoners alf, bob, xav, yas

if s <= t or s exists and t doesn't

the warden sends in alf then xav alternately s - 1 times
alf keeps switching the switch to 1
xav keeps switching the switch to 0

the warden sends in alf once more
alf leaves the switch on 0 (Ps = 0)

now any further times alf and xav see a 0 without seeing a 1 they will leave the switch in 0 (Lemma)

the warden can then do exactly the same with bob and yas subsituted for alf and xav
from this point on the switch will always remain 0, and there is no chance that the prisoners can have enough information, since any sequence observed by alf or xav would feel exactly the same as one without bob and yas and vice-versa



if t < s or t exists and s doesn't

the warden sends in alf then xav alternately t - 1 times
alf keeps switching the switch to 1
xav keeps switching the switch to 0

the warden sends in alf and xav once more
alf switches the switch to 1 (P(t-1) = 1)
xav leaves the switch on 1 (Qt = 1)

now any further times alf and xav see a 1 without seeing a 0 they will leave the switch in 1 (Lemma)

the warden sends in bob then yas alternately t - 1 times
bob keeps switching the switch to 0
yas keeps switching the switch to 1

the warden sends in bob once more
bob switches the switch to 1 (Qt = 1)

now any further times bob and yas see a 1 without seeing a 0 they will leave the switch in 1 (Lemma)

from this point on the switch will always remain 1, the prisoners do not have enough information since any sequence observed by bob or yas will feel exactly the same as one without xav and alf only going in once, likewise any sequence observed by alf or xav would feel the same as one without bob or yas participating at all


if neither s or t exist, i.e. P is a sequence of all 1s, Q is a sequence of all 0s

the warden can send a rotation of alf, bob, xav and yas. the sequence they observe will not be distinct from one which is missing another prisoner.

I believe this argument can be extended to any even number greater than 2 by considering the prisoners in pairs.

edit: should also work for odd numbers by sending one prisoner in multiple times at the start and letting him settle into a row of ons, then just do the same problem with 0 and 1 reversed for the remaining even number of prisoners.

edit2: the problem is clearly soluble for 2 prisoners, 3 prisoners is winnable by the prisoners by doing redrogue's amended scheme.

edit3: to clarify my Lemma I am arguing that by the warden repeatedly putting in the same prisoner until they stick with a position then the problem becomes simplified to one where the prisoners always stick with their position. If they weren't to stick with a position then their future positions could still be subdivided into sequences which did leave the switch always in the same position, it is the warden's absolute knowledge of the strategy that allows this.

Phew
Last edited by gcoope on Mon Apr 11, 2011 7:46 pm UTC, edited 1 time in total.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A twist on the switch problem

Postby Yakk » Mon Apr 11, 2011 7:29 pm UTC

Spoiler:
gcoope, what if the warden cannot solve the algorithm that the prisoners are using?

You implicitly implied that the warden solved the halting program described by the original email sent -- ie, the warden can figure out that the prisoners will settle down.

I guess the prisoners have to prove certain properties about their algorithm, and as such the warden also has to be able to prove the same properties?

Except the prisoners just have to prove that "eventually, given that every prisoner will visit an infinite number of times, we will be able to know that every prisoner has entered", while the warden (in order to use your attack) has to prove "at this particular point, a prisoner is now behaving in a really simple manner".

Your lemma:
"Lemma: the strategy will not involve toggling a switch back and forward if no change has been seen.

i.e. if a prisoner leaves or switches the switch on and the next time they come back it is still on, they will never need to switch it off on that turn and vice-versa. To see this note that since the strategy must work with any order of prisoners the warden selects, it must in particular work with the same order with a repetition of that same prisoner."
No, it doesn't have to work in any order of prisoners the warden selects. It has to eventually work after that order of prisoners.

Imagine if it is set up so that it doesn't trigger until after the 100 millionth time every prisoner enters the cell. So for the first 1 million entries, everyone toggles the switch. Everyone expect this to happen, yet they somehow factor that out.

Second, you tried a reduction -- "if there is a solution, there is a simpler solution", then implicitly reasoned that the simple solution cannot exist with reasoning that relies on the solution being simple enough to solve (in a certain sense) by the warden.

Your approach seems wonderful -- and this objection may not be substantial enough to defeat it. But it is at least worth considering...
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: A twist on the switch problem

Postby gcoope » Mon Apr 11, 2011 8:02 pm UTC

Yakk, thanks for the in-depth look at my idea.

I have updated my post to try and clarify the Lemma, although I think you got it.
Spoiler:
You are right that the warden must be able to determine the long term behaviour of a single prisoner if they are repeatedly put in the room, which is a bigger question that just determining the next state of the switch.

If someone could find such an algorithm that works, is deterministic, and fundamentally difficult to characterise long-term that'd be absolutely fascinating to me.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A twist on the switch problem

Postby Yakk » Mon Apr 11, 2011 8:18 pm UTC

Spoiler:
Busy Beaver. Don't know if it works... but it is deterministic and no warden can solve it.

Or other ridiculous situations, such as:
https://secure.wikimedia.org/wikipedia/ ... ee_theorem
where elementary proofs of the halting of a given algorithm grow in size ... rather too fast to express through any sane means.

The real catch here is that the other prisoners need to be able to justify that they have found every prisoner, and the warden is just as smart as the prisoners.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: A twist on the switch problem

Postby douglasm » Mon Apr 11, 2011 8:51 pm UTC

I think I have an idea that might work, let's see if I can type up the details.
Spoiler:
Everyone has a count that starts at 1. Everyone has a meta-state with possible values Done, Counter, Provisional Exiter, and Exiter.

Done: Do nothing. Ever.

Counter:
If the switch is on, flip it and increase your count by 1. If this causes your count to reach its previous maximum for the second time, become a Provisional Exiter.
If the switch is off and your count is the highest it has ever been, flip it and decrease your count by 1. If this makes your count 0, become Done.
If the switch is off and your count is 1 below the highest it has ever been, do nothing.

Provisional Exiter:
If the switch is on, flip it and increase your count by 1. Become a Counter.
If the switch is off, flip it and decrease your count by 1. Become an Exiter.

Exiter:
If the switch is on, do nothing.
If the switch is off, flip it and decrease your count by 1. If your count reaches 0, become Done.

Once a Counter reaches a count of 100, he can announce that all prisoners have visited the room.

Why this works:
The end condition is obvious - the total count (+1 for an on switch) is always 100, so a count of 100 necessarily requires that all 99 others have reached count 0 and become Done.

In order to defeat a strategy, the Warden must either cause an erroneous announcement (not possible) or get the prisoners stuck in an endless loop. The Warden cannot cause an oscillation-style endless loop because the only prisoner type vulnerable to it, Counter, converts to Provisional Exiter after a single iteration of the loop and does not convert back unless non-loop progress is made. Thus, the Warden's only hope is static no-change looping. This requires having every prisoner at a "do nothing" state, which means either Counter at 1 below highest and an off switch or Exiter with an on switch. If all Counters are 1 below max, that means the last Counter to leave max status flipped the switch on. All ways to flip the switch off produce either a Counter or Provisional Exiter at current highest count, so that do-nothing combination isn't possible - producing either part of it requires negating the other part.

The only remaining failure combination to consider is all Exiters with an on switch. If all prisoners are Done or Exiters, the Exiters themselves will promptly turn the switch on so that part isn't a problem for the Warden. The problem is that he must somehow get every prisoner into Exiter/Done status. Which is... really easy. Crap.


Never mind, found an obvious failure pattern for my strategy while trying to write up an explanation of it. Feel free to read it for ideas, but it doesn't actually work.

Hmm, further thinking I don't have time to fully expand and analyze atm: what if every prisoner had a direction of count as part of the meta state and tried to oscillate repeatedly between 1 and increasingly large maximums (1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5...), but jumping out if the chance to hit 0 ever comes up?

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

Re: A twist on the switch problem

Postby EricH » Mon Apr 11, 2011 8:57 pm UTC

Yakk, I want to pull that last statement out of your spoiler for discussion:
Yakk wrote:The real catch here is that the other prisoners need to be able to justify that they have found every prisoner, and the warden is just as smart as the prisoners.


Is that true? From the problem statement,
sfwc wrote:At any time, any prisoner may claim that all prisoners have visited the switch room. If they are right, all prisoners will go free, but if they are wrong all prisoners will be killed, and you (who are not a prisoner) will also be killed.

The way I read it, then, we don't have to prove to the warden that every prisoner has visited the switch room--he already knows whether they have or not. We just have to avoid making the claim until that condition occurs.
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: A twist on the switch problem

Postby gcoope » Mon Apr 11, 2011 9:05 pm UTC

douglasm wrote:Never mind, found an obvious failure pattern for my strategy while trying to write up an explanation of it. Feel free to read it for ideas, but it doesn't actually work.

Hmm, further thinking I don't have time to fully expand and analyze atm: what if every prisoner had a direction of count as part of the meta state and tried to oscillate repeatedly between 1 and increasingly large maximums (1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5...), but jumping out if the chance to hit 0 ever comes up?

Interesting ideas but I think any approach like this is doomed to failure unless you can point out a flaw in my reasoning above (not unlikely).
EricH wrote:The way I read it, then, we don't have to prove to the warden that every prisoner has visited the switch room--he already knows whether they have or not. We just have to avoid making the claim until that condition occurs.

Is there really a difference? If they cannot prove that every prisoner has visited the switch room I don't see how they can know the condition to be true.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A twist on the switch problem

Postby Yakk » Mon Apr 11, 2011 9:25 pm UTC

To make the claim, they have to prove it to themselves (or that is how I read it).

---

Lets start with 2 prisoners and a lightbulb, and work our way up maybe?

2 prisoners:
If you see it off, turn it on. You now leave it on.
If you see it on without turning it on, say 'we have all been in the room'.

3 prisoners:
First time you enter, you see a 0. You turn it on. You now do nothing forever.
First time you enter, you see a 1. You turn it off. You now do nothing forever. If you ever see it on again, you say "we have all been in the room".

So now we can claim "with at least 4 prisoners", which you used in your argument.

How about 4 prisoners? It is a small enough set that we might be able to find a flaw in your argument explicitly.

Now, if you don't respond to seeing a 0 the first time you enter, the warden can just keep sending you in until you would set it to 1. In fact, the warden can do this for every single prisoner, reducing the game to one in which "when you first see a 0, you set it to 1". (if nobody ever changes a 0, the game ends)

So, WLOG (without loss of generality), we can assume:
First time you enter, you see a 0. You set it to 1.

Next, if you are ever provably going to respond to a given input, WLOG you will respond the first time, as the Warden can "force" a response by sending you in repeatedly until you do.

Similarly, if new prisoners never respond to a 1, game collapses immediately upon the first time a prisoner enters.

So, first time you enter, you see a 1. You set it to 0.

These must be true.

At this point here, we have two kinds of prisoners -- alpha and beta. Alpha saw a 0 initially, and Beta saw a 1 initially.

Each Beta knows that there was at least one Alpha before it. Alphas do not know this.

The 3 prisoner problem was solved by Betas being able to recognize Alphas that arrived after them, by Alphas becoming lazy.

---

Alphas being lazy seems like a good move. If you are an Alpha, you are out of the game.

Betas then eat a "1" from someone. This might be an Alpha. Later 1s can also be Alphas, as they cannot distinguish between the two.

How does a Beta respond to a nigh-infinite chain of later 0s? How about a later 1?

Suppose Betas ignore 0s. Then the Warden simply sends 4 people in order, and the two Betas "starve". Thus Betas cannot ignore 0s. They must drop a 1 on a 0.

A problem is that a Beta dropping a 1 on a 0 is indistinguishable from the Beta not being there.

Hmm.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A twist on the switch problem

Postby WarDaft » Mon Apr 11, 2011 11:14 pm UTC

Hmm...
Spoiler:
Some rough work...

If the switch is off when you first enter, you are a countee, turn it on, never do anything else ever again. If it is on when you first enter, you are a counter, turn the switch off, your count is one.

If you are a counter, and you enter the room, and the switch is on, turn it off and increase your count by one.

If you are a counter, and you enter the room, and the switch is off, you are no longer a counter. Your goal is now to turn the switch on once for each time you've counted, and once for yourself, and never again turn it off. Once you have turned it on this many times, you will never touch it ever again.

No, this doesn't work... the warden could make all the counters self-destruct.


Hmm.


Ooooh.... the prisoners need to see sequences of other people having flipped it! The first time each prisoner enters the room, they flip the switch, and this determines their polarity. They will only ever flip the switch in that direction, but they have to see it in sequences before they will do so. They must demand longer and longer sequences (ensuring that more and more people have been to the room, as the other prisoners will be demanding longer sequences as well) and when they have seen one long enough, then they can flip it.

The question is, can we actually construct sequences which guarantee success for the problem at hand?

This strikes me as something that might get fiddly.

Let's see if we can get the four prisoner case working as a test run...

If you see it off on your first time, you are type A, flip it.
If you see it on on your first time, you are type B, flip it.

First try at sequences:

Type A: Turn it on it when you see each of 0, 010, for the first time. If you see the second, declare all prisoners accounted for.
Type B: Turn it off when you see each of 1, 101, for the first time. If you see the second, declare all prisoners accounted for.

This... appears to work!

Assuming the warden tries to have as few of the prisoners visit as they can manage...

Code: Select all

0:1:0:1:0:0:1:1:0 (what the prisoners see)
a b a b a c a d a (the prisoner visits)

a-0 (prisoner a is type A)
0
010. (prisoner a has seen both sequences, and declares the game over, correctly)
b-1
1
.101 (prisoner b has seen the first sequence and is looking for a 1)
c-0
.0
010
d-1
.1
101

There is no point in bringing either of the first prisoners back in after the first 5 visits, as neither will do anything, via the guarantee that the warden will eventually bring someone else in, there is no advantage gained from waiting to do so.

Now the warden will try to get them all in a state where they will do nothing more...

Code: Select all

0:1:0:1:0:0:1:0:1:0
a b a c a d c d b d

a-0
0
0.10
b-1
1
.101
c-1
1
.101
d-0
0
0.10

Drat, he found one.
Well, we're safe because none of the prisoners will call out wrongly, but they're stuck. Anyone see any room for improvements? Perhaps some multiples of prisoners simply can't be freed? Do we know for sure this problem has a positive solution?
Last edited by WarDaft on Mon Apr 11, 2011 11:38 pm UTC, edited 1 time in total.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Ansain
Posts: 207
Joined: Sun Apr 15, 2007 1:15 am UTC
Location: Here

Re: A twist on the switch problem

Postby Ansain » Mon Apr 11, 2011 11:37 pm UTC

This might work

Spoiler:
There are four possible states for a prisoner, neutral, counter, countee, and done.

Everyone starts Neutral with 1 count and zero delay

Neutral with 1 or more delay:
If the switch is on turn it off and gain 1 count, become a counter and lose all delay
If the switch is off choose 1 of the following
- turn it on and lose 1 point, lose 1 delay.
- do nothing lose 1 delay.

Neutral with no delay:
If the switch is on turn it off and gain 1 count , become a counter
If the switch is off turn it on and lose 1 count, become a countee

Counter:
If the switch is on, turn it off and gain 1 count
If the switch is off do nothing. Become Neutral and gain between 1 and 5 delay (your choice)

Countee:
If the switch is on, do nothing
If the switch is off turn it on, lose 1 count

Done:
If at any point you have 0 count you become done.
From now on you do nothing.

When deciding how much delay to take and whether to do nothing during the delay consider that the warden may be trying to turn everyone into a leaver, or he may be trying to create an infinite loop where points keep switching back and forth.

I think the fact that the prisoners have choices in this strategy means that they could win, but it also means that (depending on the wardens strategy) it could be difficult to win.


edit: to ensure you cannot lose by being put into the room multiple times in a row
Spoiler:
When you become neutral with delay and the switch stays in the same position (off) you must choose to flip it once before your delay runs out.
Why put off till today what you could just as easily get done tomorrow?

I can mathematically prove that 1 equals 0!.

Parts a-x in my plan weren't that important anyways.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: A twist on the switch problem

Postby gcoope » Mon Apr 11, 2011 11:51 pm UTC

I think I have this solved for any reasonably simple strategies, see my earlier post, I know it's not written out hugely clearly.

@Ansain...how do your prisoners choose between their two options? Even though they know the warden is malicious I don't see how this helps.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A twist on the switch problem

Postby WarDaft » Mon Apr 11, 2011 11:59 pm UTC

Woops, I let the warden make a slight error, that might be important...

Also, my solution involves more communication between the prisoners than is immediately apparently possible, so it should avoid at least the basic pitfalls.

Spoiler:
It might be necessary to have an extremely large definition base so as to arrange for sub-typing based on observed sequences of changes, if so, the worst case scenario could be that our email length is exponential or even super-exponential in the number of prisoners.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: A twist on the switch problem

Postby gcoope » Tue Apr 12, 2011 12:07 am UTC

WarDaft wrote:Woops, I let the warden make a slight error, that might be important...

Also, my solution involves more communication between the prisoners than is immediately apparently possible, so it should avoid at least the basic pitfalls.

You can follow my argument with your strategy fairly well, hopefully it can demonstrate it.
P = 1,0,0,0....(since if a prisoner sees a 0 first time he will change it to a 1, if he sees 0s every time after that he will never change it)
Q = 0,1,1,1....
so s=t=1
thus the warden can send a,x,b,y....just send them in one after the other
a will switch it to 1
x will switch it to 0
b will switch it to 1
y will switch it to 0

none of the prisoners will ever switch it again now, and they have clearly not gained enough knowledge to determine that every prisoner has entered.

of course this particular arrangement only works for this particular set of sequences, however the warden can come up with an order of prisoners that will spoil the party for any algorithm like this.

edit: the trick to this is to keep the prisoners in two sets of equivalent people, they don't end up getting to see varied sequences as the warden doesn't let them.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A twist on the switch problem

Postby WarDaft » Tue Apr 12, 2011 12:30 am UTC

.... you edited your post, and now... it's actually wrong.

thus the warden can send a,x,b,y....just send them in one after the other
a will switch it to 1
x will switch it to 0
b will switch it to 1
y will switch it to 0

none of the prisoners will ever switch it again now,

That would be

Code: Select all

0:1:0:1:0
a b c d ?

a-0
.0
010
b-1
.1
101
c-0
.0
010
d-1
.1
101
Both a and c are looking for a single zero and that's what's next.

Granted, it looks like you can still trap them, but they will switch it at least a few more times.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: A twist on the switch problem

Postby gcoope » Tue Apr 12, 2011 12:50 am UTC

Sorry, I understood the first position they see to also be their first sequence they are looking for. If you want a and c to see another 0 and b and d to see another 1 just try:

a, b, a, b, c, d, c, d

now they will all just leave it on 0.

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: A twist on the switch problem

Postby sfwc » Tue Apr 12, 2011 2:28 pm UTC

gcoope has solved it. Congratulations!

There isn't a strategy which guarantees that the prisoners escape. If you think you have such a strategy, please test it against gcoope's strategy for the warden, outlined in his earlier post, before you put it here.

There are a couple of details to sort out. First, there might be some bits of the proof which could do with some clarification. If there's anything you want more detail about, then ask here. If gcoope doesn't answer your questions, then I'll try to.

Second, although gcoope's argument works for 100 prisoners,
Spoiler:
his extension to odd numbers of prisoners doesn't quite work: The prisoners apart from the one you singled out at the start might end up always returning 0s, and then you couldn't ever reintroduce the original prisoner without endangering everything.

So it would be good to resolve the question `for which N can N prisoners get out?'. No major new ideas needed for this, I promise. What we know already:
Spoiler:
The prisoners get out if N is at most 3. The warden might be able to keep them in if N is even and at least 4.

Yakk, the questions you asked lead to some interesting issues, which I haven't thought about before. Since your objections don't apply to a warden with God-like omniscience, and since even a warden who isn't omniscient might get lucky and act like one who is, the prisoners can't guarantee their escape.

[Jargon alert]However, it might be possible to produce a computable strategy which will beat any warden who acts in a computable way. Also, the argument that the warden can keep the prisoners in relies on the law of the excluded middle. I wonder if it's possible to set up an intuitionistic model in which the prisoners can always get out? I would be very interested to see an answer to either of these questions.[/Jargon alert]

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A twist on the switch problem

Postby Yakk » Tue Apr 12, 2011 5:00 pm UTC

... ok, someone posted a solution then deleted it. Sigh. Anyhow, I had fun with notation, so I'll post the problem with it:
Spoiler:
State diagram:

Code: Select all

  [Z]<--(0,1)--[I]--(1,0)-->[?]--(1,0)-->[*]--(1,0)-->[Exit]
   ^----(0,1)--[X]<-(0,1)---/

You start at I. Edges are labelled with (input, output) pairs. Non-labelled inputs loop back to the same state with (x,x) edges.

The game is pretty simple.

You start with one 1 in your stomach. By default, you eat 1s, and dumping 1s on zeroes. If you have 3 1s in your stomach at any time, you refuse to dump 1s anymore. If you ever dump a 1, you stop eating 1s.

The first person dumps a 1. They are now "out of the game" (in state Z for Zero). The first person being assigned to show up by the warden no longer matters.

The second person sees that one and eats it. We'll call this state [Z][?]0. They are now in state [?], or in an intermediate state. We have two branches: one in which the second person repeats before the third person arrives (S+), and one where the second person doesn't (S-).

If [?] visits before anyone else, we end up in [Z][X]1, which is stable. So these are the two possible states before person #3 is introduced to the room.

Case S+: 3rd person visits [Z][X]1
The third person arrives to a 1. The third person transitions to [?], giving us a state of [Z][X][?]0.

Case S-: 3rd person visits [Z][?]0
The third person arrives to a 0. The third person transitions to a [Z], giving us a state of [Z][Z][?]1.

S+ can transition to S- if [X] is the next one to visit.
S+ can transition to S+- if [?] visits next:

Case S+-:
[?] visits after S+. State is now [Z][X][X]1.

Before the 4th prisoner shows up, no visit can exit these 3 states.

So we have to worry about [Z][X][?]0, [Z][Z][?]1 and [Z][X][X]1.

The 4th prisoner visits each of these states, giving us the following possible states:
A: [Z][Z][X][?]1
B: [Z][Z][?][?]0
C: [Z][X][X][?]0

In A, the only state transition possible is [?] visiting. So it evolves as follows (all evolution is forced):
[Z][Z][X][*]0 -> [Z][Z][Z][*]1 -> [Z][Z][Z][EXIT]0

In B, either [?] visiting is a state change, which ... sends us to state A:
[Z][Z][X][?]1 -> [Z][Z][X][*]0 -> [Z][Z][Z][*]1 -> [Z][Z][Z][EXIT]0

In C, there are two initial branches. If [X] visits, we end up ... in state A.
If [?] visits, we end up ... crashing:
[Z][X][X][X]1
We lose.

Lets reverse engineer the route to failure shall we?
0 -> [Z]1 -> [Z][?]0 -> [Z][X]1 -> [Z][X][?]0 -> [Z][X][X]1 -> [Z][X][X][?]0 -> [Z][X][X][X]1
Ie, the first person puts a 1 on the track. Each person after that picks it up and drops it off again, entering the "nulled" state of [X]. We end up with a bunch of prisoners who all think that picking up the 1 is someone else's responsibility.

I'm still trying to figure out a good information theoretic boundary that makes this problem insolvable.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: A twist on the switch problem

Postby sfwc » Tue Apr 12, 2011 11:22 pm UTC

I wrote:However, it might be possible to produce a computable strategy which will beat any warden who acts in a computable way.

I just realised that that isn't possible.
Spoiler:
gcoope's method can be reformulated as a collection of countably many computable strategies, such that whatever strategy the prisoners play at least one of these strategies will defeat them.

Yakk is right that it isn't clear what the right boundary is here. My next guess is that there is no computable way to turn (programs for) computable strategies for the prisoners into (programs for) computable strategies for the warden which will beat them.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: A twist on the switch problem

Postby gcoope » Wed Apr 13, 2011 12:57 am UTC

sfwc wrote:Second, although gcoope's argument works for 100 prisoners,
Spoiler:
his extension to odd numbers of prisoners doesn't quite work: The prisoners apart from the one you singled out at the start might end up always returning 0s, and then you couldn't ever reintroduce the original prisoner without endangering everything.

Spoiler:
Yeah you're right, If I may reformulate my answer a little. We simplify the problem as before, where the prisoners don't bother changing the switch if they reenter and it is the same, such behaviour could be negated by the warden repeatedly choosing them until they switch it into one of the infinitely repeating positions.

The sequences P and Q and integers s and t are as defined earlier;

Pi is the value of the switch left by a prisoner who has been in the room exactly i times and every time they have entered the room the switch has been off
Qi is the value of the switch left by a prisoner who has been in the room exactly i times and every time they have entered the room the switch has been on

As noted before P is a sequence of 1s possibly followed by a sequence of 0s
Q is a sequence of 0s possibly followed by a sequence of 1s

let s be the first position a 0 appears in P
t be the first position a 1 appears in Q

s or t being undefined are left as an exercise

now what the warden can try and do is to put the two prisoners into types, ones who only ever see an off switch or their same switch again, and ones who only ever see an on switch or their same switch again

let the two groups be called G (will only turn the switch on or leave it) and H (will only turn the switch off or leave it)


if |H| <= (s-1)*|G| <= (t-1)*|H|

the warden can alternate sending in members of G and H, each member of G s - 1 times, each member of H at least once and at most t - 1 times, in any order until he runs out of members of G (which will happen from the above condition) and ending with a member of H

the switch will have been turned on and off (s-1)*|G| times, and from Ps = 0 we know that the next time any member of G enters the room he will leave the switch off, since the members of H all turned the switch off last then they will leave it off. So from this point on none of the prioners will change the switch.

How do we know that none of the prisoners can announce, since the warden has sent in every prisoner by this stage? Well if |G| > 1 and |H| > 1 then for any given prisoner it's easy to construct a sequence which would look identical to them but not involve every prisoner.


if |G| <= (t-1)*|H| + 1 and (t-1)*|H| < (s-1)*|G|

the warden can alternate sending in members of G and H, each member of G at least once and at most s - 1 times, each member of H t-1 times, until he runs out of members of H and ending with a member of G

the switch will have been turned on (t-1)*|H| + 1 times, from Qt = 1 we know that the next time any member of H enters they will leave the switch on, since all of G have turned the switch on most recently they will leave it on


so if the warden can split the group into G and H with sizes fulfilling one of the above conditions he is sorted
if s = 1 or t = 1 the inequalities break down but these cases can be treated separately, left as an exercise

if the number of prisoners is even = 2n, try |G| = n, |H| = n
now clearly either (s-1)*n <= (t-1)*n or (t-1)*n < (s-1)*n so we are done

if the number of prisoners is odd = 2n+1 and t > 1, s > 1
let |G| = n + 1, |H| = n
|H| <= (s-1)*|G| and |G| <= (t-1)*|H| + 1

clearly exactly one of (s-1)*|G| <= (t-1)*|H| or (t-1)*|H| < (s-1)*|G|
so the warden can always split up a group of at least 4 and perform the strategy explained above

1, 2 and 3 prisoners have all been shown to be possible by the prisoners

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: A twist on the switch problem

Postby sfwc » Wed Apr 13, 2011 9:13 am UTC

gcoope wrote:
Spoiler:
Yeah you're right, If I may reformulate my answer a little. We simplify the problem as before, where the prisoners don't bother changing the switch if they reenter and it is the same, such behaviour could be negated by the warden repeatedly choosing them until they switch it into one of the infinitely repeating positions.

The sequences P and Q and integers s and t are as defined earlier;

Pi is the value of the switch left by a prisoner who has been in the room exactly i times and every time they have entered the room the switch has been off
Qi is the value of the switch left by a prisoner who has been in the room exactly i times and every time they have entered the room the switch has been on

As noted before P is a sequence of 1s possibly followed by a sequence of 0s
Q is a sequence of 0s possibly followed by a sequence of 1s

let s be the first position a 0 appears in P
t be the first position a 1 appears in Q

s or t being undefined are left as an exercise

now what the warden can try and do is to put the two prisoners into types, ones who only ever see an off switch or their same switch again, and ones who only ever see an on switch or their same switch again

let the two groups be called G (will only turn the switch on or leave it) and H (will only turn the switch off or leave it)


if |H| <= (s-1)*|G| <= (t-1)*|H|

the warden can alternate sending in members of G and H, each member of G s - 1 times, each member of H at least once and at most t - 1 times, in any order until he runs out of members of G (which will happen from the above condition) and ending with a member of H

the switch will have been turned on and off (s-1)*|G| times, and from Ps = 0 we know that the next time any member of G enters the room he will leave the switch off, since the members of H all turned the switch off last then they will leave it off. So from this point on none of the prioners will change the switch.

How do we know that none of the prisoners can announce, since the warden has sent in every prisoner by this stage? Well if |G| > 1 and |H| > 1 then for any given prisoner it's easy to construct a sequence which would look identical to them but not involve every prisoner.


if |G| <= (t-1)*|H| + 1 and (t-1)*|H| < (s-1)*|G|

the warden can alternate sending in members of G and H, each member of G at least once and at most s - 1 times, each member of H t-1 times, until he runs out of members of H and ending with a member of G

the switch will have been turned on (t-1)*|H| + 1 times, from Qt = 1 we know that the next time any member of H enters they will leave the switch on, since all of G have turned the switch on most recently they will leave it on


so if the warden can split the group into G and H with sizes fulfilling one of the above conditions he is sorted
if s = 1 or t = 1 the inequalities break down but these cases can be treated separately, left as an exercise

if the number of prisoners is even = 2n, try |G| = n, |H| = n
now clearly either (s-1)*n <= (t-1)*n or (t-1)*n < (s-1)*n so we are done

if the number of prisoners is odd = 2n+1 and t > 1, s > 1
let |G| = n + 1, |H| = n
|H| <= (s-1)*|G| and |G| <= (t-1)*|H| + 1

clearly exactly one of (s-1)*|G| <= (t-1)*|H| or (t-1)*|H| < (s-1)*|G|
so the warden can always split up a group of at least 4 and perform the strategy explained above

1, 2 and 3 prisoners have all been shown to be possible by the prisoners

Yes, that works.

I wrote:My next guess is that there is no computable way to turn (programs for) computable strategies for the prisoners into (programs for) computable strategies for the warden which will beat them.

I've now come up with a proof. I'll show that if the warden can do this then they can solve the halting problem.
Spoiler:
Suppose the prisoners play like this: First, they all agree on some program P. On their first visit to the switch room, they each set their internal state to either counter (if the switch was set to 0 when they entered) or countee (if it was set to 1), and they put the switch in position 1. There is another internal state setting; they can be either frozen or active. After their first visit to the switch room they become frozen (so some of them become frozen counters, others frozen countees). On subsequent visits to the switch room they act like this:
  • If they are frozen, they leave the switch as it is. They run one more step in the computation of P, and if P halts then they become active. Otherwise, they remain frozen.
  • If they are active, they proceed according to the standard strategy. So countees begin with one soul and try to give it away as soon as they get the chance, and counters collect all the souls they can and announce that all the prisoners are present once they have collected enough souls.

If the program P never halts, then this is a pretty awful strategy. Nevertheless, it is the inclusion of these cases which makes trouble for the warden. In such a case, the first prisoner to enter the room will set the switch to 1 and from that point on everyone will leave it in that position (since they will always stay frozen). The warden must eventually bring all prisoners into the switch room, and so eventually all prisoners will have visited it. At that point, the first prisoner who entered the room will be a counter, the rest will be countees. An observer who knew that the warden would beat the prisoners could now conclude that P never halts; if it ever did halt then once they all defrosted the prisoners' souls would quickly all be collected by the counter and they would escape. Since the warden's strategy is computable, this would give a way to compute whether P halts, and so to solve the halting problem; run a simulation of the above events and if all prisoners enter the switch room before anybody defrosts then P never halts.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A twist on the switch problem

Postby WarDaft » Wed Apr 13, 2011 6:22 pm UTC

There is of course the problem, that if the prisoners can prove that their plan will actually work, then so can the warden. This means the prisoners must select a strategy which they cannot prove will guarantee their escape beforehand, and hope that it will let them escape without the warden besting the strategy.

Now it depends on the universe that the warden lives in.

Suppose the warden constructs a random oracle from a QRNG. If the sequences produced by QRNG are incomputable, then it is possible for the warden to always have a chance to defeat the prisoners. The question is simply how large can this chance be made?

With such a QRNG, the warden can construct random values with infinite expected value but are finite with probability 1.

The simplest is of course the double until tails method (IE a 50% chance of 1, a 25% chance of 2, a 12.5% chance of 4... with expected value of 0.5 + 0.5 + 0.5...) but lets assume the warden is a little more malicious and instead triples until double tails (25% chance of 3, 18.75% chance of 9, ~14% chance of 27...).

Now the warden has the prisoners visit with the following strategy:
For all but the first prisoner, before ever bringing in the n+1th prisoner for a visit, first select a random value with the method above and wait until the nth prisoner has been brought in that many more times. The first prisoner may be brought in freely.

So, a mocked up example, (these numbers are taken from a BBS generator with 71 bit modulus... I was in a hurry)

Before the 4rd prisoner is brought in for the first time, the third prisoner must be brought in 3 times. For the third prisoner to be brought in 3 times, the second prisoner must be brought in 9 + 729 + 9 times. Before the second prisoner may be brought in 747 times, the first prisoner must be brought in 602204895 times. It is not practical for me to have started with the 5th prisoner, as it would require billions of RNG calls to determine the number of times the first prisoner would be brought in. I can say that for the first million visits by the second prisoner, the first prisoner must have 718,346,015,925,179,029,774,464 visits with the seed and modulus I have chosen.

I'm sure this method could be improved upon further of course. For example, I have been resetting the visit count to 3 on every occurrence of double tails. This is perhaps overly kind of the warden.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

gcoope
Posts: 30
Joined: Sun May 17, 2009 11:48 am UTC

Re: A twist on the switch problem

Postby gcoope » Thu Apr 14, 2011 8:08 am UTC

@ WarDaft

It appears you are now looking at the question of whether you can give the prisoners a chance of escaping with a non-deterministic algorithm, and trying to reduce the probability of this by increasing the expected number of visits that must be made. However it doesn't quite work like that. There is no guarantee that increasing the expected number of visits will reduce the long term probability or possibility of the prisoners' escape.

Incidentally if we are to answer this question fully I believe we may need a couple of clarifications which weren't relevant in the deterministic question:

1. Does the warden have to pre-plan his sequence of prisoners who come into the room or can he select dynamically?
2. Can the warden use his knowledge of who has announced to select prisoners dynamically?
3. Can the warden see the switch position and use this knowledge to select prisoners dynamically?
4. Must the warden be going to bring someone in again surely or almost surely?

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: A twist on the switch problem

Postby sfwc » Thu Apr 14, 2011 5:15 pm UTC

gcoope wrote:There is no guarantee that increasing the expected number of visits will reduce the long term probability or possibility of the prisoners' escape.

I agree. A simple modification of my argument above should give the following result (sorry about the painful phrasing, but I wanted to be exact).

Let p be any real number which is at least 0 and strictly less than 1. There is no computable way to turn (names of) programs for computable strategies for the prisoners into (names of) programs for nondeterministic computable strategies for the warden such that, whatever (name of a) program the prisoners use, their chance of escaping is at most p.

gcoope wrote:Incidentally if we are to answer this question fully I believe we may need a couple of clarifications which weren't relevant in the deterministic question.

These are important distictions, but I think we can afford to be very generous to the warden and still get the result above.

1. We can let him select his sequence of prisoners dynamically.
2. (Omitted since I didn't understand gcoope's point (2). Once someone announces everyone is released or killed.)
3. We can let him see the switch position and use this knowledge.
4. We need only require him to return each prisoner to the room almost surely.

We can also require the prisoners to be completely deterministic in their strategy.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A twist on the switch problem

Postby Yakk » Thu Apr 14, 2011 5:25 pm UTC

4. We need only require him to return each prisoner to the room almost surely.

Wait, what?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A twist on the switch problem

Postby WarDaft » Thu Apr 14, 2011 8:12 pm UTC

Let p be any real number which is at least 0 and strictly less than 1. There is no computable way to turn (names of) programs for computable strategies for the prisoners into (names of) programs for nondeterministic computable strategies for the warden such that, whatever (name of a) program the prisoners use, their chance of escaping is at most p.
Uh... actually... across all programs... that's trivially false.

Via the Chaitan constant, only a certain percentage of all programs eventually halt. The prisoners have to chose a program that they cannot prove an upper bound on halting, otherwise the warden could prove the same upper bound as well, and use that to ruin them - the warden has no bound on the amount of time they can work on proving this, yet you must at some point have stopped trying to do so to provide the strategy to the prisoners.

The percentage of programs which are unlikely to be proven to have an upper bound on execution time given a certain amount of time to prove it so, yet do indeed halt, surely cannot be any larger than the percentage of programs overall that halt.



I was thinking strictly of strategies the warden could then do to bolster the chances that the prisoners would be executed if they selected a program that does indeed halt without either party knowing it, and using a QRNG is a very possibly (though not provably) non-computable tool the warden could use to increase their likelihood of besting the prisoners.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: A twist on the switch problem

Postby sfwc » Fri Apr 15, 2011 11:46 am UTC

Yakk wrote:
4. We need only require him to return each prisoner to the room almost surely.

Wait, what?

I guess I should have been clearer about this. A very simple (and not especially sensible) strategy for the warden would be to always pick a prisoner to enter the switch room at random. If they do that, then the probability that they meet the condition that no prisoner should be forever kept away from the switch room is 1. So they meet this condition almost surely, rather than surely. If we were very strict, and required the warden to surely meet this condition, we wouldn't allow that strategy (or others like it, such as those mentioned by WarDaft above) for the warden. But we don't have to be that strict.

WarDaft wrote:Uh... actually... across all programs... that's trivially false.

It looks like despite my convoluted phraseology I wasn't clear enough about what I meant. The kind of situation I intended to exclude was one in which, for any particular name N of a strategy S for the prisoners, if we first calculate what strategy S' the warden will use against S and then calculate the probability that the prisoners will get out if they play S and the warden plays S', we'll get an answer which is at most p.

This calculation is made after we already know what strategy the prisoners are going to use, so it doesn't depend on knowing how likely it is that the prisoners would use any particular strategy. That's why considerations involving the Chaitin constant, which does rely on knowing something like that, can't arise. More precisely, there isn't just one Chaitin constant. To get a `Chaitin constant' you first need to specify some extra data, which roughly can be thought of as computably assigning to each (name of a) program a probability that that (name of a) program will be used.

I guess I need to work on my clarity.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A twist on the switch problem

Postby Yakk » Fri Apr 15, 2011 4:00 pm UTC

sfwc wrote:
Yakk wrote:
4. We need only require him to return each prisoner to the room almost surely.

Wait, what?
I guess I should have been clearer about this. A very simple (and not especially sensible) strategy for the warden would be to always pick a prisoner to enter the switch room at random. If they do that, then the probability that they meet the condition that no prisoner should be forever kept away from the switch room is 1. So they meet this condition almost surely, rather than surely. If we were very strict, and required the warden to surely meet this condition, we wouldn't allow that strategy (or others like it, such as those mentioned by WarDaft above) for the warden. But we don't have to be that strict.
Hmm. Can we exploit that? Ie, make the average (mean) number of times the prisoner enters the room be some constant K, while making sure that the probability that the prisoner enters the room at some point in the future at least once be 1?

Mean probably doesn't work. I could see having median be bounded might be possible.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A twist on the switch problem

Postby WarDaft » Fri Apr 15, 2011 6:28 pm UTC

sfwc wrote:It looks like despite my convoluted phraseology I wasn't clear enough about what I meant. The kind of situation I intended to exclude was one in which, for any particular name N of a strategy S for the prisoners, if we first calculate what strategy S' the warden will use against S and then calculate the probability that the prisoners will get out if they play S and the warden plays S', we'll get an answer which is at most p.

This calculation is made after we already know what strategy the prisoners are going to use, so it doesn't depend on knowing how likely it is that the prisoners would use any particular strategy. That's why considerations involving the Chaitin constant, which does rely on knowing something like that, can't arise. More precisely, there isn't just one Chaitin constant. To get a `Chaitin constant' you first need to specify some extra data, which roughly can be thought of as computably assigning to each (name of a) program a probability that that (name of a) program will be used.

I guess I need to work on my clarity.


The algorithm the prisoners will use will have to be unambiguously specified in some language they understand. Specifically, the prisoners must be sure that this really is a program, so it must be communicated in a language where each statement is decidedly either a program or not. Then, we can take every program unambiguously specified by that language, and determine the Chaitan constant for it.

Necessarily, the prisoners must be using a program that their side has not been able to prove to halt, otherwise the warden could prove it as well as the warden has time on their side. Selecting a program with some computable strategy from programs you cannot prove to halt in the time available should produce essentially the same likelihood of it halting as selecting one essentially at random from the same set of program.

Hmm. Can we exploit that? Ie, make the average (mean) number of times the prisoner enters the room be some constant K, while making sure that the probability that the prisoner enters the room at some point in the future at least once be 1?

Mean probably doesn't work. I could see having median be bounded might be possible.
While I am aware of no rule stating such, some tinkering in W|A seems to indicate most convergent sums of expected visits results in an overall chance of not visiting the room of greater than 0.

A potential exception is giving the prisoner n2 chances of 1/22 for each n > 0. This appears to have a 0 probability of never sending the prisoner in, while having a mean number of entrances of 6, but W|A doesn't have anything to say about the convergence of the product.

I guess I should have been clearer about this. A very simple (and not especially sensible) strategy for the warden would be to always pick a prisoner to enter the switch room at random. If they do that, then the probability that they meet the condition that no prisoner should be forever kept away from the switch room is 1. So they meet this condition almost surely, rather than surely. If we were very strict, and required the warden to surely meet this condition, we wouldn't allow that strategy (or others like it, such as those mentioned by WarDaft above) for the warden. But we don't have to be that strict.
Hmm... if we assume that this is not the case... that is, every prisoner not only returns to the room with probability 1, but is guaranteed to return to the room after some arbitrarily long period... then the warden has a system equivalent to unbounded nondeterminism.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: A twist on the switch problem

Postby sfwc » Sat Apr 16, 2011 10:29 am UTC

Yakk wrote:Mean probably doesn't work. I could see having median be bounded might be possible.

No, the median must be unbounded. Pick some prisoner (call them Bob) and some natural number N. Number all visits of prisoners to the switch room in time order. For each set S of natural numbers of size at most N, let E(S) be the event `The numbers of Bob's visits to the switch room are all in S'. By assumption, the probability of each E(S) is 0, and there are only countably many such events. So letting E be the union of these events, which is the event `Bob enters the switch room at most N times', we see that E also has probability 0. In particular, the probability that Bob enters the switch room more than N times is greater than 1/2, and so Bob's median number of visits to the switch room must be bigger than N. Since N was arbitrary, the median number of visits can't be finite.

WarDaft wrote:The algorithm the prisoners will use will have to be unambiguously specified in some language they understand. Specifically, the prisoners must be sure that this really is a program, so it must be communicated in a language where each statement is decidedly either a program or not. Then, we can take every program unambiguously specified by that language, and determine the Chaitan constant for it.

It's clear that I've still not managed to explain my claim sufficiently well, but I'm not even sure any more where the misunderstanding lies. I know it is irksome, but would you mind taking the time to read through what I have written once more and then explain in your own words what you think I am claiming, so that I can see where I haven't been clear?

WarDaft wrote:Necessarily, the prisoners must be using a program that their side has not been able to prove to halt, otherwise the warden could prove it as well as the warden has time on their side.

Not so. I am claiming a limitation on what the warden can do, not an ability that the prisoners have. So although in my arguments I mention potential strategies for the prisoners, I don't claim that any of those strategies are individually any good. In fact, my arguments explicitly deal with strategies which are terrible, and in which the prisoners know for sure that none of them will ever claim that they've alll visited the switch room.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A twist on the switch problem

Postby WarDaft » Sat Apr 16, 2011 4:29 pm UTC

It's clear that I've still not managed to explain my claim sufficiently well, but I'm not even sure any more where the misunderstanding lies. I know it is irksome, but would you mind taking the time to read through what I have written once more and then explain in your own words what you think I am claiming, so that I can see where I haven't been clear?
Okay, are you claiming that there is no minimum probability that the prisoners will fail, or that we cannot calculate it?

Not so. I am claiming a limitation on what the warden can do, not an ability that the prisoners have. So although in my arguments I mention potential strategies for the prisoners, I don't claim that any of those strategies are individually any good. In fact, my arguments explicitly deal with strategies which are terrible, and in which the prisoners know for sure that none of them will ever claim that they've alll visited the switch room.
We don't want them to know for sure though... because if they can know for sure, and the warden gets the same message, the warden can know for sure as well. The prisoners best bet lies in strategies that they honestly do not know about either way. This admits the chance that they have selected a program which does eventually halt but is very difficult to prove so, and that the warden will have taken all the prisoners to the room before realizing that it does actually halt. Strategies that they know to fail need not be included, because if they can discover it to fail, then so can the warden. Likewise, for any program they can know to halt, the warden can discover this as well.

Suppose I want to trip you up with a question about whether or not a program halts. The hardest I can make this question for you is to pick a program that I myself have not yet been able to decide either way.

Now, if we limit the warden's time for analysis, this does not apply, but no such limit was implied.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: A twist on the switch problem

Postby sfwc » Sat Apr 16, 2011 5:14 pm UTC

WarDaft wrote:Okay, are you claiming that there is no minimum probability that the prisoners will fail, or that we cannot calculate it?

`No minimum probability' comes closest to what I'm claiming. But I want to see what you think I'm claiming. Please take the trouble to explain what you think I'm saying, so that I can see what I need to explain better.

WarDaft wrote:We don't want them to know for sure though... because if they can know for sure, and the warden gets the same message, the warden can know for sure as well.

That isn't a problem. I'm not worried that the warden might beat the prisoners in some of the cases I mentioned, as long as he doesn't beat them in all those cases.

WarDaft wrote:Strategies that they know to fail need not be included, because if they can discover it to fail, then so can the warden.

Sure, but there's no harm in including them, and excluding them just makes the proof more technically complicated.

WarDaft wrote:Suppose I want to trip you up with a question about whether or not a program halts. The hardest I can make this question for you is to pick a program that I myself have not yet been able to decide either way.

Sure, but that's not the situation we're considering. It's not like I've challenged you to trip me up with such a question. It's more like I've claimed that whatever such question you asked I'd be able to answer it. Obviously, I'm lying, even if some of the questions you might ask are really easy. You don't need to actually trip me up to know that my claim is false.

WarDaft wrote:Now, if we limit the warden's time for analysis, this does not apply, but no such limit was implied.

You're right; I'm not imposing any such time limit.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 10 guests