1.
Turing machine
–
Despite the models simplicity, given any computer algorithm, a Turing machine can be constructed that is capable of simulating that algorithms logic. The machine operates on an infinite memory tape divided into discrete cells, the machine positions its head over a cell and reads the symbol there. The Turing machine was invented in 1936 by Alan Turing, who called it an a-machine, thus, Turing machines prove fundamental limitations on the power of mechanical computation. Turing completeness is the ability for a system of instructions to simulate a Turing machine, a Turing machine is a general example of a CPU that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a capable of enumerating some arbitrary subset of valid strings of an alphabet. Assuming a black box, the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program and this is due to the fact that the halting problem is unsolvable, which has major implications for the theoretical limits of computing. The Turing machine is capable of processing an unrestricted grammar, which implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through lambda calculus, a Turing machine that is able to simulate any other Turing machine is called a universal Turing machine. The thesis states that Turing machines indeed capture the notion of effective methods in logic and mathematics. Studying their abstract properties yields many insights into computer science and complexity theory, at any moment there is one symbol in the machine, it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, however, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings, the Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are symbols, which the machine can read and write, one at a time, in the original article, Turing imagines not a mechanism, but a person whom he calls the computer, who executes these deterministic mechanical rules slavishly. If δ is not defined on the current state and the current tape symbol, Q0 ∈ Q is the initial state F ⊆ Q is the set of final or accepting states. The initial tape contents is said to be accepted by M if it eventually halts in a state from F, Anything that operates according to these specifications is a Turing machine. The 7-tuple for the 3-state busy beaver looks like this, Q = Γ = b =0 Σ = q 0 = A F = δ = see state-table below Initially all tape cells are marked with 0. In the words of van Emde Boas, p.6, The set-theoretical object provides only partial information on how the machine will behave and what its computations will look like. For instance, There will need to be many decisions on what the symbols actually look like, and a failproof way of reading and writing symbols indefinitely

2.
Quantum computing
–
Quantum computing studies theoretical computation systems that make direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from binary digital electronic computers based on transistors, a quantum Turing machine is a theoretical model of such a computer, and is also known as the universal quantum computer. The field of computing was initiated by the work of Paul Benioff and Yuri Manin in 1980, Richard Feynman in 1982. A quantum computer with spins as quantum bits was also formulated for use as a quantum space–time in 1968, there exist quantum algorithms, such as Simons algorithm, that run faster than any possible probabilistic classical algorithm. A classical computer could in principle simulate a quantum algorithm, as quantum computation does not violate the Church–Turing thesis, on the other hand, quantum computers may be able to efficiently solve problems which are not practically feasible on classical computers. A classical computer has a made up of bits, where each bit is represented by either a one or a zero. A quantum computer maintains a sequence of qubits, in general, a quantum computer with n qubits can be in an arbitrary superposition of up to 2 n different states simultaneously. A quantum computer operates by setting the qubits in a drift that represents the problem at hand. The sequence of gates to be applied is called a quantum algorithm, the calculation ends with a measurement, collapsing the system of qubits into one of the 2 n pure states, where each qubit is zero or one, decomposing into a classical state. The outcome can therefore be at most n classical bits of information, Quantum algorithms are often probabilistic, in that they provide the correct solution only with a certain known probability. Note that the term non-deterministic computing must not be used in case to mean probabilistic. An example of an implementation of qubits of a computer could start with the use of particles with two spin states, down and up. This is true because any such system can be mapped onto an effective spin-1/2 system, a quantum computer with a given number of qubits is fundamentally different from a classical computer composed of the same number of classical bits. This means that when the state of the qubits is measured. To better understand this point, consider a classical computer that operates on a three-bit register, if there is no uncertainty over its state, then it is in exactly one of these states with probability 1. However, if it is a computer, then there is a possibility of it being in any one of a number of different states. The state of a quantum computer is similarly described by an eight-dimensional vector. Here, however, the coefficients a k are complex numbers, and it is the sum of the squares of the absolute values, ∑ i | a i |2

