Pular para o conteúdo principal


Mostrando postagens de Abril, 2017

The escape of blue eyed vampires (answer)

The island of blue eyed vampires (answer)An initial ideaEach one needs to figure out if him/herself is blue eyed. They assume having blue eyes and see how the others react.A technical detailsThere are some variations to formalize this problem using different type of logic: modal logic, temporal logic, Public Announcement Logic and so on.I believe that those kind of prove are tedious to write and read. For now, I will write a sketch to a prove but I belive the best way to prove is using an algorimthm what basically, it would be an adaptation of DPLL algorithm (Davis–Putnam–Logemann–Loveland) that uses dedutive reasoning and prove by contraction.Legend\[\begin{matrix}
BlueEyed(X) :X \text{ is blue eyed.} \\
Leave(X) :X \text{ leaves.} \\
O(y) :y \text{ holds at the next (temporal) state.}
\end{matrix}\]In this temporal simplified logic, we have a set of state that holds the in- formation of days, \(W = \{d_0, d_1, d_2, d3 \ldots , d_n\}\) and transition \(S : W \rightarrow W = \{(d_0, …