The recognition of the self-crossing of plane trajectory by Kolmogorov algorithm
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part V, Tome 32 (1972), pp. 35-44
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{ZNSL_1972_32_a5,
author = {M. V. Kubinets},
title = {The recognition of the self-crossing of plane trajectory by {Kolmogorov} algorithm},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {35--44},
publisher = {mathdoc},
volume = {32},
year = {1972},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_1972_32_a5/}
}
M. V. Kubinets. The recognition of the self-crossing of plane trajectory by Kolmogorov algorithm. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part V, Tome 32 (1972), pp. 35-44. http://geodesic.mathdoc.fr/item/ZNSL_1972_32_a5/