This question stems from intuition so it is a little soft. It concerns performing computation using transformations on sets. The idea is that a rearrangement like Steiner symmetrization might be "computationally strong enough" to be used to execute arbitrary programs.

First we probably should pick an appropriate set $\mathcal{B} \subset \mathcal{P}(\mathbb{R}^d)$, maybe the Lebesgue or Borel measurable sets. Then consider a set of transformations $(T_i)_{i \in I}$ where $T_i: \mathcal{B} \longrightarrow \mathcal{B}$ for every $i \in I$.

We also need a program function $f: \mathcal{B} \longrightarrow I$. Lastly we need some condition that decides when the program finishes running, formally $E: \mathcal{B} \longrightarrow \{\mathit{True}, \mathit{False}\}$.

Then computation is done as follows:

  1. Some $M_0 \in \mathcal{B}$ is the input

  2. $M_{n+1} = T_{f(M_n)}(M_n)$

  3. If $E(M_n) = \mathit{True}$ then the program stops running and the output is $M_n$

1. Question: How are such systems of computation formalized? (i.e. does there exist a "name" for this)

2. Question: Can such systems be "Turing complete" in some sense? How would one show this?

I will also give the specific example that made me wonder: $\mathcal{B}$ are the Lebesgue measurable sets and $(T_i)_{i \in I}$ are the Steiner symmetrizations in all directions. Then $f$ is something I don't know and $E$ could be a condition like the set being convex.

I am sorry for this question being a little vague and would appreciate if someone could improve it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.