RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1972 Volume 32, Pages 35–44 (Mi znsl2562)

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

M. V. Kubinets


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.



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024