In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".
William Albert Dembski is an American mathematician, philosopher and theologian. He was a proponent of intelligent design (ID) pseudoscience, specifically the concept of specified complexity, and was a senior fellow of the Discovery Institute's Center for Science and Culture (CSC). On September 23, 2016, he officially retired from intelligent design, resigning all his "formal associations with the ID community, including [his] Discovery Institute fellowship of 20 years". A February 2021 interview in the CSC's blog Evolution News announced "his return to the intelligent design arena".
Alfred Vaino Aho is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming.
John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University, Co-Director of the Center on Frontiers of Computing Studies at Peking University, and the Director of the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University.
In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithms for primality testing and integer factorization, finding solutions to diophantine equations, and explicit methods in arithmetic geometry. Computational number theory has applications to cryptography, including RSA, elliptic curve cryptography and post-quantum cryptography, and is used to investigate conjectures and open problems in number theory, including the Riemann hypothesis, the Birch and Swinnerton-Dyer conjecture, the ABC conjecture, the modularity conjecture, the Sato-Tate conjecture, and explicit aspects of the Langlands program.
Specified complexity is a creationist argument introduced by William Dembski, used by advocates to promote the pseudoscience of intelligent design. According to Dembski, the concept can formalize a property that singles out patterns that are both specified and complex, where in Dembski's terminology, a specified pattern is one that admits short descriptions, whereas a complex pattern is one that is unlikely to occur by chance. Proponents of intelligent design use specified complexity as one of their two main arguments, alongside irreducible complexity.
Intelligent Design: The Bridge Between Science and Theology is a 1999 book by the mathematician William A. Dembski, in which the author presents an argument in support of intelligent design. Dembski defines the term "specified complexity", and argues that instances of it in nature cannot be explained by Darwinian evolution, but instead are consistent with the intelligent design. He also derives an instance of his self-declared law of conservation of information and uses it to argue against Darwinian evolution. The book is a summary treatment of the mathematical theory he presents in The Design Inference (1998), and is intended to be largely understandable by a nontechnical audience. Dembski also provides a Christian theological commentary, and analysis of, what he perceives to be the historical and cultural significance of the ideas.
Jeffrey David Ullman is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers, theory of computation, data structures, and databases are regarded as standards in their fields. He and his long-time collaborator Alfred Aho are the recipients of the 2020 Turing Award, generally recognized as the highest distinction in computer science.
The Design Inference: Eliminating Chance through Small Probabilities is a 1998 book by American philosopher and mathematician William A. Dembski, a proponent of intelligent design, which sets out to establish approaches by which evidence of intelligent agency could be inferred in natural and social situations. In the book he distinguishes between 3 general modes of competing explanations in order of priority: regularity, chance, and design. The processes in which regularity, chance, and design are ruled out one by one until one remains as a reasonable and sufficient explanation for an event, are what he calls an "explanatory filter". It is a method that tries to eliminate competing explanations in a systematic fashion including when a highly improbable event conforms to a discernible pattern that is given independently of the event itself. This pattern is Dembski's concept of specified complexity. Throughout the book he uses diverse examples such as detectability of spontaneous generation and occurrence of natural phenomena and cases of deceit like ballot rigging, plagiarism, falsification of data, etc.
Wesley Royce Elsberry is a data scientist with an interdisciplinary background in marine biology, zoology, computer science, and wildlife and fisheries sciences. He also became notably involved in the defense of evolutionary science against creationist rejection of evolution.
Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions beginning in 2000.
Janusz (John) Antoni Brzozowski was a Polish-Canadian computer scientist and Distinguished Professor Emeritus at the University of Waterloo's David R. Cheriton School of Computer Science.
Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.
Thomas Nathaniel Hibbard was an American mathematician and computer scientist.
The Journal of Integer Sequences is a peer-reviewed open-access academic journal in mathematics, specializing in research papers about integer sequences.
Daniel Mier Gusfield is an American computer scientist, Distinguished Professor of Computer Science at the University of California, Davis. Gusfield is known for his research in combinatorial optimization and computational biology.
Therese Charlotte Biedl is an Austrian computer scientist known for her research in computational geometry and graph drawing. Currently she is a professor at the University of Waterloo in Canada.
Hugh Cowie Williams is a Canadian mathematician. He deals with number theory and cryptography.
Cobham's theorem is a theorem in combinatorics on words that has important connections with number theory, notably transcendental numbers, and automata theory. Informally, the theorem gives the condition for the members of a set S of natural numbers written in bases b1 and base b2 to be recognised by finite automata. Specifically, consider bases b1 and b2 such that they are not powers of the same integer. Cobham's theorem states that S written in bases b1 and b2 is recognised by finite automata if and only if S differs by a finite set from a finite union of arithmetic progressions. The theorem was proved by Alan Cobham in 1969 and has since given rise to many extensions and generalisations.
Alan Belmont Cobham was an American mathematician and computer scientist known for inventing the notion of polynomial time and the complexity class P,[B] for Cobham's thesis stating that the problems that have practically usable computer solutions are characterized by having polynomial time,[B] and for Cobham's theorem on the sets of numbers that can be recognized by finite automata.[C] He also did foundational work on automatic sequences,[D] invented priority queues and studied them from the point of view of queueing theory,[A] and wrote a program for playing contract bridge that was at the time one of the best in the world.
