In "Lectures on Computation", Richard Feynman discusses the firing
squad problem: an array of finite state machines ('soldiers'), length
N,
receives a start pulse at one end (the 'Fire!' command), which is
then
transmitted down the line.  Later, they must all fire in unison (each
soldier has one bullet).  The goal is to make this happen in minimum
time.

He alludes to it as a known problem, though it's new to me.

The purported solutions range from 3N to 8N clock ticks.  I have
found a solution which has an upper bound of 3N.  It seems optimal
to me, though I cannot prove it (probably no such proof exists).

Feynman admits he failed to solve it, and that someone has supposedly
devised a design which runs in time 2N.  I disbelieve this; I think
he's
mistaken, or misinformed.

Can anyone confirm a 2N solution?  Or provide an impossibility proof?


---
Paul T.

PT wrote:
> 
> In "Lectures on Computation", Richard Feynman discusses the firing
> squad problem: an array of finite state machines ('soldiers'),
> length N, receives a start pulse at one end (the 'Fire!' command),
> which is then transmitted down the line.  Later, they must all
> fire in unison (each soldier has one bullet).  The goal is to make
> this happen in minimum time.
> 
> He alludes to it as a known problem, though it's new to me.
> 
> The purported solutions range from 3N to 8N clock ticks.  I have
> found a solution which has an upper bound of 3N.  It seems optimal
> to me, though I cannot prove it (probably no such proof exists).
> 
> Feynman admits he failed to solve it, and that someone has
> supposedly devised a design which runs in time 2N.  I disbelieve
> this; I think he's mistaken, or misinformed.
> 
> Can anyone confirm a 2N solution?  Or provide an impossibility
> proof?

Easy.  At the start end, the 1st soldier receives a count of 0, and
passes on a count of 1, i.e. n+1.  Etc, until the end soldier
receives the value of N.  This has taken N clocks.  Now the end
soldier passes back N-1, and remembers N.  N, to him, now means
fire after N more clocks.  This is repeated up the line, each
passing back received N-1.  When the result arrives at the first
soldier, they all fire.  Elapsed time, 2N.

If the first soldier knows the value of N it can be reduced to time
N.

I suspect you have omitted some condition.  Feynman would have had
no problem with that.

-- 
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: <http://cbfalconer.home.att.net>
            Try the download section.


-- 
Posted via a free Usenet account from http://www.teranews.com

CBFalconer wrote:
> PT wrote:
>> In "Lectures on Computation", Richard Feynman discusses the firing
>> squad problem: an array of finite state machines ('soldiers'),
>> length N, receives a start pulse at one end (the 'Fire!' command),
>> which is then transmitted down the line.  Later, they must all
>> fire in unison (each soldier has one bullet).  The goal is to make
>> this happen in minimum time.
>>
>> He alludes to it as a known problem, though it's new to me.
>>
>> The purported solutions range from 3N to 8N clock ticks.  I have
>> found a solution which has an upper bound of 3N.  It seems optimal
>> to me, though I cannot prove it (probably no such proof exists).
>>
>> Feynman admits he failed to solve it, and that someone has
>> supposedly devised a design which runs in time 2N.  I disbelieve
>> this; I think he's mistaken, or misinformed.
>>
>> Can anyone confirm a 2N solution?  Or provide an impossibility
>> proof?
> 
> Easy.  At the start end, the 1st soldier receives a count of 0, and
> passes on a count of 1, i.e. n+1.  Etc, until the end soldier
> receives the value of N.  This has taken N clocks.  Now the end
> soldier passes back N-1, and remembers N.  N, to him, now means
> fire after N more clocks.  This is repeated up the line, each
> passing back received N-1.  When the result arrives at the first
> soldier, they all fire.  Elapsed time, 2N.
> 
> If the first soldier knows the value of N it can be reduced to time
> N.
> 
> I suspect you have omitted some condition.  Feynman would have had
> no problem with that.

     Seems to me the additional condition was probably about the
nature of the soldier-to-soldier signal: If a soldier can pass
only a "pulse," not a number, the problem gets harder.  (The
dodge of passing a number by emitting a train of pulses works
but takes inordinate time, since it takes N pulses plus one
blank space, or N+1 clocks, to transmit the number.  Fancier
encodings might be used, but I don't see how they could crack
the lg(N) barrier, which wouldn't lead to 2N  solution from
the transmit-a-count strategy.)

     Question: Can a soldier "pulse" to his right and left
