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
Fulltext:
PDF file (440 kB)
Cited by
English version:
Journal of Soviet Mathematics, 1980,
14
:5,
1445–1450
Bibliographic databases:
©
Steklov Math. Inst. of RAS
, 2024