Search Results

In computability theory, what are examples of decision problems of which it is not known whether they are decidable?

Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a matrix …

Donald Knuth suggested a bitwise approximation for addition on the non-negative integers that is very fast on common processors: $(a,b)\mapsto (a\oplus b) \oplus ((a\land b) \ll 1)$, where $a,b$ are g …

The fish-scale conjecture: In every poset not containing an infinite antichain there exist a chain $C$ and a decomposition of the vertex set into antichains $A_i$, such that $C\cap …

Donald Knuth introduced a fast, bit-wise approximation to integer addition by $$(a,b) \mapsto a \, ^{\land} \, b \, ^{\land} \, ((a \text{ & } b) \ll 1)$$ where $a,b$ are given in binary and $\,^{\lan …

Let $\newcommand{\tn}{\{0,1\}^\mathbb{N}}\tn$ be the collection of all infinite binary sequences. For $s\in\tn$ and $k\in\mathbb{N}$ let the left-shift of $s$ by $k$ positions, $\ell_k(s)\in \tn$, be …

Let $n\in\mathbb{N}$ be a positive integer. Let $\{0,1\}^{(2^n)}$ be the set of $0,1$-sequences of length $2^n$. For $a,b\in \{0,1\}^{(2^n)}$ let $d_h(a,b)$ be the Hamming distance between $a$ and $b$ …

Motivation. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b " …

Is $\;\big\{(a,b,c)\in\mathbb{N}^3: \big(\exists m,n,\ell \in (\mathbb{N}\setminus\{0,1,2\})\big): a^m + b^n= c^\ell\big\}\;$ computable?

Let $\mathbb{N}$ denote the set of positive integers, and let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the neighborhood sum function $\mathrm{nsum}_f:V\to\ma …

Let $n>1$ be an integer. For $a,b\in \{0,1\}^n$ let $d_h(a, b)$ denote the Hamming distance of $a$ and $b$. For $k\in \{1,\ldots,n-1\}$ let $H(n,k)$ be the graph on $\{0,1\}^n$ given by the edge set $ …

(This question actually arose in real life when dealing with status bits with mutual influence.) Let $G=(V,E)$ be a connected, simple, undirected graph with $|V| \geq 2$. For $v\in V$, let $N_G(v) = …

We consider any non-negative integer as an ordinal, that is $0=\emptyset$ and $n=\{0,\ldots,n-1\}$ for every positive integer. Let $\{0,1\}^n$ denote the set of $\{0,1\}$-vectors of length $n$. Define …

Let $\mathbb{N}$ denote the set of non-negative integers. We say that a sequence $f:\mathbb{N}\to \{0,1\}$ is normal if every finite $\{0,1\}$-sequence appears in $f$. Let the swapping operation $\sig …

First, we note that $\mathbb{IR}$ is ordered by $[a,b] \sqsubseteq [c,d]$ iff $[c,d] \subseteq [a,b]$, which makes $\mathbb{IR}$ into a domain. Now suppose $f: [-a,a]\to \mathbb{IR}$ is Scott-continuo …