independently, or is every "pulse" received by both neighbors?
At first blush, the latter case appears insoluble -- but my
intuition falls somewhat short of omniscience ...

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

PT <ptanenbaum@consultant.com> writes:

> In "Lectures on Computation", Richard Feynman discusses the firing
> squad problem: an array of finite state machines ('soldiers'), length
> N,
> receives a start pulse at one end (the 'Fire!' command), which is
> then
> transmitted down the line.  Later, they must all fire in unison (each
> soldier has one bullet).  The goal is to make this happen in minimum
> time.
> [ ... ]

Googling for "firing squad problem" is the fastest way to
get a solution; of the references that turns up, 
   http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem
and
   http://www.stanford.edu/~jcackler/automata/problem.htm
look pretty useful.

(Spoiler: According to the second reference, the best
and provably minimal solution has N-2 steps and 6 states per
DFA.)


-- 
Mark Jeffcoat
Austin, TX

On Mar 3, CBFalconer <cbfalco...@yahoo.com> wrote:
> > In "Lectures on Computation", Richard Feynman discusses the firing
> > squad problem: an array of finite state machines ('soldiers'),
> > length N, receives a start pulse at one end (the 'Fire!' command),
> > which is then transmitted down the line.  Later, they must all
> > fire in unison (each soldier has one bullet).  The goal is to make
> > this happen in minimum time.
>
> > He alludes to it as a known problem, though it's new to me.
>
> > The purported solutions range from 3N to 8N clock ticks.  I have
> > found a solution which has an upper bound of 3N.  It seems optimal
> > to me, though I cannot prove it (probably no such proof exists).
>
> > Feynman admits he failed to solve it, and that someone has
> > supposedly devised a design which runs in time 2N.  I disbelieve
> > this; I think he's mistaken, or misinformed.
>
> > Can anyone confirm a 2N solution?  Or provide an impossibility
> > proof?
>
> Easy.  At the start end, the 1st soldier receives a count
> of 0, and passes on a count of 1, i.e. n+1.  Etc, until the
> end soldier receives the value of N...
>
> If the first soldier knows the value of N it can be reduced
> to time N.

N is not specified until run time, and can
be arbitrarily large.  The solution must work
for any value of N.

---
Paul T.

On Mar 3, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> >> In "Lectures on Computation", Richard Feynman discusses the firing
> >> squad problem: an array of finite state machines ('soldiers'),
> >> length N, receives a start pulse at one end (the 'Fire!' command),
> >> which is then transmitted down the line.  Later, they must all
> >> fire in unison (each soldier has one bullet).  The goal is to make
> >> this happen in minimum time.
>
> >> The purported solutions range from 3N to 8N clock ticks.  I have
> >> found a solution which has an upper bound of 3N.  It seems optimal
> >> to me, though I cannot prove it (probably no such proof exists).
>
> >> ... someone has supposedly devised a design which
> >> runs in time 2N.  I disbelieve this;
>
> >> Can anyone confirm a 2N solution?  Or provide an impossibility
> >> proof?
.....
> > I suspect you have omitted some condition.  Feynman would have had
> > no problem with that.
>
>    Seems to me the additional condition was probably about the
> nature of the soldier-to-soldier signal: If a soldier can pass
> only a "pulse," not a number, the problem gets harder.  (The
> dodge of passing a number by emitting a train of pulses works
> but takes inordinate time, since it takes N pulses plus one
> blank space, or N+1 clocks, to transmit the number.  Fancier
> encodings might be used, but I don't see how they could crack
> the lg(N) barrier, which wouldn't lead to 2N  solution from
> the transmit-a-count strategy.)

Your observation re encoding is cogent,
but not really germane.  N is unknown,
that's the point.


>  Question: Can a soldier "pulse" to his right and left
> independently, or is every "pulse" received by both neighbors?

You can have any number of input/output
lines to each side, acting independently.
It's your canonical state machine.

The conditions are:
o   It's a discrete time system.
o   Every soldier is identical.
o   Each soldier communicates only
     with his left and right neighbor.
o   N is unspecified, and arbitrarily large.
    A soldier does not know N, or even his
    own position in line.


