A Comment on Budach's Mouse-in-an-Octant Problem
classification
💻 cs.FL
keywords
budachproblemmouse-in-an-octantapparentlyarticleattributedbehaviourboas
read the original abstract
Budach's Mouse-in-an-Octant Problem (attributed to Lothar Budach in a 1980 article by van Emde Boas and Karpinski) concerns the behaviour of a very simple finite-state machine ("the mouse") moving on the integer two-dimensional grid. Its decidability is apparently still open. This note sketches a proof that an extended version of the problem (a super-mouse) is undecidable.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.