3.
Association for Computing Machinery
–
The Association for Computing Machinery is an international learned society for computing. It was founded in 1947 and is the worlds largest scientific and it is a not-for-profit professional membership group. Its membership is more than 100,000 as of 2011 and its headquarters are in New York City. The ACM is an organization for academic and scholarly interests in computer science. Its motto is Advancing Computing as a Science & Profession, ACM is organized into over 171 local chapters and 37 Special Interest Groups, through which it conducts most of its activities. Additionally, there are over 500 college and university chapters, the first student chapter was founded in 1961 at the University of Louisiana at Lafayette. Many of the SIGs, such as SIGGRAPH, SIGPLAN, SIGCSE and SIGCOMM, sponsor regular conferences, the groups also publish a large number of specialized journals, magazines, and newsletters. ACM publishes over 50 journals including the prestigious Journal of the ACM, other publications of the ACM include, ACM XRDS, formerly Crossroads, was redesigned in 2010 and is the most popular student computing magazine in the US. ACM Interactions, an interdisciplinary HCI publication focused on the connections between experiences, people and technology, and the third largest ACM publication, ACM Computing Surveys ACM Computers in Entertainment A number of journals, specific to subfields of computer science, titled ACM Transactions. ACM has made almost all of its publications available to subscribers online at its Digital Library. Individual members additionally have access to Safari Books Online and Books24x7, ACM also offers insurance, online courses, and other services to its members. In 1997, ACM Press published Wizards and Their Wonders, Portraits in Computing, written by Christopher Morgan, the book is a collection of historic and current portrait photographs of figures from the computer industry. The ACM Portal is a service of the ACM. Its core are two sections, ACM Digital Library and the ACM Guide to Computing Literature. The ACM Digital Library is the collection of all articles published by the ACM in its articles, magazines. The Guide is a bibliography in computing with over one million entries, the ACM Digital Library contains a comprehensive archive starting in the 1950s of the organizations journals, magazines, newsletters and conference proceedings. Online services include a forum called Ubiquity and Tech News digest, there is an extensive underlying bibliographic database containing key works of all genres from all major publishers of computing literature. This secondary database is a rich discovery service known as The ACM Guide to Computing Literature, ACM adopted a hybrid Open Access publishing model in 2013

4.
Scott Aaronson
–
Scott Joel Aaronson is a theoretical computer scientist. His primary area of research is quantum computing and computational complexity theory more generally, Aaronson grew up in the United States, though he spent a year in Asia when his father—a science writer turned public-relations executive—was posted to Hong Kong. He enrolled in a program for gifted youngsters run by Clarkson University, Aaronson had shown ability in mathematics from an early age, teaching himself calculus at the age of 11, provoked by symbols in a babysitters textbook. He discovered computer programming at age 11, and felt he lagged behind peers, partly for this reason, he felt drawn to theoretical computing, particularly computational complexity. At Cornell, he interested in quantum computing, and devoted himself to computational complexity. After postdoctorates at the Institute for Advanced Study and the University of Waterloo and his primary area of research is quantum computing and computational complexity theory more generally. In the summer of 2016 he moved from MIT to the University of Texas at Austin as David J. Bruton Jr, centennial Professor of Computer Science and as the founding director of UT Austins new quantum computing center. Aaronson is one of two winners of the 2012 Alan T. Waterman Award, best Paper Award of CSR2011 for the paper The Equivalence of Sampling and Searching. He is a founder of the Complexity Zoo wiki, which all classes of computational complexity. He is the author of the much-read blog Shtetl-Optimized as well as the essay Who Can Name The Bigger Number and it weaves together seemingly disparate topics into a cohesive whole, including quantum mechanics, complexity, free will, time travel, the anthropic principle and many others. Many of these applications of computational complexity were later fleshed out in his article Why Philosophers Should Care About Computational Complexity. An article of Aaronsons, The Limits of Quantum Computers, was published in Scientific American, Aaronson is frequently cited in non-academic press, such as Science News, The Age, ZDNet, Slashdot, New Scientist, The New York Times, and Forbes magazine. Aaronson was the subject of attention in October 2007, when he accused Love Communications of plagiarizing a lecture he wrote on quantum mechanics in an advertisement of theirs. He alleged that a commercial for Ricoh Australia by Sydney-based agency Love Communications appropriated content almost verbatim from the lecture, Aaronson received an email from the agency claiming to have sought legal advice and saying they did not believe that they were in violation of his copyright. Unsatisfied, Aaronson pursued the matter, and the agency settled the dispute without admitting wrongdoing by making a contribution to two science organizations of his choice. Concerning this matter, Aaronson stated, Someone suggested a cameo with the models, scott Aaronson at the Mathematics Genealogy Project Aaronsons blog Aaronson homepage

