Probvious: Difference between revisions
Jump to navigation
Jump to search
(Cleanup some confusing sentences) |
No edit summary |
||
| Line 1: | Line 1: | ||
"'''Probvious'''" (a portmanteau of the words ''probabilistic'' and ''obvious'') is an adjective used to express a high degree of confidence about a mathematical | "'''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.<ref>Conway, J. H. (2013). On Unsettleable Arithmetical Problems. The American Mathematical Monthly, 120(3), 192–198. https://doi.org/10.4169/amer.math.monthly.120.03.192</ref> The term has been used by [https://www.bbchallenge.org bbchallenge] contributors to describe the solutions to halting problems for [[Cryptids]] such as [[Bigfoot]] and [[Hydra]]. | ||
==Usage== | ==Usage== | ||
[[File:ProbviousExcerpt.png|right|300px|thumb|The excerpt from the article by John Conway where "probvious" is introduced.]] | [[File:ProbviousExcerpt.png|right|300px|thumb|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 | The word appears in Conway's article a few times as a way of forming conjectures about a known [[Collatz-like]] function.<ref>Atkin, A. O. L. “Problem 63-13.” SIAM Review, vol. 8, no. 2, 1966, pp. 234–36. JSTOR, http://www.jstor.org/stable/2028281</ref><ref>Guy, R. K. (1983). Don’t Try to Solve These Problems! The American Mathematical Monthly, 90(1), 35–41. https://doi.org/10.1080/00029890.1983.11971148</ref> This function, denoted <math>\mu(n)</math>, is defined as: | ||
<math display="block">\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}</math> | <math display="block">\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}</math> | ||
Conway first uses "probvious" to describe the idea that the sequences of iterates <math>(\cdots,8,\mu(8),\mu^2(8),\cdots)</math> and <math>(\cdots,14,\mu(14),\mu^2(14),\cdots)</math> diverge to infinity. | Conway first uses "probvious" to describe the idea that the sequences of iterates <math>(\cdots,8,\mu(8),\mu^2(8),\cdots)</math> and <math>(\cdots,14,\mu(14),\mu^2(14),\cdots)</math> diverge to infinity. | ||
Likewise, there exist | 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. | ||
== References == | == References == | ||
<references /> | <references /> | ||
Revision as of 13:03, 14 April 2025
"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.[1] The term has been used by bbchallenge contributors to describe the solutions to halting problems for Cryptids such as Bigfoot and Hydra.
Usage
The word appears in Conway's article a few times as a way of forming conjectures about a known Collatz-like function.[2][3] This function, denoted , is defined as:
Conway first uses "probvious" to describe the idea that the sequences of iterates and 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.
References
- ↑ Conway, J. H. (2013). On Unsettleable Arithmetical Problems. The American Mathematical Monthly, 120(3), 192–198. https://doi.org/10.4169/amer.math.monthly.120.03.192
- ↑ Atkin, A. O. L. “Problem 63-13.” SIAM Review, vol. 8, no. 2, 1966, pp. 234–36. JSTOR, http://www.jstor.org/stable/2028281
- ↑ Guy, R. K. (1983). Don’t Try to Solve These Problems! The American Mathematical Monthly, 90(1), 35–41. https://doi.org/10.1080/00029890.1983.11971148