Formalize ignorance

Question

This is a spinoff of my attempt to capture the notion of 'explicit bijection' at https://mathoverflow.net/a/323827.

I wonder whether it is possible to formalize the idea that an algorithm computing a map $f:A\to B$ between two finite sets does not 'know' or 'use' a description of $B$.

Let me give two examples to illustrate what I mean. Let $A$ be the set of binary words of length $n$.

For the first example, let $f$ be the map corresponding to the following algorithm:

• let $w=w_1\dots w_n$ be the binary word
• let $i=1$
• for $l$ in $w$, reading the word left to right:
  • if $l=1$ increase $i$ by one
  • otherwise write down $i$, and set $i=1$
• write down $i$.

That is, the word $1$ is mapped to $2$ and the word $0$ is mapped to $1,1$. In general, this algorithm associates (bijectively) to each binary word of length $n$ a composition of $n+1$. So $B$ is the set of integer compositions of $n+1$, but it seems (to me) that the algorithm does not use this fact.

For the second example, let $f$ be the map corresponding to the following algorithm:

• let $w=w_1\dots w_n$ be the binary word
• let $k=\sum_{i=1}^n 10^{(n-i)w_i}$
• sort the integer compositions of $n+1$ into lexicographic order and write down the $k$-th.

It is not hard to see that the two maps coincide. However, I would (like to) say that the second algorithm uses the fact that $B$ is the set of integer compositions of $n+1$.

Answer 1

I think regular (or close to regular) languages and finite state automatons might be relevant here.

A language is just a subset of the set of all strings over some alphabet. Classes of combinatorial objects can often be represented as languages with fairly nice descriptions.

A finite state automaton is basically a computer with a fixed, finite amount of memory. It can read from an input tape, but cannot write to it, and does not have an infinite "scratch work" tape. A language L is regular if there is a finite state automaton which halts if and only if the string on the input tape is in L.

We'll also extend this notion to function from one language to another. We'll say a function $f: L \rightarrow L'$ is automaton computable if it can be implemented by a computer with a fixed, finite amount of memory that can read from and navigate through the input tape, write to and navigate through the output tape, but cannot write to the input tape or read from the output tape.

An example here is if L is the set of all binary strings, and L' is the set of all binary strings of even length all of whose even digits are 0, then there is a automaton computable bijection from L to L' given by taking an input string $w_1w_2 \dots w_n$, reading it left to right, and writing $w_i0$ to the output tape for each letter $w_i$ we read.

If we slightly modify your first algorithm, I think it's right to say it is automaton computable. Language L will be the set of finite binary strings, and language L' will be the set of finite sequences of unary numbers, where a sequence of unary numbers is represented by $111...110111...110111...110111...11$, i.e. with a sequence of k 1s representing the number k, with 0s as separators. Then there is an automaton computable function which take a binary string of length n in L and outputs a composition of n+1 represented as a 0-separated sequence of unary numbers. The idea is to use your first algorithm, but instead of storing $i$ as a variable before writing it, we write it down as we go along.

The second algorithm does not correspond to an automaton computable function, however, because this sorting cannot be done with a fixed, finite amount of memory.