5.
Computational complexity theory
–
A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying the amount of resources needed to solve them, such as time and storage. Other complexity measures are used, such as the amount of communication, the number of gates in a circuit. One of the roles of computational complexity theory is to determine the limits on what computers can. Closely related fields in computer science are analysis of algorithms. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources, a computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a problem is referred to as a problem instance. In computational complexity theory, a problem refers to the question to be solved. In contrast, an instance of this problem is a rather concrete utterance, for example, consider the problem of primality testing. The instance is a number and the solution is yes if the number is prime, stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input. For this reason, complexity theory addresses computational problems and not particular problem instances, when considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet, as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices and this can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the objects of study in computational complexity theory. A decision problem is a type of computational problem whose answer is either yes or no. A decision problem can be viewed as a language, where the members of the language are instances whose output is yes. The objective is to decide, with the aid of an algorithm, if the algorithm deciding this problem returns the answer yes, the algorithm is said to accept the input string, otherwise it is said to reject the input. An example of a problem is the following

6.
ArXiv
–
In many fields of mathematics and physics, almost all scientific papers are self-archived on the arXiv repository. Begun on August 14,1991, arXiv. org passed the half-million article milestone on October 3,2008, by 2014 the submission rate had grown to more than 8,000 per month. The arXiv was made possible by the low-bandwidth TeX file format, around 1990, Joanne Cohn began emailing physics preprints to colleagues as TeX files, but the number of papers being sent soon filled mailboxes to capacity. Additional modes of access were added, FTP in 1991, Gopher in 1992. The term e-print was quickly adopted to describe the articles and its original domain name was xxx. lanl. gov. Due to LANLs lack of interest in the rapidly expanding technology, in 1999 Ginsparg changed institutions to Cornell University and it is now hosted principally by Cornell, with 8 mirrors around the world. Its existence was one of the factors that led to the current movement in scientific publishing known as open access. Mathematicians and scientists regularly upload their papers to arXiv. org for worldwide access, Ginsparg was awarded a MacArthur Fellowship in 2002 for his establishment of arXiv. The annual budget for arXiv is approximately $826,000 for 2013 to 2017, funded jointly by Cornell University Library, annual donations were envisaged to vary in size between $2,300 to $4,000, based on each institution’s usage. As of 14 January 2014,174 institutions have pledged support for the period 2013–2017 on this basis, in September 2011, Cornell University Library took overall administrative and financial responsibility for arXivs operation and development. Ginsparg was quoted in the Chronicle of Higher Education as saying it was supposed to be a three-hour tour, however, Ginsparg remains on the arXiv Scientific Advisory Board and on the arXiv Physics Advisory Committee. The lists of moderators for many sections of the arXiv are publicly available, additionally, an endorsement system was introduced in 2004 as part of an effort to ensure content that is relevant and of interest to current research in the specified disciplines. Under the system, for categories that use it, an author must be endorsed by an established arXiv author before being allowed to submit papers to those categories. Endorsers are not asked to review the paper for errors, new authors from recognized academic institutions generally receive automatic endorsement, which in practice means that they do not need to deal with the endorsement system at all. However, the endorsement system has attracted criticism for allegedly restricting scientific inquiry, perelman appears content to forgo the traditional peer-reviewed journal process, stating, If anybody is interested in my way of solving the problem, its all there – let them go and read about it. The arXiv generally re-classifies these works, e. g. in General mathematics, papers can be submitted in any of several formats, including LaTeX, and PDF printed from a word processor other than TeX or LaTeX. The submission is rejected by the software if generating the final PDF file fails, if any image file is too large. ArXiv now allows one to store and modify an incomplete submission, the time stamp on the article is set when the submission is finalized

7.
CC (complexity)
–
In computational complexity theory, CC is the complexity class containing decision problems which can be solved by comparator circuits of polynomial size. The most important problem which is complete for CC is a variant of the stable marriage problem. A comparator circuit is a network of wires and gates, each comparator gate, which is a directed edge connecting two wires, takes its two inputs and outputs them in sorted order. The input to any wire can be either a variable, its negation, one of the wires is designated as the output wire. The comparator circuit value problem is the problem of evaluating a comparator circuit given an encoding of the circuit, the complexity class CC is defined as the class of problems logspace reducible to CCVP. An equivalent definition is the class of problems AC0 reducible to CCVP, since there are sorting networks which can be constructed in AC0, this shows that the majority function is in CC. A problem in CC is CC-complete if every problem in CC can be reduced to it using a logspace reduction, the comparator circuit value problem is CC-complete. In the stable marriage problem, there is a number of men and women. Each person ranks all members of the opposite sex, a matching between men and women is stable if there are no unpaired man and woman who prefer each other over their current partners. Among the stable matchings, there is one in each woman gets the best man that she ever gets in any stable matching. The decision version of the matching problem is, given the rankings of all men and women, whether a given man. Although the classical Gale–Shapley algorithm cannot be implemented as a comparator circuit, another problem which is CC-complete is lexicographically-first maximal matching. In this problem, we are given a graph with an order on the vertices. The lexicographically-first maximal matching is obtained by successively matching vertices from the first bipartition to the minimal available vertices from the second bipartition, the problem asks whether the given edge belongs to this matching. Scott Aaronson showed that the model is CC-complete. The problem is to decide whether any pebbles are present in a particular pile after executing the program and he used this to show that the problem of deciding whether any balls reach a designated sink vertex in a Digi-Comp II-like device is also CC-complete. The comparator circuit evaluation problem can be solved in polynomial time, on the other hand, comparator circuits can solve directed reachability, and so CC contains NL. There is a world in which CC and NC are incomparable

