Abstract
A predicate is constructed which is recognizable in real time by a Kolmogoroff algorithm but which is not recognizable in real time by a machine with polynomial accessibility.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Literature cited
A. N. Kolmogorov, “Onthe concept of an algorithm,” Usp. Mat. Nauk,8, No. 4(56), 175–176 (1953).
S. A. Cook and S. O. Aanderaa, “On the minimum computation time of functions,” Trans. Am. Math. Soc.,142, 291–314 (1969).
M. S. Paterson, M. J. Fisher, and A. R. Meyer, “An improved overlap argument for online multiplication,” SIAM-AMS Proc., Soc.,142, 291–314 (1969).
A. Schönhage, “Real time simulation of multidimensional Turing machines by storage modification machines,” Proj. MAC Tech. Memo., No. 37 (1973).
F. Harary, Graph Theory, Addison-Wesley (1969).
F. C. Hennie, “On-line Turing machine computation,” IEEE Trans. Electrical Comp., EC-15,1, 35–44 (1966).
Additional information
Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Mathematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 60, pp. 29–37, 1976. Results presented September 25, 1975.
The author would like to acknowledge the advice of A. O. Slisenko and the valuable comments of S. V. Pakhomova, which substantially improved the presentation.
Rights and permissions
About this article
Cite this article
Grigor'ev, D.Y. Kolmogoroff algorithms are stronger than turing machines. J Math Sci 14, 1445–1450 (1980). https://doi.org/10.1007/BF01693975
Issue Date:
DOI: https://doi.org/10.1007/BF01693975