Algorithms · Complexity theory · Information entropy
The earliest abacus-like counting boards appear in Mesopotamia, providing a physical tool for arithmetic computation that would spread and evolve across civilizations for millennia. · Wikipedia: https://en.wikipedia.org/wiki/Abacus
The ancient Indian grammarian Panini composed the Ashtadhyayi, a rigorous formal rule system for Sanskrit grammar that is widely regarded as a precursor to modern formal language theory and metalinguistic notation. Source — Wikipedia:
Chinese mathematicians employed counting rods for arithmetic and algebraic computation, enabling sophisticated calculations including solutions to linear equations and extraction of square and cube roots. Source — Wikipedia:
The Chinese suanpan abacus was developed and refined, becoming a dominant computing instrument in East Asia and later spreading to Japan as the soroban, where it remained in widespread use into the modern era. · Wikipedia: https://en.wikipedia.org/wiki/Suanpan
Muhammad ibn Musa al-Khwarizmi published his treatise on algebra at the House of Wisdom in Baghdad, introducing systematic methods for solving linear and quadratic equations; his name gave rise to the word 'algorithm.' · Wikipedia: https://en.wikipedia.org/wiki/Al-Khwarizmi
The Kurdish engineer al-Jazari described a programmable drum-based automaton in his 'Book of Knowledge of Ingenious Mechanical Devices,' representing one of the earliest known examples of programmable machinery using cams and pegs. Source — Wikipedia:
Korean monks at the Heungdeok Temple printed Jikji using metal movable type, predating European movable type printing by decades and demonstrating an early form of information reproduction technology. Source — Wikipedia:
Charles Babbage designed the Analytical Engine, a proposed mechanical general-purpose computer incorporating an arithmetic logic unit, conditional branching, and memory, though it was never completed in his lifetime. Source — Wikipedia:
Ada Lovelace published notes on the Analytical Engine including a method for computing Bernoulli numbers, now widely recognized as the first published algorithm intended for machine execution. Source — Wikipedia:
Kurt Gödel published his incompleteness theorems, demonstrating that any sufficiently powerful formal axiomatic system contains true statements that are unprovable within the system, profoundly impacting the foundations of computation. Source — Wikipedia:
Alan Turing introduced the Turing machine in 'On Computable Numbers,' providing a formal model of computation that defined the limits of what is mechanically computable and laid the foundation for theoretical computer science. · Wikipedia: https://en.wikipedia.org/wiki/Turing_machine
Alonzo Church published the lambda calculus, an alternative formal system for defining computable functions, and conjectured with Turing that their equivalent models capture the intuitive notion of effective calculability. · Wikipedia: https://en.wikipedia.org/wiki/Lambda_calculus
Claude Shannon published 'A Mathematical Theory of Communication,' introducing information entropy as a measure of uncertainty and establishing the theoretical foundations of digital communication and data compression. · Wikipedia: https://en.wikipedia.org/wiki/Information_theory
Andrey Markov Jr. published 'The Theory of Algorithms,' formalizing the concept of normal algorithms and contributing to the Soviet school of computability theory parallel to Western developments. Source — Wikipedia:
Noam Chomsky published his classification of formal grammars into four types (regular, context-free, context-sensitive, and recursively enumerable), establishing a hierarchy that connects formal language theory to automata and computation. · Wikipedia: https://en.wikipedia.org/wiki/Chomsky_hierarchy
Stephen Cook proved that the Boolean satisfiability problem is NP-complete, introducing the concept of NP-completeness and establishing the P versus NP problem as a central question in computer science. · Wikipedia: https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
Juris Hartmanis and Richard Stearns published 'On the Computational Complexity of Algorithms,' formally defining time complexity classes and establishing computational complexity theory as a field. Source — Wikipedia:
Richard Karp demonstrated that 21 diverse combinatorial problems are all NP-complete, showing the breadth of the P versus NP question and cementing the practical importance of complexity theory. · Wikipedia: https://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems
Ron Rivest, Adi Shamir, and Leonard Adleman published the RSA public-key cryptosystem, whose security relies on the computational hardness of factoring large integers, linking complexity theory to practical cryptography. · Wikipedia: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
Leonard Adleman demonstrated the first experimental computation using DNA molecules to solve a Hamiltonian path problem, opening the field of molecular computing and expanding the physical substrates of computation. · Wikipedia: https://en.wikipedia.org/wiki/DNA_computing
David Deutsch published the concept of a universal quantum Turing machine, establishing the theoretical foundation of quantum computation and showing that quantum computers could in principle simulate any physical process. · Wikipedia: https://en.wikipedia.org/wiki/Quantum_Turing_machine
Peter Shor published a polynomial-time quantum algorithm for integer factorization, demonstrating that quantum computers could break RSA and establishing quantum complexity theory as a practically important field. · Wikipedia: https://en.wikipedia.org/wiki/Shor's_algorithm
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena at the Indian Institute of Technology Kanpur published the AKS primality test, the first deterministic polynomial-time algorithm for testing primality, resolving a long-standing open problem. · Wikipedia: https://en.wikipedia.org/wiki/AKS_primality_test