8.
International Standard Book Number
–
The International Standard Book Number is a unique numeric commercial book identifier. An ISBN is assigned to each edition and variation of a book, for example, an e-book, a paperback and a hardcover edition of the same book would each have a different ISBN. The ISBN is 13 digits long if assigned on or after 1 January 2007, the method of assigning an ISBN is nation-based and varies from country to country, often depending on how large the publishing industry is within a country. The initial ISBN configuration of recognition was generated in 1967 based upon the 9-digit Standard Book Numbering created in 1966, the 10-digit ISBN format was developed by the International Organization for Standardization and was published in 1970 as international standard ISO2108. Occasionally, a book may appear without a printed ISBN if it is printed privately or the author does not follow the usual ISBN procedure, however, this can be rectified later. Another identifier, the International Standard Serial Number, identifies periodical publications such as magazines, the ISBN configuration of recognition was generated in 1967 in the United Kingdom by David Whitaker and in 1968 in the US by Emery Koltay. The 10-digit ISBN format was developed by the International Organization for Standardization and was published in 1970 as international standard ISO2108, the United Kingdom continued to use the 9-digit SBN code until 1974. The ISO on-line facility only refers back to 1978, an SBN may be converted to an ISBN by prefixing the digit 0. For example, the edition of Mr. J. G. Reeder Returns, published by Hodder in 1965, has SBN340013818 -340 indicating the publisher,01381 their serial number. This can be converted to ISBN 0-340-01381-8, the check digit does not need to be re-calculated, since 1 January 2007, ISBNs have contained 13 digits, a format that is compatible with Bookland European Article Number EAN-13s. An ISBN is assigned to each edition and variation of a book, for example, an ebook, a paperback, and a hardcover edition of the same book would each have a different ISBN. The ISBN is 13 digits long if assigned on or after 1 January 2007, a 13-digit ISBN can be separated into its parts, and when this is done it is customary to separate the parts with hyphens or spaces. Separating the parts of a 10-digit ISBN is also done with either hyphens or spaces, figuring out how to correctly separate a given ISBN number is complicated, because most of the parts do not use a fixed number of digits. ISBN issuance is country-specific, in that ISBNs are issued by the ISBN registration agency that is responsible for country or territory regardless of the publication language. Some ISBN registration agencies are based in national libraries or within ministries of culture, in other cases, the ISBN registration service is provided by organisations such as bibliographic data providers that are not government funded. In Canada, ISBNs are issued at no cost with the purpose of encouraging Canadian culture. In the United Kingdom, United States, and some countries, where the service is provided by non-government-funded organisations. Australia, ISBNs are issued by the library services agency Thorpe-Bowker

9.
NP-completeness
–
In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC, the abbreviation NP refers to nondeterministic polynomial time. That is, the required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve problems quickly. NP-complete problems are addressed by using heuristic methods and approximation algorithms. A problem p in NP is NP-complete if every problem in NP can be transformed into p in polynomial time. NP-complete problems are studied because the ability to quickly verify solutions to a problem seems to correlate with the ability to solve that problem. It is not known whether every problem in NP can be quickly solved—this is called the P versus NP problem, because of this, it is often said that NP-complete problems are harder or more difficult than NP problems in general. A decision problem C is NP-complete if, C is in NP, C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NP-hard, a consequence of this definition is that if we had a polynomial time algorithm for C, we could solve all problems in NP in polynomial time. The concept of NP-completeness was introduced in 1971, though the term NP-complete was introduced later, at 1971 STOC conference, there was a fierce debate among the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine. This is known as the question of whether P=NP, nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics. The Clay Mathematics Institute is offering a US $1 million reward to anyone who has a proof that P=NP or that P≠NP. Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete, in 1972, Richard Karp proved that several other problems were also NP-complete, thus there is a class of NP-complete problems. For more details refer to Introduction to the Design and Analysis of Algorithms by Anany Levitin, an interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices, consider these two problems, Graph Isomorphism, Is graph G1 isomorphic to graph G2. Subgraph Isomorphism, Is graph G1 isomorphic to a subgraph of graph G2, the Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete and this is an example of a problem that is thought to be hard, but is not thought to be NP-complete

