Finite approximate approach to the study of the complexity of recursive predicates

DOI10.1007/BF01091745zbMath0401.68023OpenAlexW2040175666MaRDI QIDQ1255316

R. I. Freidzon

Publication date: 1978

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

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

zbMATH Keywords

Complexity of Recursive PredicatesFinite AutomatonPartial Recursive FunctionTuring Machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Cites Work

• Unnamed Item
• Fast multiplication of large numbers
• Lower estimate of the number of steps for an inverting normal algorithm and other similar algorithms
• Gödel numberings of partial recursive functions
• Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On the Length of Programs for Computing Finite Binary Sequences
• On the size of machines
• On the problem of finding minimal programs for tables

This page was built for publication: Finite approximate approach to the study of the complexity of recursive predicates