Abstract:
Let $M$ be one head one 2-dimensional tape Turing machine with an input. Let input alphabet be $V=\{U,D,R,L\}$, tape alphabet be $\{{}\ast,\lambda\}$ ($\lambda$ being a blank symbol). Every symbol from $V$ corresponds to a direction on the tape: $U$ – up, $D$ – down, $R$ – right, $L$ – left. If $\alpha$, comes on the input of $M$ then the head moves in the direction $\alpha$ and if it observes the symbol $\lambda$ then it prints a $\ast$; observing the symbol $\ast$$M$ stops with the output “there is a self-crossing”. We show that $M$ can be real-time simulated by a Kolmogorov algorithm.