|
Zapiski Nauchnykh Seminarov 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.
Citation:
M. V. Kubinets, “The recognition of the self-crossing of plane trajectory by Kolmogorov algorithm”, Studies in constructive mathematics and mathematical logic. Part V, Zap. Nauchn. Sem. LOMI, 32, "Nauka", Leningrad. Otdel., Leningrad, 1972, 35–44
Linking options:
https://www.mathnet.ru/eng/znsl2562 https://www.mathnet.ru/eng/znsl/v32/p35
|
Statistics & downloads: |
Abstract page: | 113 | Full-text PDF : | 50 |
|