The recognition of the self-crossing of plane trajectory by Kolmogorov algorithm

M. V. Kubinets

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part V, Tome 32 (1972), pp. 35-44

Résumé

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.