Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

3 votes

Primitive recursive permutations

Given a set $X\not\ni 0$, let $\pi_X$ be the permutation of $\mathbb{N}$ defined as follows: $$\pi_X(x)=\begin{cases} x+1 & \mbox{ if }x\not\in X,\\ \max(\{y\in X: y<x\}\cup \{0\}) & \mbox{ ...
Noah Schweber's user avatar
10 votes

Does every computable function have infinitely many "non-padded" representations?

Given any computable function $f : \mathbb{N} \to \mathbb{N}$ the set of its indices $S_f = \{n \in \mathbb{N} \mid \phi_n = f\}$ is for all practical purposes "the set of all programs computing $...
Andrej Bauer's user avatar
  • 29.1k

Top 50 recent answers are included