Tupper’s Self Referential Formula in R | R-bloggers

• Read original article here

Tupper’s Self Referential Formula in R
Posted on October 16, 2022 by Theory meets practice... in R bloggers | 0 Comments
[This article was first published on Theory meets practice... , and kindly contributed to R-bloggers ]. (You can report issue about the content on this page here )
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Share Tweet
Abstract:
We implement Tupper’s self-referencing formula in R. This has been done before by others, but the joy was to be able to learn how to do it yourself using the tidyverse.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License . The R-markdown source code of this blog is available under a GNU General Public License (GPL v3) license from GitHub.
Introduction
Tupper’s self-referencial formula (Tupper 2001) is an equation which maps a 2D \((x,y)\) coordinate to an \(\{\text{FALSE},\text{TRUE}\}\) value. If \((x,y)\) represent pixel locations, the output over a grid of values can thought of as a black & white image where the true/false values are mapped to \(\{0,1\}\) in the usual way. Tupper’s formula is \(f(x,y) =\) \[ \frac{1}{2} < \left\lfloor \operatorname{mod}\left( \left\lfloor\frac{y}{17}\right\rfloor\cdot 2^{-17\lfloor x \rfloor - \operatorname{mod}(\lfloor y \rfloor, 17)}, 2\right)\right\rfloor. \] We note that if one evaluates the function for all integers \((x,y)\) for \(0 \leq x \leq 105\) and \(k\leq y\leq k+16\), where \(k\) is a fixed constant, then one gets a binary image with 106×17 pixels. The entire magic of Tupper’s formula is that it’s just unpacking an encoding of that 106×17 grid by representing it as a 1802 long binary number which is then converted from base-2 into base-10. For some (not so obvious) reason this number is then multiplied by 17 to yield the final value of \(k\) (in base-10) 1 .
We also note that since the right-hand side of Tupper’s equation will always be 0 or 1, the comparison with \(\frac{1}{2}\) appears superfluous and seems to be just a way to get a Boolean instead of a 0/1. Furthermore, since we will be using only integer values for \(x\) and \(y\), the floor operators around \(x\) and \(y\) are not really needed either.
More Background
Initially, I learned about the formula from a twitter post:
Tupper’s self-referential formula is a formula that visually represents itself when graphed at a specific location in the (x, y) plane. pic.twitter.com/wAUVahJ9Dq
— Fermat’s Library ((fermatslibrary?)) February 4, 2018
A nice Numberphile video has also been dedicated to the formula.
R Implementation
One challenge of implementing Tupper’s formula in R is that \(k\) will be a very large integer (~500 digits). Hence, one needs a special purpose library to handle these large numbers. StaTEAstics in their 2013 R blog post on Tupper’s formula use the GNU Multiple Precision Arithmetic Library for this purpose and is interfaced in the gmp R package . We follow their implementation:
## GNU Multiple Precision Arithmetic Library) for handling the long integers library(gmp) ## Define the constant k k