The last is the real sticky wicky.

One more thing: the right end soldier
needs to recognize his position, somehow.
Therefore, there must exist an input "you
are the right end", which is activated
externally at start up.  Feynman does not
mention this, but I believe it's necessary.


---
Paul T.

On Mar 3, PT <ptanenb...@consultant.com> wrote:
> The conditions are:
> o   It's a discrete time system.
> o   Every soldier is identical.
> o   Each soldier communicates only
>      with his left and right neighbor.
> o   N is unspecified, and arbitrarily large.
>     A soldier does not know N, or even his
>     own position in line.

For extra credit, you might try to minimize
the number of I/O lines.


--
Paul T.

"CBFalconer" <cbfalconer@yahoo.com> wrote in message 
news:47CCC397.A4E578F3@yahoo.com...
| PT wrote:
| >
| > In "Lectures on Computation", Richard Feynman discusses the firing
| > squad problem: an array of finite state machines ('soldiers'),
| > length N, receives a start pulse at one end (the 'Fire!' command),
| > which is then transmitted down the line.  Later, they must all
| > fire in unison (each soldier has one bullet).  The goal is to make
| > this happen in minimum time.
| >
| > He alludes to it as a known problem, though it's new to me.
| >
| > The purported solutions range from 3N to 8N clock ticks.  I have
| > found a solution which has an upper bound of 3N.  It seems optimal
| > to me, though I cannot prove it (probably no such proof exists).
| >
| > Feynman admits he failed to solve it, and that someone has
| > supposedly devised a design which runs in time 2N.  I disbelieve
| > this; I think he's mistaken, or misinformed.
| >
| > Can anyone confirm a 2N solution?  Or provide an impossibility
| > proof?
|
| Easy.  At the start end, the 1st soldier receives a count of 0, and
| passes on a count of 1, i.e. n+1.  Etc, until the end soldier
| receives the value of N.  This has taken N clocks.  Now the end
| soldier passes back N-1, and remembers N.  N, to him, now means
| fire after N more clocks.  This is repeated up the line, each
| passing back received N-1.  When the result arrives at the first
| soldier, they all fire.  Elapsed time, 2N.
|
| If the first soldier knows the value of N it can be reduced to time
| N.
|
| I suspect you have omitted some condition.  Feynman would have had
| no problem with that.

You are making the assumption that each soldier has an independent
clock tick that he can count and all you did was find a value for N.

Try to solve it realistically -- as in there really is a line of soldiers,
they do not have clocks or watches, only guns and elbows to nudge
the next soldier.

With one soldier - he fires when nudged.
With  two soldiers the general nudges soldier 1, soldier 1 nudges
soldier 2 who has nobody to nudge to his right and so he nudges
left and fires. Soldier 1 gets a nudge from the right and fires.
Problem: Is there a time interval between nudge and fire?

CBFalconer <cbfalconer@yahoo.com> wrote:

} PT wrote:
} > 
} > In "Lectures on Computation", Richard Feynman discusses the firing
} > squad problem: an array of finite state machines ('soldiers'),
} > length N, receives a start pulse at one end (the 'Fire!' command),
} > which is then transmitted down the line.

} Easy.  At the start end, the 1st soldier receives a count of 0, and
} passes on a count of 1, i.e. n+1.  Etc, until the end soldier
} receives the value of N.

