Kolmogoroff algorithms are stronger than Turing machines

DOI10.1007/BF01693975zbMath0449.03030OpenAlexW4318751709MaRDI QIDQ1147126

Dima Yu. Grigoriev

Publication date: 1980

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01693975

zbMATH Keywords

Turing machinesKolmogoroff algorithmsreal time recognizability of a predicate

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Algorithms in computer science (68W99)

Cites Work

• On-Line Turing Machine Computations
• On the Minimum Computation Time of Functions

This page was built for publication: Kolmogoroff algorithms are stronger than Turing machines