2
$\begingroup$

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.

$\endgroup$

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.