Probvious

"Probvious" (a portmanteau of the words probabilistic and obvious) is an adjective used to express a high degree of confidence about a mathematical property or statement that is not known to be true. It was introduced by John Conway in an article discussing potentially 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 the article by John Conway where "probvious" is introduced.

The word appears in Conway's article a few times as a way of forming conjectures about a Collatz-like function that had already been investigated in the past. 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 using probabilistic approximations of their functions suggests a clear solution. For example, Bigfoot and Hydra are probviously nonhalting because they simulate biased pseudo-random walks which (when interpreted as random) leave vanishingly small probabilities of ever halting. Similarly, machines such as Lucy's Moonlight and Mother of Giants are probviously halting because they simulate a sequence of pseudo-random coin flips, halting with a fixed probability on each trial.