The Hartmanis-Stearns conjecture, posed by Juris Hartmanis and Richard Stearns in the 1965 paper that founded computational complexity theory, states that if a real number's expansion in some integer base is real-time computable by a multitape Turing machine, then that number is either rational or transcendental. If true, the conjecture would imply that no integer multiplication algorithm can run in linear time.
Facts
StatementIf a real number's expansion in some integer base b of at least 2 is real-time computable by a multitape Turing machine, then that number is either rational or transcendental. 1 Proposed Year Progress Toward ResolutionBoris Adamczewski and Yann Bugeaud proved a restricted version of the conjecture for automatic sequences, later generalized by Adamczewski, Cassaigne and Le Gonidec to sequences generated by deterministic pushdown automata; a prior claimed proof by Loxton and van der Poorten was found to contain a gap. The general conjecture remains open, and it implies that no integer multiplication algorithm can run in linear time, though an O(n log n) algorithm is known. 1 Classification
Resolution Status Prize Status
Prize Status (category) Sources
1. Hartmanis-Stearns Conjecture (Wikipedia)
Statement section
if x is a real number whose expansion in some base b ≥ 2 is real-time computable, then x is rational or transcendental
Background section
The conjecture was posed in 1965 in a paper by Juris Hartmanis and Richard E. Stearns that founded the field of computational complexity theory.
Partial results section
x is rational or transcendental if the expansion of x in some base b ≥ 2 is an automatic sequence
- Lead section
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.