10.
Polynomial hierarchy
–
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. It is a counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. There are multiple equivalent definitions of the classes of the polynomial hierarchy. If any Σ k P = Σ k +1 P, or if any Σ k P = Π k P, then the hierarchy collapses to level k, in particular, if P = NP, then the hierarchy collapses completely. The union of all classes in the hierarchy is the complexity class PH. The polynomial hierarchy is an analogue of the hierarchy and arithmetical hierarchy. It is known that PH is contained within PSPACE, but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if, if the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete problems, we know that if PSPACE = PH, then the hierarchy must collapse. Each class in the hierarchy contains ≤ m P -complete problems. Furthermore, each class in the hierarchy is closed under ≤ m P -reductions, meaning that for a class C in the hierarchy. These two facts together imply that if K i is a problem for Σ i P, then Σ i +1 P = N P K i. For instance, Σ2 P = N P S A T, in other words, if a language is defined based on some oracle in C, then we can assume that it is defined based on a complete problem for C. Complete problems therefore act as representatives of the class for which they are complete, the Sipser–Lautemann theorem states that the class BPP is contained in the second level of the polynomial hierarchy. Kannans theorem states that for any k, Σ2 is not contained in SIZE, todas theorem states that the polynomial hierarchy is contained in P#P. EXPTIME Exponential hierarchy Arithmetic hierarchy A. R. Meyer and L. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space, in Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pp. 125–129,1972. The paper that introduced the polynomial hierarchy, theoretical Computer Science, vol.3, pp. 1–22,1976. Michael R. Garey and David S. Johnson, computers and Intractability, A Guide to the Theory of NP-Completeness

11.
BPP (complexity)
–
BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in time with a deterministic machine. Alternatively, BPP can be defined using only deterministic Turing machines, for some applications this definition is preferable since it does not mention probabilistic Turing machines. In practice, a probability of 1⁄3 might not be acceptable, however. It can be any constant between 0 and 1⁄2 and the set BPP will be unchanged and this makes it possible to create a highly accurate algorithm by merely running the algorithm several times and taking a majority vote of the answers. For example, if one defined the class with the restriction that the algorithm can be wrong with probability at most 1⁄2100, besides the problems in P, which are obviously in BPP, many problems were known to be in BPP but not known to be in P. The number of problems is decreasing, and it is conjectured that P = BPP. For a long time, one of the most famous problems that was known to be in BPP, in other words, is there an assignment of values to the variables such that when a nonzero polynomial is evaluated on these values, the result is nonzero. It suffices to choose each variables value uniformly at random from a subset of at least d values to achieve bounded error probability. If the access to randomness is removed from the definition of BPP, in the definition of the class, if we replace the ordinary Turing machine with a quantum computer, we get the class BQP. Adding postselection to BPP, or allowing computation paths to have different lengths, BPPpath is known to contain NP, and it is contained in its quantum counterpart PostBQP. A Monte Carlo algorithm is an algorithm which is likely to be correct. Problems in the class BPP have Monte Carlo algorithms with polynomial bounded running time and this is compared to a Las Vegas algorithm which is a randomized algorithm which either outputs the correct answer, or outputs fail with low probability. Las Vegas algorithms with polynomial bound running times are used to define the class ZPP, alternatively, ZPP contains probabilistic algorithms that are always correct and have expected polynomial running time. This is weaker than saying it is a polynomial time algorithm, since it may run for super-polynomial time and it is known that BPP is closed under complement, that is, BPP = co-BPP. BPP is low for itself, meaning that a BPP machine with the power to solve BPP problems instantly is not any more powerful than the machine without this extra power. The relationship between BPP and NP is unknown, it is not known whether BPP is a subset of NP, NP is a subset of BPP or neither. If NP is contained in BPP, which is considered unlikely since it would imply practical solutions for NP-complete problems, then NP = RP and it is known that RP is a subset of BPP, and BPP is a subset of PP