Pular para o conteúdo principal

Postagens

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, …