Reseña: Compass-free navigation of mazes
Se ha publicado un artículo de razonamiento formalizado en HOL Light sobre geometría titulado Compass-free navigation of mazes
Sus autores son Phil Scott y Jacques Fleuriot (de la Universidad de Edimburgo).
Su resumen es
If you find yourself in a corridor of a standard maze, a sure and easy way to escape is to simply pick the left (or right) wall, and then follow it along its twists and turns and around the dead-ends till you eventually arrive at the exit. But what happens when you cannot tell left from right? What if you cannot tell North from South? What if you cannot judge distances, and have no idea what it means to follow a wall in a given direction? The possibility of escape in these circumstances is suggested in the statement of an unproven theorem given in David Hilbert’s celebrated Foundations of Geometry, in which he effectively claimed that a standard maze could be fully navigated using axioms and concepts based solely on the relations of points lying on lines in a specified order. We discuss our algorithm for this surprisingly challenging version of the maze navigation problem, and our HOL Light verification of its correctness from Hilbert’s axioms.
El trabajo se ha presentado en el SCSS 2016 (7th International Symposium on Symbolic Computation in Software Science).
El código de las correspondientes teorías en HOL Light se encuentra aquí.
grow polynomially in n if and only if the spectral radius is at most one. One problem with the above characterization is the determination of all complex eigenvalues. In case A contains only non-negative real values, a simplification is possible with the help of the