Alas, not so easy -- you can't do that with a finite state machine.
[how many states does your FSM have?  and what if there are many more
soldiers than that? -- you can't store an arbitrary number in an FSM!]

We worked that problem in a course I took decades ago on automata theory
and the solution involved "division by 2".  NB: the details here are
*incorrect* [I can't remember all of it] and the details can be fixed for
an arbitrary # of soldiers, but this'll give you the idea for how you solve
the problem: for the moment [so you can see how it goes] assume you have
2^N - 1 soldiers.

What you do is send *TWO* signals down the line, one moving three times as
fast as the other and the fast signal "bounces" off of the end.  At some
point the two signals will arrive in opposite directions at some soldier.
This soldier is "in the middle".  That soldier then sends two sets of the
two signals, one in each direction, and marks himself an "end soldier" [and
so begins reflecting].  If you receive both signals at the same time, you
send that neighbor a "shoot now" signal and you shoot on the next click.  

A variation on this, that we worked on and is pretty interesting is to have
an unbounded line of FSM soldiers.  What you need to do is figure out how
to design the FSMs so that the soldier at the start of the line fires his
rifle at *prime*numbered* clock ticks [and only prime numbered ones].  It
isn't too hard once you understand how the firing-squad problem works....

  /Bernie\
-- 
Bernie Cosell                     Fantasy Farm Fibers
bernie@fantasyfarm.com            Pearisburg, VA
    -->  Too many people, too few sheep  <--          

On Mar 3, 8:00=A0pm, PT <ptanenb...@consultant.com> wrote:
> In "Lectures on Computation", Richard Feynman discusses the firing
> squad problem: an array of finite state machines ('soldiers'), length
> N,
> receives a start pulse at one end (the 'Fire!' command), which is
> then
> transmitted down the line. =A0Later, they must all fire in unison (each
> soldier has one bullet). =A0The goal is to make this happen in minimum
> time.
>
> He alludes to it as a known problem, though it's new to me.
>
> The purported solutions range from 3N to 8N clock ticks. =A0I have
> found a solution which has an upper bound of 3N. =A0It seems optimal
> to me, though I cannot prove it (probably no such proof exists).
>
> Feynman admits he failed to solve it, and that someone has supposedly
> devised a design which runs in time 2N. =A0I disbelieve this; I think
> he's
> mistaken, or misinformed.
>
> Can anyone confirm a 2N solution? =A0Or provide an impossibility proof?
>
> ---
> Paul T.

A fire signal was heard only from the next soldier in line.  As they
stand to fire in unison as count was all that was transmitted first.
So they count to N.  And the last man waits for N time to pass until
shooting.  Each man knows his count and wait a period less.  All that
was required was a count as a message. So the timing was understood.

So  "one", "two", "three"  ... "N"

So N waits N clock ticks. N-1 wait N-1 clock ticks...........  And the
first guy never knows the end number?  So the second traveling order
was required!

2N is the first undoadle ordering method.  It is not solvable because

(N-placenumber) was not the first order.  So reverse and send a
meassage down the time line.  One second, "two seconds", "three
seconds"....... Fifteen seconds(say).  On fftteen the applied
elemental transform was to be used and the message was firing delay
for the next soldier

"fourteen(said by fifteen),"thirteen","twelve",  ..... "one" is said
to one position in 2n

You can not say a position number as the travel back order!!!!!!!

PT wrote:
> Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
>
>>>> In "Lectures on Computation", Richard Feynman discusses the
>>>> firing squad problem: an array of finite state machines
>>>> ('soldiers'), length N, receives a start pulse at one end (the
>>>> 'Fire!' command), which is then transmitted down the line. 
>>>> Later, they must all fire in unison (each soldier has one
>>>> bullet).  The goal is to make this happen in minimum time.
>>>>
>>>> The purported solutions range from 3N to 8N clock ticks.  I
>>>> have found a solution which has an upper bound of 3N.  It
>>>> seems optimal to me, though I cannot prove it (probably no
>>>> such proof exists).
>>>>
>>>> ... someone has supposedly devised a design which
>>>> runs in time 2N.  I disbelieve this;
>>>>
>>>> Can anyone confirm a 2N solution?  Or provide an impossibility
>>>> proof?
> ....
>>> I suspect you have omitted some condition.  Feynman would have
>>> had no problem with that.
>>
>> Seems to me the additional condition was probably about the
>> nature of the soldier-to-soldier signal: If a soldier can pass
>> only a "pulse," not a number, the problem gets harder.  (The
>> dodge of passing a number by emitting a train of pulses works
>> but takes inordinate time, since it takes N pulses plus one
>> blank space, or N+1 clocks, to transmit the number.  Fancier
>> encodings might be used, but I don't see how they could crack
>> the lg(N) barrier, which wouldn't lead to 2N  solution from
>> the transmit-a-count strategy.)
> 
> Your observation re encoding is cogent, but not really germane. 
> N is unknown, that's the point.

You snipped attributions, and my solution.  Which did not require
knowing N for the 2N result.  It did for the N result.  Never snip
attributions for material you quote.

-- 
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: <http://cbfalconer.home.att.net>
            Try the download section.



-- 
Posted via a free Usenet account from http://www.teranews.com

CBFalconer wrote:
> You snipped attributions, and my solution.  Which did not require
> knowing N for the 2N result.  It did for the N result.  Never snip
> attributions for material you quote.

If N is arbitrarily large, then log(N) is arbitrarily large.  Therefore,
no finite state machine is capable of storing (or transmitting) a
digital representation of N (or indeed any representation).  Since
your solution requires that, it can't work.

   - Logan

"CBFalconer" <cbfalconer@yahoo.com> wrote in message 
news:47CCC397.A4E578F3@yahoo.com...
> PT wrote:
>>
>> In "Lectures on Computation", Richard Feynman discusses the firing
>> squad problem: an array of finite state machines ('soldiers'),
>> length N, receives a start pulse at one end (the 'Fire!' command),
>> which is then transmitted down the line.  Later, they must all
>> fire in unison (each soldier has one bullet).  The goal is to make
>> this happen in minimum time.
>>
>> He alludes to it as a known problem, though it's new to me.
>>
>> The purported solutions range from 3N to 8N clock ticks.  I have
>> found a solution which has an upper bound of 3N.  It seems optimal
>> to me, though I cannot prove it (probably no such proof exists).
>>
>> Feynman admits he failed to solve it, and that someone has
>> supposedly devised a design which runs in time 2N.  I disbelieve
>> this; I think he's mistaken, or misinformed.
>>
>> Can anyone confirm a 2N solution?  Or provide an impossibility
>> proof?
>
> Easy.  At the start end, the 1st soldier receives a count of 0, and
> passes on a count of 1, i.e. n+1.  Etc, until the end soldier
> receives the value of N.  This has taken N clocks.  Now the end
> soldier passes back N-1, and remembers N.  N, to him, now means
> fire after N more clocks.  This is repeated up the line, each
> passing back received N-1.  When the result arrives at the first
> soldier, they all fire.  Elapsed time, 2N.
>
> If the first soldier knows the value of N it can be reduced to time
> N.
>
> I suspect you have omitted some condition.  Feynman would have had
> no problem with that.

I think the problem was meant to be an N by N array. Not an N line. And 
there were other conditions about only getting one message or some such 
stupidness. 

On Mon, 03 Mar 2008 23:00:53 -0500, Eric Sosman wrote:
....
>      Question: Can a soldier "pulse" to his right and left
> independently, or is every "pulse" received by both neighbors?
> At first blush, the latter case appears insoluble -- but my
> intuition falls somewhat short of omniscience ...

Pulsing both ways wouldn't work, because every soldier echoes the pulse;
you'd get one every clock, from one side or the other. By the time it got
to soldier N, everybody would be receiving continual clocks.

Cheers!
Rich

Mark Jeffcoat <jeffcoat@alumni.rice.edu> writes:
> PT <ptanenbaum@consultant.com> writes:
> 
> > In "Lectures on Computation", Richard Feynman discusses the firing
> > squad problem: an array of finite state machines ('soldiers'), length
> > N,
> > receives a start pulse at one end (the 'Fire!' command), which is
> > then
> > transmitted down the line.  Later, they must all fire in unison (each
> > soldier has one bullet).  The goal is to make this happen in minimum
> > time.
> > [ ... ]
> 
> Googling for "firing squad problem" is the fastest way to
> get a solution; of the references that turns up, 
>    http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem
> and
>    http://www.stanford.edu/~jcackler/automata/problem.htm
> look pretty useful.
> 
> (Spoiler: According to the second reference, the best
> and provably minimal solution has N-2 steps and 6 states per
> DFA.)

According tho that second reference, the best and provably
minimal solution has 0 steps and 0 states per DFA.

And according to that reference, they aren't DFAs at all, 
either.

Phil
-- 
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration

"MisterE" <voids@sometwher.world> wrote:

} I think the problem was meant to be an N by N array. Not an N line. And 
} there were other conditions about only getting one message or some such 
} stupidness. 

NxN is easy once you can solve N-in-a-line: you synchronize across row-1,
but what you synchronize isn't "fire" but "Begin synchronizing your
column".  When the columns synchronize they all fire.

  /Bernie\
-- 
Bernie Cosell                     Fantasy Farm Fibers
bernie@fantasyfarm.com            Pearisburg, VA
    -->  Too many people, too few sheep  <--