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

Zap. Nauchn. Sem. LOMI, 1976 Volume 60, Pages 29–37 (Mi znsl2067)

This article is cited in 8 papers

Kolmogoroff algorithms are stronger than turing machines

D. Yu. Grigor'ev


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.

UDC: 518.5


 English version:
Journal of Soviet Mathematics, 1980, 14:5, 1445–1450

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024