Author |
Topic: Firing Squad Synchronization (Read 9797 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Firing Squad Synchronization
« on: Feb 4th, 2003, 9:01pm » |
 Quote  Modify
|
Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization Firing Squad Synchronization
A prisoner is awaiting execution by firing squad. A row of N robotic soldiers stands nearby.
These robotic soldiers can be in a finite number of states (they are all finite state machines). A clock provides a sequence of time steps: 0, 1, 2, etc.. At each step, the state of each soldier is given by a transition function. This function takes three arguments as input: the soldier's previous state, the previous state of the soldier to the right, and the previous state of the soldier to the left. The transition function must be identical for all soldiers except for the soldiers at the ends of the row, whom could have different transition functions.
One of the soldiers at one end of the row is deemed the general of the squad. Initially at time 0, the general is in state qinit, whereas all other soliders are in state qsleep. The objective is to get all soldiers to enter the state qbang simultaneously for the first time, thereby riddling the prisoner with N bullets.
Design state machines and transition functions for the robotic soldiers which will accomplish this objective, given that the number of states for a soldier cannot depend on N. What is the running time of your system in terms of N?
Hint (achievable running time): If your machines are sufficiently clever, you can achieve O(N) time! There's even a solution that takes exactly 2N - 2 time steps.
Note 1: If we did not specify "for the first time", a trivial solution would be to have all soldiers keep firing, and eventually they will all be in state qbang. Not an interesting problem.
Note 2: In a sense, the heart of this problem is that no soldier knows what N is.
Note 3: Problem originally posed by J. Myhill in 1957.
Note 4: This problem describes something called a cellular automaton. The soldiers are like "cells", and how a cell is updated depends on the state of nearby cells. Perhaps the most well-known cellular automaton is John Conway's Game of Life.
|
| « Last Edit: Feb 4th, 2003, 10:03pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
 |
Re: Firing Squad Synchronization
« Reply #1 on: Feb 5th, 2003, 6:35am » |
Quote Modify
|
WWU,
I’m not familiar with the formal definition of “finite state machines”. I thought of an algorithm, that allows getting to “fire” in 2n-1 cycles, but it require ~n states per robot. So it is finite, but may be very large. Is it acceptable?
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Firing Squad Synchronization
« Reply #2 on: Feb 5th, 2003, 9:27am » |
Quote Modify
|
<< Removed so not to confuse >>
|
| « Last Edit: Feb 5th, 2003, 11:52pm by BNC » |
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
poseur
Guest
|
|
Re: Firing Squad Synchronization
« Reply #3 on: Feb 5th, 2003, 11:36am » |
Quote Modify
 Remove
|
The simplest solution basically just counts to the right until you reach the end, then the right end starts a countdown that the rest synchronize to.
But what if the soldiers can't count that high. What if you want to solve it in the same length of time using the fewest different states possible?
I haven't figured this out yet, but the way I'm thinking is thus, this method synchronizes the first and last soldier using only a half dozen states, regardless of how many soldiers are in between:
The first soldier sets himself to state 1, and then state 3 and waits in that state till he gets the right signal back.
The middle soldiers set themselves to state 1 as soon as the soldier to the left is set. When that soldier becomes state 3, they set themselves to state 2 and then to state 3. That way the count of soldiers so far is propagated to the right as the length of time each soldier stays in state 1 or 2.
The last soldier sets himself to state 4 when the signal reaches him. When each soldier sees 4 or more to his right he adds 3 to his own state, to echo a signal back to the left.
When the second last soldier becomes a 5, the last soldier knows the echoed info has had time to get all the way back to the first soldier, and the 2 end soldiers could fire at the same time.
But I haven't figured out how to synchronize all the guys in the middle with the fewest possible states.
|
|
IP Logged |
|
|
|
poseur
Guest
|
|
Re: Firing Squad Synchronization
« Reply #4 on: Feb 5th, 2003, 12:03pm » |
Quote Modify
Remove
|
That might be confusing. Here's how their states look with 9 soldiers.
1SSSSSSSS
31SSSSSSS
321SSSSSS
3311SSSSS
33211SSSS
333111SSS
3332111SS
33331111S
333321114
333331144
333332444
333336444
333366544
333666644
336666654
366666664
*6666666*
When soldier 8 finishes an 8 count, the first and last soldiers can fire at the same time. Even with 1000 soldiers, you don't need to count higher than 6 to synchronize the ends in the minimum time possible. But can you syncrhonize the ones in the middle using a few more states and making the info echo around a little more?
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Firing Squad Synchronization
« Reply #5 on: Feb 5th, 2003, 1:54pm » |
Quote Modify
|
on Feb 5th, 2003, 9:27am, BNC wrote:OK, in case ~n states are allowed, here is my solution (in pseudo-code); In case it’s not, let me know and I will remove this message:
|
|
The problem states "Design state machines and transition functions for the robotic soldiers which will accomplish this objective, given that the number of states for a soldier cannot depend on N." So the number of states in a soldier cannot be "~n".
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Firing Squad Synchronization
« Reply #6 on: Feb 7th, 2003, 3:09am » |
Quote Modify
|
As the puzzle is worded, a solution would be that qinit -> qbang and qsleep -> qbang, independently of any inputs. Then everyone fires at time 1. You probably wanted to say something to prevent this.
I don't have a really great wording to suggest. Perhaps one way is to say that all the robots are in state qsleep at all times < 0, but the general has an extra boolean input that goes from F to T at time 0, and we are given that this stimulus takes his state from qsleep to qinit.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Firing Squad Synchronization
« Reply #7 on: Feb 7th, 2003, 12:01pm » |
Quote Modify
|
I think the best way to stop people from taking the easy way out is to make the following transition mandatory:
qsleep qsleep qsleep ==> qsleep
That is to say, soldiers must stay sleeping unless one of the soldiers beside them wakes up. This is probably what is meant by the "sleep" state anyways.
I have been thinking about the problem, and if we assume that the soldiers sleep until they are woken up by a soldier beside them, then counting per se won't do any good, because all you can determine is how far you are from the non-leader end of the line.
Of course, a single automaton cannot count up to N, but a group of automata can count up to N, because they can pool information. In fact, the whole puzzle is about gradually distributing information to all the automata. What I think should happen is that a large group of automata collectively knows that they must count down from 10 to zero, and then go bang. As the count gets smaller and smaller, smaller and smaller groups of automata must be able to count, until we reach the end, when every automata can realize with only its own inputs that it is time to enter the qbang state.
I have started to think about one type of solution that requires about O(NlogN) time. From examining the problem, I have decided that you can always dissect the soldiers into two equal-sized groups, each of which will take the same amount of time to reach qbang. Here's how I envision it:
1) The leader sends out two pulses in the positive direction. One pulse is encoded to travel at one soldier per step, and the other is encoded to travel at one soldier every three steps. The slower pulse is delayed by one time step. All soldiers are programmed to transmit the pulses at the same speed and in a consistent direction, except that the last soldier bounces the pulse back.
2) We dissect the line of soldiers by observing where these two pulses cross. There are two cases:
3) If there are an odd number of soldiers, then the pulses meet at the middle soldier. This soldier then transmits neither pulse, but instead starts the further subdivision of the line of soldiers (I'll explain this in step 5)
4) If there are an even number of soldiers, then the pulses never meet. However, the middle two soldiers will recognize that this happens, and will divide the list between them, the right one taking the right half, and the left one taking the left half.
5) The new leaders initiate the further subdivision of the lists by sending out pulses of speed 1 and speed 1/3 again. From now on, they act as reflectors of pulses, rather than transmitters.
6) When the the subdivided row of soldiers gets to be only 2 or 3 soldiers long, then the middle soldier (or in the case of only 2 soldiers, the "leader") will realize this, and immediately enter a qready, aim state. Because the subdivided row is so short, all soldiers will become aware of this, and will enter qfire in the next step.
I think that solves it, but I'm quite sure that it's not the best solution. However, I think it is an O(NlogN) solution, and although it has a lot of states, the number of states does not depend on N. Here's an example with 7 soldiers:
1 0 0 0 0 0 0
3 1 0 0 0 0 0
0 3 1 0 0 0 0
0 3 0 1 0 0 0
0 3 0 0 1 0 0
0 0 3 0 0 1 0
0 0 3 0 0 0 1
0 0 3 0 0 1 0
0 0 0 3 1 0 0
0 0 0 * 0 0 0
0 0 1 3 1 0 1
0 1 3 0 3 1 0
1 0 3 0 3 0 1
0 1 3 0 3 1 0
0 * * 0 * * 0
1 3 3 1 3 3 1
0 a a 0 a a 0
b b b b b b b
|
| « Last Edit: Feb 7th, 2003, 12:11pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Firing Squad Synchronization
« Reply #8 on: Feb 8th, 2003, 1:06am » |
Quote Modify
|
That sounds really good, James, though I haven't thought about it super hard yet. I had already thought of part of that idea too, but not enough to see where it was going -- I noticed that if the general sends out one full-speed pulse and one half-speed pulse, the latter reaches the other end of the line at the same time that the former comes back to the general, so this would synchronize the two ends of the line, but it doesn't help anyone in the middle. Then I started to think about where those pulses cross (it's at 2/3 of the way down the line), but I didn't get as far as adjusting the speed to make them meet in the middle.
Doesn't your solution take O(N) time, though? There are O(log N) phases, but each phase is twice as fast as the previous one. So maybe you have the optimal solution already.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Firing Squad Synchronization
« Reply #9 on: Feb 10th, 2003, 11:11am » |
Quote Modify
|
Tim,
I puzzled over that for a little while too, and eventually decided that it was O(NlogN), but perhaps I'd better come up with a justification one way or another. This will all be approximate.
It takes 1.5*N steps to divide the list in half, so
T(N) = T(N/2) + 1.5*N
Subdividing again, we get:
T(N) = T(N/4) + 1.5*N/2 + 1.5*N
eventually, we get down to only two or three automata, in which case it takes 2 or 3 moves:
T(N) = 2 + ... + 1.5*N/2 + 1.5*N = 3N
Wow! I guess that is only O(N). It takes a little longer if the row size is not a power of 2, and it certainly isn't 2N-2, but it's better than I thought! I think we can shave a move off of the end if the last cell size is 2, because both soldiers can realize at once that they will be entering the "bang" stage soon.
It seems like with this solution, we don't use all the information at our disposal. Specifically, the reflector at the end of the line could transmit a 1/3 speed signal to break up the second line quicker, but then we run into the problem that the first half of the list isn't broken up as quickly. To break the other half up in the same way, the leader has to send out a 1/7 speed signal. In order to get 2N-2 performance, we must also send out a 1/15 speed signal, a 1/31 signal, etc., but I haven't figured out a way to send all of these signals (if we don't send all of them, the row will not be synchronized). There must be some good way--if only I could think of it. Here is an example, with 1/3 and 1/7 speed signals, showing why we need a 1/15 speed signal too. You can see that most of the list is split up properly, but there is a section (in bold) that does not get split up when it should.
Also notice that the synchronization of these messages and the conditions for realizing that you are a new leader are rather complicated. I'm sure that a consistent set of rules could be made up, however. Probably that will all be part of the method of sending out 1/15 speed, 1/31 speed, etc. signals.
[font=courier][tt]
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0
7 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 3 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 7 3 0 0 1 0 0 0 0 0 0 0 0 0 0
0 7 3 0 0 0 1 0 0 0 0 0 0 0 0 0
0 7 3 0 0 0 0 1 0 0 0 0 0 0 0 0
0 7 0 3 0 0 0 0 1 0 0 0 0 0 0 0
0 7 0 3 0 0 0 0 0 1 0 0 0 0 0 0
0 7 0 3 0 0 0 0 0 0 1 0 0 0 0 0
0 0 7 0 3 0 0 0 0 0 0 1 0 0 0 0
0 0 7 0 3 0 0 0 0 0 0 0 1 0 0 0
0 0 7 0 3 0 0 0 0 0 0 0 0 1 0 0
0 0 7 0 0 3 0 0 0 0 0 0 0 0 1 0
0 0 7 0 0 3 0 0 0 0 0 0 0 0 0 1
0 0 7 0 0 3 0 0 0 0 0 0 0 0 1 3
0 0 7 0 0 0 3 0 0 0 0 0 0 1 3 7
0 0 0 7 0 0 3 0 0 0 0 0 1 0 3 7
0 0 0 7 0 0 3 0 0 0 0 1 0 0 3 0
0 0 0 7 0 0 0 3 0 0 1 0 0 3 7 0
0 0 0 7 0 0 0 3 0 1 0 0 0 3 7 0
0 0 0 7 0 0 0 3 1 0 0 0 0 3 7 0
0 0 0 7 0 0 0 * * 1 0 0 3 0 7 0
0 0 0 7 0 0 1 3 3 1 0 0 3 0 7 0
0 0 0 0 7 1 3 7 7 3 1 0 3 0 7 0
0 0 0 0 1 0 3 7 7 3 0 1 3 7 0 0
0 0 0 * * 0 3 0 0 3 0 * * 7 0 0
0 0 1 3 3 1 7 0 0 7 1 3 3 1 0 0
0 1 3 7 7 * * 0 0 * * 7 7 * * 0
b 0 3 7 b b b b b b b b b b b b
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Firing Squad Synchronization
« Reply #10 on: Feb 10th, 2003, 1:58pm » |
Quote Modify
|
I've figured out how to send all the 1/3, 1/7, 1/15, etc speed messages. Here's how you do it:
1) Each message has two states, a "passive" and an "active" state. The state changes whenever the message is passed to the next soldier. The message with speed 1 also has these active and passive states. A leader always holds passive messages.
2) When a message is in an active state, then the soldier holding the message releases an active back-message (that travels with speed 1 in the reverse direction) simultaneously with passing the message on to the next soldier in line. When a message is in a passive state, a passive back-message is sent.
3) The speed-1 message always goes forward with speed 1, but the slower messages only go forward when the current soldier recieves an active back-message.
4) The passive back-messages are used to figure out whether a new leader is responsible for one or two different sub-rows (in other words, if the row had even or odd length, etc.)
5) Note that the active back-messages are, on average, propogated backwards half of the time, and the passive back-messages are never propogated backwards. This achieves the speed-halving effect that we were looking for. Also note that the soldiers do not need to know at what speed the message they are carrying is supposed to travel. They just pass it on when they get a back-message.
6) Further note that the leader always has a passive message to send, whereas other soldiers may have no message at a given point in time, so they will sleep, waiting until they receive a message they should pass on.
Now I will detail the entire solution one more time:
1) There are two types of soldiers: leaders and non-leaders (actually, the last soldier in line is a third type--a leader in limbo). Leaders have the job of generating messages to pass down the line. A leader starts in the qinit state, in which it sends a single passive speed-1 message, and enters the qtransmit state, in which it hands off a new passive message every time it receives a back-message. A leader enters the qbang state as soon as a soldier near it enters the qready,aim state.
2) A non-leader soldier accepts messages of all types, and passes them down the line. If the message is in an active state, then the soldier releases a back-message as it passes the message on. A non-leader enters the qready,aim state instead of receiving a speed-1 message that it would be asked to passed to a leader. A non-leader always enters the qbang state when in the qready,aim state.
3) A non-leader soldier becomes a leader instead of receiving a speed-1 message if it already has another message (or just passed one on last turn), or when the soldier before it has a message and has received a passive back-message before one turn ago. If is is an "early" leader, meaning that it received its speed-1 message before (or less than 1 turn after) it received a passive back-message then it becomes a left-right-leader. Otherwise it becomes a leader only in the direction in which the speed-1 message was travelling (either a left-leader or a right-leader). A soldier beside it will become the leader in the other direction. The new leader is initially in the qinit,left, qinit,right, or qinit,both states.
4) Upon becoming a leader, the soldier sends out a speed-1 message in the directions for which it is responsible, then enters a transmit state, similar to other leaders.
I think that pretty much sums it up. I would do an example here, but I fear it would take up too much space. Oh, what the heck! Here we go:
Legend:
0 = sleep state
1 = passive speed-1 message
2 = active speed-1 message
A = active message
P = passive message
a = active back-message
p = passive back-message
* = soldier becomes leader, qinit
T = qtransmit
R = qready,aim
B = qbang
(note that directions for messages are not shown--you'll have to figure them out)
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
* 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
T 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
T 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
T A 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
T A a 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
T A 0 p 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
T 0 P 0 a 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
T A P a 0 p 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0
T A P 0 p 0 a 0 1 0 0 0 0 0 0 0 0 0 0 0 0
T A 0 A 0 a 0 p 0 2 0 0 0 0 0 0 0 0 0 0 0
T A 0 A a 0 p 0 a 0 1 0 0 0 0 0 0 0 0 0 0
T A 0 A 0 p 0 a 0 p 0 2 0 0 0 0 0 0 0 0 0
T A a 0 P 0 a 0 p 0 a 0 1 0 0 0 0 0 0 0 0
T A 0 0 P a 0 p 0 a 0 p 0 2 0 0 0 0 0 0 0
T 0 P 0 P 0 p 0 a 0 p 0 a 0 1 0 0 0 0 0 0
T A P p 0 A 0 a 0 p 0 a 0 p 0 2 0 0 0 0 0
T A P 0 0 A a 0 p 0 a 0 p 0 a 0 1 0 0 0 0
T A P 0 0 A 0 p 0 a 0 p 0 a 0 p 0 2 0 0 0
T A P 0 a 0 P 0 a 0 p 0 a 0 p 0 a 0 1 0 0
T A P a 0 0 P a 0 p 0 a 0 p 0 a 0 p 0 2 0
T A P 0 0 0 P 0 p 0 a 0 p 0 a 0 p 0 a 0 *
T A 0 A 0 p 0 A 0 a 0 p 0 a 0 p 0 a 0 2 T
T A 0 A p 0 0 A a 0 p 0 a 0 p 0 a 0 1 0 T
T A 0 A 0 0 0 A 0 p 0 a 0 p 0 a 0 2 0 A T
T A 0 A 0 0 a 0 P 0 a 0 p 0 a 0 1 0 a A T
T A 0 A 0 a 0 0 P a 0 p 0 a 0 2 0 p 0 A T
T A 0 A a 0 0 0 P 0 p 0 a 0 1 0 a 0 P 0 T
T A 0 A 0 0 0 p 0 A 0 a 0 2 0 p 0 a P A T
T A a 0 P 0 p 0 0 A a 0 1 0 a 0 p 0 P A T
T A 0 0 P p 0 0 0 A 0 2 0 p 0 a 0 A 0 A T
T 0 P 0 P 0 0 0 a 0 * 0 a 0 p 0 a A 0 A T
T A P 0 P 0 0 a 0 2 T 2 0 a 0 p 0 A 0 A T
T A P 0 P 0 a 0 1 0 T 0 1 0 a 0 P 0 a A T
T A P 0 P a 0 2 0 A T A 0 2 0 a P 0 0 A T
T A P 0 P 0 1 0 a A T A 0 0 1 0 P 0 P 0 T
T A P p 0 * 0 p 0 A T A 0 0 0 * 0 p P A T
T A P 0 2 T 2 0 P 0 T 0 P 0 2 T 2 0 P A T
T A P 1 0 T 0 1 P A T A P 1 0 T 0 1 P A T
T A * * A T A * * A T A * * A T A * * A T
T R T T R T R T T R T R T T R T R T T R T
B B B B B B B B B B B B B B B B B B B B B
TADA! It takes 2N-2 turns! Now all we have to do is implement it and see if it really works!
|
| « Last Edit: Feb 12th, 2003, 11:27am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Firing Squad Synchronization
« Reply #11 on: Feb 12th, 2003, 11:25am » |
Quote Modify
|
I got it working on a spreadsheet! And yes, it does have 2N-2 performance...The logic is a little messy, but I got it working on a size-12 row, found a couple more mistakes testing it on a size-41 row, and then it worked perfectly, first time, on a size-64 row. Anything bigger bogs down my computer too much (stupid spreadsheet program... the size-64 row only took 123 000 cells)
The end-of-the-line soldiers are exactly the same as other soldiers, except that they are set to a different initial state, and have half of their inputs reading zero permanently (because there's nobody there).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Firing Squad Synchronization
« Reply #12 on: Feb 12th, 2003, 7:10pm » |
Quote Modify
|
Shouldn't implementing a known solution be pretty easy? Figuring out the solution seems like he hard part. Just make a table defining the new state given the previous state and that of its neighbors. If there are N possible states, the center soldiers would need an N by N by N table, and the end soldiers would need an N by N table.
James F, that is a clever method of sending signals, but it is not clear to me how this is implemented with the soldiers as finite state machines. Does your spreadsheet use tables to define each new state from the previous state? How many different states are needed?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Firing Squad Synchronization
« Reply #13 on: Feb 12th, 2003, 11:42pm » |
Quote Modify
|
I'd guess 11 states, namely the eleven he wrote down in his legend above his example three posts up..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Firing Squad Synchronization
« Reply #14 on: Feb 17th, 2003, 10:58am » |
Quote Modify
|
SWF,
The solution I presented requires a fairly large number of states, but it certainly can be implemented using finite state machines. After a little bit more optimization, here's what I ended up with:
Define a soldier as a finite state machine, with the following properties:
1) It has a "leader" state, which stores whether or not it is a leader, and if so, in which direction(s). It also keeps track of leaders-in-waiting, first-time leaders, and whether or not the soldier is firing.
2) It has a "speed-1 message" state, which stores whether or not it is sending any speed-1 messages, and if so, in which direction(s).
3) It has a "normal message" state, which stores whether or not it is holding/sending any normal messages, and if so, in which direction(s). This also keeps track of how many back-messages it has received.
4) It has a "back-message" state, which stores whether or not it is sending a back-message, and if so, in which direction.
Note that I abandoned the ideas of "active" and "passive" messages in favour of a back-message counter system. It's much simpler this way.
At each time step, first decide on the "leader" status of the soldier. This depends on leader status, speed-1 message status, and message status of the soldier and its neighbours from the previous time step. The conditions are fairly complex for this.
Next, decide on the speed-1 message state. This depends on the soldier's own new leader status for this turn, and its neighbours' speed-1 message states from the previous time step.
Now, decide on the message state. This one is fairly complicated, and depends on the soldier's own new leader status and the message and back-message states of the soldier and its neighbours from the previous time step.
Finally, decide on your back-message state. For simplicity, this depends on the soldier's own new leader, speed-1 message and message states, and also on the back-message states of the soldier's neighbours from the previous time step.
Although it seemed straightforward when I started, some of these conditions are a little persnickety.
I defined 17*4*16*3 = 3264 states in total, but in a medium-sized row of soldiers, I only found 37 distinct states that the soldiers had in practise. There could be a few more that my trial did not find, but the problem is likely solvable with fewer states than this (especially since I know a few of these are completely unnecessary states).
<edit>
I think it can be done with exactly 20 states.
|
| « Last Edit: Feb 17th, 2003, 12:05pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Firing Squad Synchronization
« Reply #15 on: Dec 30th, 2003, 12:50pm » |
Quote Modify
|
Here is an exhaustive list of states and transitions for my solution (simplified and distilled a number of times). It requires 16 distinct states. Unless I screwed this up, it should fully define my solution, and be implementable.
Define a soldier as having the following possible states:
0 - sleep mode
1 - leader
2 - leader, sending speed-1
3 - leader-in-waiting (sleep mode for the soldier at the end of the line)
4 - non-leader, sending speed-1 right (and bm left)
5 - non-leader, sending speed-1 left (and bm right)
6 - non-leader, holding right
7 - non-leader, holding right, just got bm
8 - non-leader, holding right, stale bm
9 - non-leader, transmitting right (and bm left)
10 - non-leader, holding left
11 - non-leader, holding left, just got bm
12 - non-leader, holding left, stale bm
13 - non-leader, transmitting left (and bm right)
14 - non-leader, sending bm left
15 - non-leader, sending bm right
16 - fire!
The soldier to the left is "L" and the soldier to the right is "R". The "==>" notation indicates the state for the next turn. Sometimes there are two transitions specified from a given condition; use the more specific one (I have tried to list these first, but forgive me if I missed a couple). If no transition applies, the current state is the state for the next turn. The soldier at the starting end of the line begins in state 2, and the leader at the opposite end begins in state 3.
Note that the leader directions were only required (in non-simplified versions of this solution) so that leaders do not fire when they see another leader beside them (since two leaders can be created simultaneously side-by-side). But we could guard against this by triggering ONLY if we see a leader beside us that is in a different state (either transmitting a speed-1 when we are not, or not transmitting a speed-1 when we are).
From state 0:
if (L in {2,4}) and (R in {1,2,13}) ==> 2
if (R in {2,5}) and (L in {1,2,9}) ==> 2
(if receiving a speed-1 from one side, and a regular message from the other, or if the other side is a leader, it is time to become a leader)
if L in {2,4} ==> 4
if R in {2,5} ==> 5
(otherwise, if receiving a speed-1, just pass it on)
if (L in {15,13,5}) and (R in {1,13}) ==> 11
if (R in {14,9,4}) and (L in {1,9}) ==> 7
(if receiving a regular message from one side and a back-message from the other, accept the back-message immediately, bypassing state 6 or 10)
if L in {1,9} ==> 6
if L in {15,13,5} ==> 15
if R in {1,13} ==> 10
if R in {14,9,4} ==> 14
(accept regular and back-messages)
From state 1:
if (R in {2}) or (L in {2}) ==> 16
(a leader always fires if beside another leader who's not synchronized)
From state 2:
if (R in {1}) or (L in {1}) ==> 16
(a leader always fires if beside another leader who's not synchronized)
else ==> 1
(you are done sending your first and only speed-1. Now you are just a leader)
From state 3:
if (L in {2,4}) or (R in {2,5}) ==> 2
(awake ye soldier at the far end of the line. It is time to fulfill your destiny as a leader!)
From state 4:
if R in {12,13} ==> 2
(if you are trying to send a speed-1 to a soldier who has a stale message or is trying to send you a message, then you two should both become leaders)
else ==> 0
(otherwise, you have nothing else to do for now, so go to sleep)
From state 5:
if L in {8,9} ==> 2
(if you are trying to send a speed-1 to a soldier who has a stale message or is trying to send you a message, then you two should both become leaders)
else ==> 0
(otherwise, you have nothing else to do for now, so go to sleep)
From state 6:
if R in {2,5} ==> 2
(if you receive a speed-1 while holding a regular message, then congratulations! you are now a leader!)
if R in {14,9,4} ==> 7
(If you receive a back-message while holding a regular message, then note that to yourself. After you get another back-message, you can transmit!)
From state 7:
if R in {2,5} ==> 2
(if you receive a speed-1 while holding a regular message, even if you just received a back-message, then congratulations! you are now a leader!)
else ==> 8
(so you didn't get a speed-1 in time. If you get a speed-1 now before the next back-message, you can still be a leader, but you'll have to share)
From state 8:
if R in {5} ==> 2
(if you get a speed-1 message now, you become a leader, but so does the person who gave you the speed-1)
if R in {14,9,4} ==> 9
(you got another back-message! go ahead and transmit)
From state 9:
if R in {5} ==> 2
(if you get a speed-1 message now, you become a leader, but so does the person who gave you the speed-1)
else ==> 0
(otherwise, you have nothing else to do for now, so go to sleep)
From state 10:
if L in {2,4} ==> 2
(if you receive a speed-1 while holding a regular message, then congratulations! you are now a leader!)
if L in {15,13,5} ==> 8
(If you receive a back-message while holding a regular message, then note that to yourself. After you get another back-message, you can transmit!)
From state 11:
if L in {2,5} ==> 2
(if you receive a speed-1 while holding a regular message, even if you just got a back-message, then congratulations! you are now a leader!)
else ==> 12
(so you didn't get a speed-1 in time. If you get a speed-1 now before the next back-message, you can still be a leader, but you'll have to share)
From state 12:
if L in {4} ==> 2
(if you get a speed-1 message now, you become a leader, but so does the person who gave you the speed-1)
if L in {15,13,5} ==> 13
(you got another back-message! go ahead and transmit)
From state 13:
if L in {4} ==> 4
(if you get a speed-1 message now, you become a leader, but so does the person who gave you the speed-1)
else ==> 0
(otherwise, you have nothing else to do for now, so go to sleep)
From state 14:
if R in {2,5} ==> 5
(if you get a speed-1 message, send it on immediately)
else ==> 0
(otherwise, you have nothing else to do for now, so go to sleep)
From state 15:
if L in {4,6,4} ==> 4
(if you get a speed-1 message, send it on immediately)
else ==> 0
(otherwise, you have nothing else to do for now, so go to sleep)
From state 16:
==> 0
(well you just went and shot the guy didn't you! Might as well go back to sleep)
<edit> I have since simplified this down to 13 states, because we don't need the soldier to remember which direction he got the regular message in (effectively eliminating states 10 - 12). It doesn't reduce the amount of logic, though. </edit>
|
| « Last Edit: Dec 31st, 2003, 4:45am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
godskook
Guest
|
|
Re: Firing Squad Synchronization
« Reply #16 on: Jan 26th, 2004, 11:20am » |
Quote Modify
Remove
|
I assumed two things when solving this riddle.
First, that robots in the qsleep state were allowed to function before receiving a command from the commander(but not fire without permission)
Second, that all robots are aware of, and able to record the current clock time.
using the first assumtion, I had the robot directly opposite the commander send a counting report towards the commander at t=0
the sequence for my solution is as follows
robot states
0=no robot
1=sleep
2=report
3=command
4=countdown
5=fire
stage one: initialize
0111...1110
Stage two: messages being sent
03333111......11122220
Stage three: intersection
Case 1: N is even
033...3322...220
Case 2: N is odd
033...312...220
Stage four: countdown
033334444....444422220
Stage five: fire
05555......55550
In this model the robots do not fire unless ordered to by the commander. When ordered they will fire approximately N clock ticks after the order is first given.
If my assumtions are flawed then this falls apart, otherwise I presume that I have found the opitmal solution.
|
|
IP Logged |
|
|
|
Smasher
Guest
|
|
Re: Firing Squad Synchronization
« Reply #17 on: Mar 2nd, 2005, 12:48am » |
Quote Modify
Remove
|
Your solution requires the robots to be able to count up to N, which means they must have at least N states, which is prohibited by the terms of the problem.
|
|
IP Logged |
|
|
|
Lou Filliger
Guest
|
|
Re: Firing Squad Synchronization
« Reply #18 on: Sep 13th, 2005, 6:06pm » |
Quote Modify
Remove
|
 Regarding the firing squad problem, the soldier may have a finite number of states (call this S) not dependent on N. Can the problem be divided into a series of problems where S = 1,2,....<<N for large N.
When I first read about this problem in Feynman's computing book, I assumed that S was 2 (rifle up, ready to shoot, or rifle down). Now I read on this forum that people let S increase apparently without bound. It seems to defeat the purpose of the problem - since it's a computing problem, we want to remain as close to binary as possible, no? Each soldier being only a bit.
What was the original intention of the author of the problem, as to how many states would be permitted?
Thanks
|
|
IP Logged |
|
|
|
Lou Filliger
Guest
|
|
Re: Firing Squad Synchronization
« Reply #19 on: Sep 15th, 2005, 5:46pm » |
Quote Modify
Remove
|
Another thought while I'm waiting for a response - if these soldiers are robots, why do you need N of them? Shouldn't one robot be able to hit a precise target every time? If not, they ought to devote the extra time and energy to building better robots, not solving these ridiculous math problems.....
|
|
IP Logged |
|
|
|
asterex
Guest
|
|
Re: Firing Squad Synchronization
« Reply #20 on: Sep 15th, 2005, 6:29pm » |
Quote Modify
Remove
|
The point of a finite state machine is that you can specify the number of states it can be in, and that same number will be sufficient no matter how large the problem is scaled. So James Fingas has described a 16 state machine that should be capable of synchronizing the firing whether there are ten robots or ten million robots.
It's true that a solution that requires fewer states would be considered better, but any number of states is permissible, as long as it is not in any way dependent on N.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print