Probvious

"Probvious" (a portmanteau of the words probabilistic and obvious) is an adjective used to express a high degree of confidence about a mathematical statement that is not known to be true. It was introduced by John Conway in an article discussing possibly unprovable statements. The term has been used by bbchallenge contributors to describe the solutions to halting problems for Cryptids such as Bigfoot and Hydra.

Usage

The excerpt from John Conway's article where "probvious" is introduced.

The word appears in Conway's article a few times as a way of forming conjectures about a known Collatz-like function. This function, denoted $\mu (n)$, is defined as:

$${\begin{array}{lll}\mu (2n)&=&3n\\\mu (4n+1)&=&3n+1\\\mu (4n+3)&=&3n+2\end{array}}\Rightarrow {\begin{array}{lll}\mu ^{-1}(3n)&=&2n\\\mu ^{-1}(3n+1)&=&4n+1\\\mu ^{-1}(3n+2)&=&4n+3\end{array}}$$

Conway first uses "probvious" to describe the idea that the sequences of iterates $(\cdots ,8,\mu (8),\mu ^{2}(8),\cdots )$ and $(\cdots ,14,\mu (14),\mu ^{2}(14),\cdots )$ diverge to infinity.

Likewise, there exist Turing machines for which determining whether they halt requires solving a mathematical problem believed to be difficult, oftentimes a Collatz-like problem, but arguments using probabilistic versions of their behaviour suggest a clear solution. For example, Bigfoot and Hydra are probviously non-halting because they simulate biased random walks that drift towards infinity yet must reach zero for these machines to halt. Alternatively, Lucy's Moonlight is probviously halting because it simulates a sequence of independent random trials for which it has a fixed probability of halting each time.