scientific article; zbMATH DE number 3997169

MaRDI QIDQ4723304zbMATH OpenFDO

Authors V. A. Moshchenskij

Publication date 1985

zbMATH Keywords

lower boundtime complexityuniversal Turing machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3873306
• Universal quantifiers and time complexity of random access machines
• scientific article; zbMATH DE number 3941436
• Universal Turing machines with complexity constraint
• The Complexity of Small Universal Turing Machines
• The complexity of small universal Turing machines: A survey
• The Complexity of Small Universal Turing Machines: A Survey
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• On lower bounds for the time of computation
• Automata, Languages and Programming

Cited in

(9)

• The complexity of small universal Turing machines: A survey
• Universal Turing machines with complexity constraint
• The Complexity of Small Universal Turing Machines: A Survey
• Anytime algorithms for non-ending computations
• Modeling non-branching programs with conditional stopping on a universal Turing machine
• One method of analysis of turing computations. III
• scientific article; zbMATH DE number 3995054 (Why is no real title available?)
• The universal Turing machine interpreter
• Machines, Computations, and Universality

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723304)