I have some questions about Turing machines. Is there an embedding method where you embed Turing machines, finite automata into continuous space or graphs? Or are there geometrical approaches to analyze Turing machines or automata? ( embed them into some spaces and apply geometrical tools) Thank you



Embedding Turing machine
Let $\mathcal{M}$ be a class of binary functions acting on strings in $\Sigma^\*$,
along with a "size" function $|\cdot|:\mathcal{M}\to\{1,2,\ldots\}$ with the property that there are only finitely many $M\in\mathcal{M}$ of a given size.
Turing machines and finite automata are of this form, where size can be taken as the number of states. Then you can define the following symmetric positive definite kernel on $\Sigma^\*$:
$$ K\_n(x,x') = \sum\_{M\in\mathcal{M}, |M|\le n} 
M(x)M(x').
$$
In words, this counts the number of $M$ on at most $n$ states which accept both $x$ and $x'$. This kernel then embeds $\Sigma^\*$ into a corresponding Reproducing Kernel Hilbert Space. One can ask what languages can be defined by linear separators under this kernel. This topic was explored in
<https://www.sciencedirect.com/science/article/pii/S0304397508004581>
and
<http://www.jmlr.org/papers/volume10/kontorovich09a/kontorovich09a.pdf>
.


