1.
Mathematics
–
Mathematics is the study of topics such as quantity, structure, space, and change. There is a range of views among mathematicians and philosophers as to the exact scope, Mathematicians seek out patterns and use them to formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proof, when mathematical structures are good models of real phenomena, then mathematical reasoning can provide insight or predictions about nature. Through the use of abstraction and logic, mathematics developed from counting, calculation, measurement, practical mathematics has been a human activity from as far back as written records exist. The research required to solve mathematical problems can take years or even centuries of sustained inquiry, rigorous arguments first appeared in Greek mathematics, most notably in Euclids Elements. Galileo Galilei said, The universe cannot be read until we have learned the language and it is written in mathematical language, and the letters are triangles, circles and other geometrical figures, without which means it is humanly impossible to comprehend a single word. Without these, one is wandering about in a dark labyrinth, carl Friedrich Gauss referred to mathematics as the Queen of the Sciences. Benjamin Peirce called mathematics the science that draws necessary conclusions, David Hilbert said of mathematics, We are not speaking here of arbitrariness in any sense. Mathematics is not like a game whose tasks are determined by arbitrarily stipulated rules, rather, it is a conceptual system possessing internal necessity that can only be so and by no means otherwise. Albert Einstein stated that as far as the laws of mathematics refer to reality, they are not certain, Mathematics is essential in many fields, including natural science, engineering, medicine, finance and the social sciences. Applied mathematics has led to entirely new mathematical disciplines, such as statistics, Mathematicians also engage in pure mathematics, or mathematics for its own sake, without having any application in mind. There is no clear line separating pure and applied mathematics, the history of mathematics can be seen as an ever-increasing series of abstractions. The earliest uses of mathematics were in trading, land measurement, painting and weaving patterns, in Babylonian mathematics elementary arithmetic first appears in the archaeological record. Numeracy pre-dated writing and numeral systems have many and diverse. Between 600 and 300 BC the Ancient Greeks began a study of mathematics in its own right with Greek mathematics. Mathematics has since been extended, and there has been a fruitful interaction between mathematics and science, to the benefit of both. Mathematical discoveries continue to be made today, the overwhelming majority of works in this ocean contain new mathematical theorems and their proofs. The word máthēma is derived from μανθάνω, while the modern Greek equivalent is μαθαίνω, in Greece, the word for mathematics came to have the narrower and more technical meaning mathematical study even in Classical times
2.
Computer science
–
Computer science is the study of the theory, experimentation, and engineering that form the basis for the design and use of computers. An alternate, more succinct definition of science is the study of automating algorithmic processes that scale. A computer scientist specializes in the theory of computation and the design of computational systems and its fields can be divided into a variety of theoretical and practical disciplines. Some fields, such as computational complexity theory, are highly abstract, other fields still focus on challenges in implementing computation. Human–computer interaction considers the challenges in making computers and computations useful, usable, the earliest foundations of what would become computer science predate the invention of the modern digital computer. Machines for calculating fixed numerical tasks such as the abacus have existed since antiquity, further, algorithms for performing computations have existed since antiquity, even before the development of sophisticated computing equipment. Wilhelm Schickard designed and constructed the first working mechanical calculator in 1623, in 1673, Gottfried Leibniz demonstrated a digital mechanical calculator, called the Stepped Reckoner. He may be considered the first computer scientist and information theorist, for, among other reasons and he started developing this machine in 1834, and in less than two years, he had sketched out many of the salient features of the modern computer. A crucial step was the adoption of a card system derived from the Jacquard loom making it infinitely programmable. Around 1885, Herman Hollerith invented the tabulator, which used punched cards to process statistical information, when the machine was finished, some hailed it as Babbages dream come true. During the 1940s, as new and more powerful computing machines were developed, as it became clear that computers could be used for more than just mathematical calculations, the field of computer science broadened to study computation in general. Computer science began to be established as an academic discipline in the 1950s. The worlds first computer science program, the Cambridge Diploma in Computer Science. The first computer science program in the United States was formed at Purdue University in 1962. Since practical computers became available, many applications of computing have become distinct areas of study in their own rights and it is the now well-known IBM brand that formed part of the computer science revolution during this time. IBM released the IBM704 and later the IBM709 computers, still, working with the IBM was frustrating if you had misplaced as much as one letter in one instruction, the program would crash, and you would have to start the whole process over again. During the late 1950s, the science discipline was very much in its developmental stages. Time has seen significant improvements in the usability and effectiveness of computing technology, modern society has seen a significant shift in the users of computer technology, from usage only by experts and professionals, to a near-ubiquitous user base
3.
German language
–
German is a West Germanic language that is mainly spoken in Central Europe. It is the most widely spoken and official language in Germany, Austria, Switzerland, South Tyrol, the German-speaking Community of Belgium and it is also one of the three official languages of Luxembourg. Major languages which are most similar to German include other members of the West Germanic language branch, such as Afrikaans, Dutch, English, Luxembourgish and it is the second most widely spoken Germanic language, after English. One of the languages of the world, German is the first language of about 95 million people worldwide. The German speaking countries are ranked fifth in terms of publication of new books. German derives most of its vocabulary from the Germanic branch of the Indo-European language family, a portion of German words are derived from Latin and Greek, and fewer are borrowed from French and English. With slightly different standardized variants, German is a pluricentric language, like English, German is also notable for its broad spectrum of dialects, with many unique varieties existing in Europe and also other parts of the world. The history of the German language begins with the High German consonant shift during the migration period, when Martin Luther translated the Bible, he based his translation primarily on the standard bureaucratic language used in Saxony, also known as Meißner Deutsch. Copies of Luthers Bible featured a long list of glosses for each region that translated words which were unknown in the region into the regional dialect. Roman Catholics initially rejected Luthers translation, and tried to create their own Catholic standard of the German language – the difference in relation to Protestant German was minimal. It was not until the middle of the 18th century that a widely accepted standard was created, until about 1800, standard German was mainly a written language, in urban northern Germany, the local Low German dialects were spoken. Standard German, which was different, was often learned as a foreign language with uncertain pronunciation. Northern German pronunciation was considered the standard in prescriptive pronunciation guides though, however, German was the language of commerce and government in the Habsburg Empire, which encompassed a large area of Central and Eastern Europe. Until the mid-19th century, it was essentially the language of townspeople throughout most of the Empire and its use indicated that the speaker was a merchant or someone from an urban area, regardless of nationality. Some cities, such as Prague and Budapest, were gradually Germanized in the years after their incorporation into the Habsburg domain, others, such as Pozsony, were originally settled during the Habsburg period, and were primarily German at that time. Prague, Budapest and Bratislava as well as cities like Zagreb, the most comprehensive guide to the vocabulary of the German language is found within the Deutsches Wörterbuch. This dictionary was created by the Brothers Grimm and is composed of 16 parts which were issued between 1852 and 1860, in 1872, grammatical and orthographic rules first appeared in the Duden Handbook. In 1901, the 2nd Orthographical Conference ended with a standardization of the German language in its written form
4.
David Hilbert
–
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th, Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of geometry. He also formulated the theory of Hilbert spaces, one of the foundations of functional analysis, Hilbert adopted and warmly defended Georg Cantors set theory and transfinite numbers. A famous example of his leadership in mathematics is his 1900 presentation of a collection of problems set the course for much of the mathematical research of the 20th century. Hilbert and his students contributed significantly to establishing rigor and developed important tools used in mathematical physics. Hilbert is known as one of the founders of theory and mathematical logic. In late 1872, Hilbert entered the Friedrichskolleg Gymnasium, but, after a period, he transferred to. Upon graduation, in autumn 1880, Hilbert enrolled at the University of Königsberg, in early 1882, Hermann Minkowski, returned to Königsberg and entered the university. Hilbert knew his luck when he saw it, in spite of his fathers disapproval, he soon became friends with the shy, gifted Minkowski. In 1884, Adolf Hurwitz arrived from Göttingen as an Extraordinarius, Hilbert obtained his doctorate in 1885, with a dissertation, written under Ferdinand von Lindemann, titled Über invariante Eigenschaften spezieller binärer Formen, insbesondere der Kugelfunktionen. Hilbert remained at the University of Königsberg as a Privatdozent from 1886 to 1895, in 1895, as a result of intervention on his behalf by Felix Klein, he obtained the position of Professor of Mathematics at the University of Göttingen. During the Klein and Hilbert years, Göttingen became the preeminent institution in the mathematical world and he remained there for the rest of his life. Among Hilberts students were Hermann Weyl, chess champion Emanuel Lasker, Ernst Zermelo, john von Neumann was his assistant. At the University of Göttingen, Hilbert was surrounded by a circle of some of the most important mathematicians of the 20th century, such as Emmy Noether. Between 1902 and 1939 Hilbert was editor of the Mathematische Annalen, good, he did not have enough imagination to become a mathematician. Hilbert lived to see the Nazis purge many of the prominent faculty members at University of Göttingen in 1933 and those forced out included Hermann Weyl, Emmy Noether and Edmund Landau. One who had to leave Germany, Paul Bernays, had collaborated with Hilbert in mathematical logic and this was a sequel to the Hilbert-Ackermann book Principles of Mathematical Logic from 1928. Hermann Weyls successor was Helmut Hasse, about a year later, Hilbert attended a banquet and was seated next to the new Minister of Education, Bernhard Rust
5.
Algorithm
–
In mathematics and computer science, an algorithm is a self-contained sequence of actions to be performed. Algorithms can perform calculation, data processing and automated reasoning tasks, an algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. The transition from one state to the next is not necessarily deterministic, some algorithms, known as randomized algorithms, giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem. In English, it was first used in about 1230 and then by Chaucer in 1391, English adopted the French term, but it wasnt until the late 19th century that algorithm took on the meaning that it has in modern English. Another early use of the word is from 1240, in a manual titled Carmen de Algorismo composed by Alexandre de Villedieu and it begins thus, Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris. Which translates as, Algorism is the art by which at present we use those Indian figures, the poem is a few hundred lines long and summarizes the art of calculating with the new style of Indian dice, or Talibus Indorum, or Hindu numerals. An informal definition could be a set of rules that precisely defines a sequence of operations, which would include all computer programs, including programs that do not perform numeric calculations. Generally, a program is only an algorithm if it stops eventually, but humans can do something equally useful, in the case of certain enumerably infinite sets, They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. An enumerably infinite set is one whose elements can be put into one-to-one correspondence with the integers, the concept of algorithm is also used to define the notion of decidability. That notion is central for explaining how formal systems come into being starting from a set of axioms. In logic, the time that an algorithm requires to complete cannot be measured, from such uncertainties, that characterize ongoing work, stems the unavailability of a definition of algorithm that suits both concrete and abstract usage of the term. Algorithms are essential to the way computers process data, thus, an algorithm can be considered to be any sequence of operations that can be simulated by a Turing-complete system. Although this may seem extreme, the arguments, in its favor are hard to refute. Gurevich. Turings informal argument in favor of his thesis justifies a stronger thesis, according to Savage, an algorithm is a computational process defined by a Turing machine. Typically, when an algorithm is associated with processing information, data can be read from a source, written to an output device. Stored data are regarded as part of the state of the entity performing the algorithm. In practice, the state is stored in one or more data structures, for some such computational process, the algorithm must be rigorously defined, specified in the way it applies in all possible circumstances that could arise. That is, any conditional steps must be dealt with, case-by-case
6.
First-order logic
–
First-order logic – also known as first-order predicate calculus and predicate logic – is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. This distinguishes it from propositional logic, which does not use quantifiers, Sometimes theory is understood in a more formal sense, which is just a set of sentences in first-order logic. In first-order theories, predicates are associated with sets. In interpreted higher-order theories, predicates may be interpreted as sets of sets, There are many deductive systems for first-order logic which are both sound and complete. Although the logical relation is only semidecidable, much progress has been made in automated theorem proving in first-order logic. First-order logic also satisfies several metalogical theorems that make it amenable to analysis in proof theory, such as the Löwenheim–Skolem theorem, first-order logic is the standard for the formalization of mathematics into axioms and is studied in the foundations of mathematics. Peano arithmetic and Zermelo–Fraenkel set theory are axiomatizations of number theory and set theory, respectively, no first-order theory, however, has the strength to uniquely describe a structure with an infinite domain, such as the natural numbers or the real line. Axioms systems that do fully describe these two structures can be obtained in stronger logics such as second-order logic, for a history of first-order logic and how it came to dominate formal logic, see José Ferreirós. While propositional logic deals with simple declarative propositions, first-order logic additionally covers predicates, a predicate takes an entity or entities in the domain of discourse as input and outputs either True or False. Consider the two sentences Socrates is a philosopher and Plato is a philosopher, in propositional logic, these sentences are viewed as being unrelated and might be denoted, for example, by variables such as p and q. The predicate is a philosopher occurs in both sentences, which have a structure of a is a philosopher. The variable a is instantiated as Socrates in the first sentence and is instantiated as Plato in the second sentence, while first-order logic allows for the use of predicates, such as is a philosopher in this example, propositional logic does not. Relationships between predicates can be stated using logical connectives, consider, for example, the first-order formula if a is a philosopher, then a is a scholar. This formula is a statement with a is a philosopher as its hypothesis. The truth of this depends on which object is denoted by a. Quantifiers can be applied to variables in a formula, the variable a in the previous formula can be universally quantified, for instance, with the first-order sentence For every a, if a is a philosopher, then a is a scholar. The universal quantifier for every in this sentence expresses the idea that the if a is a philosopher. The negation of the sentence For every a, if a is a philosopher, then a is a scholar is logically equivalent to the sentence There exists a such that a is a philosopher and a is not a scholar
7.
Structure
–
Structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as biological organisms, abstract structures include data structures in computer science and musical form. Types of structure include a hierarchy, a network featuring many-to-many links, buildings, aircraft, skeletons, anthills, beaver dams and salt domes are all examples of load-bearing structures. The results of construction are divided into buildings and non-building structures, the effects of loads on physical structures are determined through structural analysis, which is one of the tasks of structural engineering. The structural elements can be classified as one-dimensional, two-dimensional, or three-dimensional, the latter was the main option available to early structures such as Chichen Itza. Two-dimensional elements with a third dimension have little of either. The structure elements are combined in structural systems, the majority of everyday load-bearing structures are section-active structures like frames, which are primarily composed of one-dimensional structures. In biology, structures exist at all levels of organization, ranging hierarchically from the atomic and molecular to the cellular, tissue, organ, organismic, population, usually, a higher-level structure is composed of multiple copies of a lower-level structure. Structural biology is concerned with the structure of macromolecules, particularly proteins. The function of molecules is determined by their shape as well as their composition. Protein structure has a four-level hierarchy, the primary structure is the sequence of amino acids that make it up. It has a backbone made up of a repeated sequence of a nitrogen. The secondary structure consists of repeated patterns determined by hydrogen bonding, the two basic types are the α-helix and the β-pleated sheet. The tertiary structure is a back and forth bending of the chain. Chemical structure refers to both molecular geometry and electronic structure, the structure can be represented by a variety of diagrams called structural formulas. Lewis structures use a dot notation to represent the valence electrons for an atom, bonds between atoms can be represented by lines with one line for each pair of electrons that is shared. In a simplified version of such a diagram, called a skeletal formula, only carbon-carbon bonds, atoms in a crystal have a structure that involves repetition of a basic unit called a unit cell. The atoms can be modeled as points on a lattice, and one can explore the effect of symmetry operations that include rotations about a point, reflections about a symmetry planes, and translations
8.
Alonzo Church
–
Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the calculus, Church–Turing thesis, proving the undecidability of the Entscheidungsproblem, Frege–Church ontology. Alonzo Church was born on June 14,1903, in Washington, D. C. where his father, the family later moved to Virginia after his father lost this position because of failing eyesight. With help from his uncle, also named Alonzo Church, he was able to attend the Ridgefield School for Boys in Ridgefield and he stayed at Princeton, earning a Ph. D. in mathematics in three years under Oswald Veblen. He married Mary Julia Kuczinski in 1925 and the couple had three children, Alonzo Church, Jr. Mary Ann and Mildred, after receiving his Ph. D. he taught briefly as an instructor at the University of Chicago and then received a two-year National Research Fellowship. This allowed him to attend Harvard University in 1927–1928 and then both University of Göttingen and University of Amsterdam the following year and he taught philosophy and mathematics at Princeton, 1929–1967, and at the University of California, Los Angeles, 1967–1990. He was a Plenary Speaker at the ICM in 1962 in Stockholm, a deeply religious person, he was a lifelong member of the Presbyterian church. He died in 1995 and was buried in Princeton Cemetery and this is known as Churchs theorem. His proof that Peano arithmetic is undecidable and his articulation of what has come to be known as the Church–Turing thesis. He was the editor of the Journal of Symbolic Logic. His creation of the lambda calculus, the lambda calculus emerged in his 1936 paper showing the unsolvability of the Entscheidungsproblem. This result preceded Alan Turings work on the problem, which also demonstrated the existence of a problem unsolvable by mechanical means. This resulted in the Church–Turing thesis, the lambda calculus influenced the design of the LISP programming language and functional programming languages in general. The Church encoding is named in his honor, many of Churchs doctoral students have led distinguished careers, including C. Anthony Anderson, Peter B. Andrews, George A. Barnard, David Berlinski, William W. Boone, Martin Davis, Alfred L. Foster, Leon Henkin, John G. Kemeny, Stephen C. Kochen, Maurice LAbbé, Isaac Malitz, Gary R. Mar, Michael O. Rabin, Nicholas Rescher, Hartley Rogers, Jr. J. Barkley Rosser, Dana Scott, Raymond Smullyan, a more complete list of Churchs students is available via Mathematics Genealogy Project. Alonzo Church, Introduction to Mathematical Logic Alonzo Church, The Calculi of Lambda-Conversion Alonzo Church, A Bibliography of Symbolic Logic, Introduction to the Collected Works of Alonzo Church, MIT Press, not yet published. In memoriam, Alonzo Church, The Bulletin of Symbolic Logic, wade, Nicholas, Alonzo Church,92, Theorist of the Limits of Mathematics, The New York Times, September 5,1995, p. B6
9.
Alan Turing
–
Alan Mathison Turing OBE FRS was an English computer scientist, mathematician, logician, cryptanalyst and theoretical biologist. Turing is widely considered to be the father of computer science. During the Second World War, Turing worked for the Government Code and Cypher School at Bletchley Park, for a time he led Hut 8, the section responsible for German naval cryptanalysis. After the war, he worked at the National Physical Laboratory and he wrote a paper on the chemical basis of morphogenesis, and predicted oscillating chemical reactions such as the Belousov–Zhabotinsky reaction, first observed in the 1960s. Turing was prosecuted in 1952 for homosexual acts, when by the Labouchere Amendment and he accepted chemical castration treatment, with DES, as an alternative to prison. Turing died in 1954,16 days before his 42nd birthday, an inquest determined his death as suicide, but it has been noted that the known evidence is also consistent with accidental poisoning. In 2009, following an Internet campaign, British Prime Minister Gordon Brown made a public apology on behalf of the British government for the appalling way he was treated. Queen Elizabeth II granted him a pardon in 2013. The Alan Turing law is now a term for a 2017 law in the United Kingdom that retroactively pardons men cautioned or convicted under historical legislation that outlawed homosexual acts. Turings father was the son of a clergyman, the Rev. John Robert Turing, from a Scottish family of merchants that had based in the Netherlands. Turings mother, Julius wife, was Ethel Sara, daughter of Edward Waller Stoney, the Stoneys were a Protestant Anglo-Irish gentry family from both County Tipperary and County Longford, while Ethel herself had spent much of her childhood in County Clare. Julius work with the ICS brought the family to British India and he had an elder brother, John. At Hastings, Turing stayed at Baston Lodge, Upper Maze Hill, St Leonards-on-Sea, very early in life, Turing showed signs of the genius that he was later to display prominently. His parents purchased a house in Guildford in 1927, and Turing lived there during school holidays, the location is also marked with a blue plaque. Turings parents enrolled him at St Michaels, a day school at 20 Charles Road, St Leonards-on-Sea, the headmistress recognised his talent early on, as did many of his subsequent educators. From January 1922 to 1926, Turing was educated at Hazelhurst Preparatory School, in 1926, at the age of 13, he went on to Sherborne School, an independent school in the market town of Sherborne in Dorset. Turings natural inclination towards mathematics and science did not earn him respect from some of the teachers at Sherborne and his headmaster wrote to his parents, I hope he will not fall between two stools. If he is to stay at school, he must aim at becoming educated
10.
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
11.
Gottfried Wilhelm Leibniz
–
Leibnizs notation has been widely used ever since it was published. It was only in the 20th century that his Law of Continuity and he became one of the most prolific inventors in the field of mechanical calculators. He also refined the number system, which is the foundation of virtually all digital computers. Leibniz, along with René Descartes and Baruch Spinoza, was one of the three great 17th-century advocates of rationalism and he wrote works on philosophy, politics, law, ethics, theology, history, and philology. Leibnizs contributions to this vast array of subjects were scattered in various learned journals, in tens of thousands of letters and he wrote in several languages, but primarily in Latin, French, and German. There is no complete gathering of the writings of Leibniz in English, Gottfried Leibniz was born on July 1,1646, toward the end of the Thirty Years War, in Leipzig, Saxony, to Friedrich Leibniz and Catharina Schmuck. Friedrich noted in his journal,21. Juny am Sontag 1646 Ist mein Sohn Gottfried Wilhelm, post sextam vespertinam 1/4 uff 7 uhr abents zur welt gebohren, in English, On Sunday 21 June 1646, my son Gottfried Wilhelm is born into the world a quarter after six in the evening, in Aquarius. Leibniz was baptized on July 3 of that year at St. Nicholas Church, Leipzig and his father died when he was six and a half years old, and from that point on he was raised by his mother. Her teachings influenced Leibnizs philosophical thoughts in his later life, Leibnizs father had been a Professor of Moral Philosophy at the University of Leipzig, and the boy later inherited his fathers personal library. He was given access to it from the age of seven. Access to his fathers library, largely written in Latin, also led to his proficiency in the Latin language and he also composed 300 hexameters of Latin verse, in a single morning, for a special event at school at the age of 13. In April 1661 he enrolled in his fathers former university at age 15 and he defended his Disputatio Metaphysica de Principio Individui, which addressed the principle of individuation, on June 9,1663. Leibniz earned his masters degree in Philosophy on February 7,1664, after one year of legal studies, he was awarded his bachelors degree in Law on September 28,1665. His dissertation was titled De conditionibus, in early 1666, at age 19, Leibniz wrote his first book, De Arte Combinatoria, the first part of which was also his habilitation thesis in Philosophy, which he defended in March 1666. His next goal was to earn his license and Doctorate in Law, in 1666, the University of Leipzig turned down Leibnizs doctoral application and refused to grant him a Doctorate in Law, most likely due to his relative youth. Leibniz then enrolled in the University of Altdorf and quickly submitted a thesis, the title of his thesis was Disputatio Inauguralis de Casibus Perplexis in Jure. Leibniz earned his license to practice law and his Doctorate in Law in November 1666 and he next declined the offer of an academic appointment at Altdorf, saying that my thoughts were turned in an entirely different direction
12.
Mechanical calculator
–
A mechanical calculator, or calculating machine, was a mechanical device used to perform automatically the basic operations of arithmetic. Most mechanical calculators were comparable in size to small computers and have been rendered obsolete by the advent of the electronic calculator. Surviving notes from Wilhelm Schickard in 1623 reveal that he designed and had built the earliest of the attempts at mechanizing calculation. A study of the surviving notes shows a machine that would have jammed after a few entries on the dial. Schickard abandoned his project in 1624 and never mentioned it again until his death years later in 1635. Two decades after Schickards supposedly failed attempt, in 1642, Blaise Pascal decisively solved these problems with his invention of the mechanical calculator. Co-opted into his fathers labour as tax collector in Rouen, Pascal designed the calculator to help in the amount of tedious arithmetic required. It was called Pascals Calculator or Pascaline, for forty years the arithmometer was the only type of mechanical calculator available for sale. The comptometer, introduced in 1887, was the first machine to use a keyboard which consisted of columns of nine keys for each digit, the Dalton adding machine, manufactured from 1902, was the first to have a 10 key keyboard. Electric motors were used on some mechanical calculators from 1901, the production of mechanical calculators came to a stop in the middle of the 1970s closing an industry that had lasted for 120 years. The first one was a mechanical calculator, his difference engine. In 1855, Georg Scheutz became the first of a handful of designers to succeed at building a smaller and simpler model of his difference engine, a crucial step was the adoption of a punched card system derived from the Jacquard loom making it infinitely programmable. The desire to economize time and mental effort in arithmetical computations and this instrument was probably invented by the Semitic races and later adopted in India, whence it spread westward throughout Europe and eastward to China and Japan. After the development of the abacus, no further advances were made until John Napier devised his numbering rods, or Napiers Bones, in 1617. The 17th century marked the beginning of the history of mechanical calculators, as it saw the invention of its first machines, including Pascals calculator, Blaise Pascal invented a mechanical calculator with a sophisticated carry mechanism in 1642. After three years of effort and 50 prototypes he introduced his calculator to the public and he built twenty of these machines in the following ten years. This machine could add and subtract two numbers directly and multiply and divide by repetition and this suggests that the carry mechanism would have proved itself in practice many times over. Pascals invention of the machine, just three hundred years ago, was made while he was a youth of nineteen
13.
Truth value
–
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth. In classical logic, with its intended semantics, the values are true and untrue or false. This set of two values is called the Boolean domain. Corresponding semantics of logical connectives are truth functions, whose values are expressed in the form of truth tables, logical biconditional becomes the equality binary relation, and negation becomes a bijection which permutes true and false. Conjunction and disjunction are dual with respect to negation, which is expressed by De Morgans laws, assigning values for propositional variables is referred to as valuation. In intuitionistic logic, and more generally, constructive mathematics, statements are assigned a value only if they can be given a constructive proof. It starts with a set of axioms, and a statement is true if you can build a proof of the statement from those axioms, a statement is false if you can deduce a contradiction from it. This leaves open the possibility of statements that have not yet assigned a truth value. Unproven statements in Intuitionistic logic are not given a truth value. Indeed, you can prove that they have no truth value. There are various ways of interpreting Intuitionistic logic, including the Brouwer–Heyting–Kolmogorov interpretation, see also, Intuitionistic Logic - Semantics. Multi-valued logics allow for more than two values, possibly containing some internal structure. For example, on the interval such structure is a total order. Not all logical systems are truth-valuational in the sense that logical connectives may be interpreted as truth functions, but even non-truth-valuational logics can associate values with logical formulae, as is done in algebraic semantics. The algebraic semantics of intuitionistic logic is given in terms of Heyting algebras, Intuitionistic type theory uses types in the place of truth values. Topos theory uses truth values in a sense, the truth values of a topos are the global elements of the subobject classifier. Having truth values in this sense does not make a logic truth valuational
14.
Formal language
–
In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it. The alphabet of a language is the set of symbols, letters. The strings formed from this alphabet are called words, and the words belong to a particular formal language are sometimes called well-formed words or well-formed formulas. A formal language is defined by means of a formal grammar such as a regular grammar or context-free grammar. The field of language theory studies primarily the purely syntactical aspects of such languages—that is. Formal language theory sprang out of linguistics, as a way of understanding the syntactic regularities of natural languages. The first formal language is thought to be the one used by Gottlob Frege in his Begriffsschrift, literally meaning concept writing, axel Thues early semi-Thue system, which can be used for rewriting strings, was influential on formal grammars. The elements of an alphabet are called its letters, alphabets may be infinite, however, most definitions in formal language theory specify finite alphabets, and most results only apply to them. A word over an alphabet can be any sequence of letters. The set of all words over an alphabet Σ is usually denoted by Σ*, the length of a word is the number of letters it is composed of. For any alphabet there is one word of length 0, the empty word. By concatenation one can combine two words to form a new word, whose length is the sum of the lengths of the original words, the result of concatenating a word with the empty word is the original word. A formal language L over an alphabet Σ is a subset of Σ*, that is, sometimes the sets of words are grouped into expressions, whereas rules and constraints may be formulated for the creation of well-formed expressions. In computer science and mathematics, which do not usually deal with natural languages, in practice, there are many languages that can be described by rules, such as regular languages or context-free languages. The notion of a formal grammar may be closer to the concept of a language. By an abuse of the definition, a formal language is often thought of as being equipped with a formal grammar that describes it. The following rules describe a formal language L over the alphabet Σ =, Every nonempty string that does not contain + or =, a string containing = is in L if and only if there is exactly one =, and it separates two valid strings of L. A string containing + but not = is in L if, no string is in L other than those implied by the previous rules
15.
Wilhelm Ackermann
–
Wilhelm Friedrich Ackermann was a German mathematician best known for the Ackermann function, an important example in the theory of computation. Ackermann was born in Herscheid municipality, Germany, and was awarded a Ph. D, from 1929 until 1948, he taught at the Arnoldinum Gymnasium in Burgsteinfurt, and then at Lüdenscheid until 1961. He was also a member of the Akademie der Wissenschaften in Göttingen. In 1928, Ackermann helped David Hilbert turn his 1917 –22 lectures on mathematical logic into a text. This text contained the first exposition ever of first-order logic, and posed the problem of its completeness, Ackermann went on to construct consistency proofs for set theory, full arithmetic, type-free logic, and a new axiomatization of set theory. Ackermann coding Ackermann ordinal Ackermann set theory Ackermann function Inverse Ackermann function 1928, on Hilberts construction of the real numbers in Jean van Heijenoort, ed.1967. From Frege to Gödel, A Source Book in Mathematical Logic, zur Widerspruchtfreisheit der Zahlentheorie, Mathematische Annalen, vol. Solvable cases of the decision problem, oConnor, John J. Robertson, Edmund F. Wilhelm Ackermann, MacTutor History of Mathematics archive, University of St Andrews. Wilhelm Ackermann at the Mathematics Genealogy Project Erich Friedmans page on Ackermann at Stetson University Hermes, In memoriam WILHELM ACKERMANN 1896-1962 Author profile in the database zbMATH
16.
Paul Bernays
–
Paul Isaac Bernays was a Swiss mathematician, who made significant contributions to mathematical logic, axiomatic set theory, and the philosophy of mathematics. He was an assistant and close collaborator of David Hilbert, Bernays spent his childhood in Berlin, and attended the Köllner Gymnasium, 1895-1907. At the University of Göttingen, he studied mathematics under David Hilbert, Edmund Landau, Hermann Weyl, and Felix Klein, physics under Voigt and Max Born, and philosophy under Leonard Nelson. In 1912, the University of Berlin awarded him a Ph. D. in mathematics, for a thesis, supervised by Landau and that same year, the University of Zurich awarded him the Habilitation for a thesis on complex analysis and Picards theorem. Bernays was Privatdozent at the University of Zurich, 1912–17, where he came to know George Pólya, starting in 1917, David Hilbert employed Bernays to assist him with his investigations of the foundations of arithmetic. Bernays also lectured on areas of mathematics at the University of Göttingen. In 1918, that university awarded him a second Habilitation, for a thesis on the axiomatics of the calculus of Principia Mathematica. In 1922, Göttingen appointed Bernays extraordinary professor without tenure and his most successful student there was Gerhard Gentzen. In 1933, he was dismissed from this post because of his Jewish ancestry, after working privately for Hilbert for six months, Bernays and his family moved to Switzerland, whose nationality he had inherited from his father, and where the ETH employed him on occasion. He also visited the University of Pennsylvania and was a scholar at the Institute for Advanced Study in 1935-36. Bernayss collaboration with Hilbert culminated in the two volume work Grundlagen der Mathematik by Hilbert and Bernays, discussed in Sieg and Ravaglia, von Neumanns theory took the notions of function and argument as primitive, Bernays recast von Neumanns theory so that classes and sets were primitive. Bernayss theory, with modifications by Kurt Gödel, is now known as von Neumann–Bernays–Gödel set theory. A proof from the Grundlagen der Mathematik that a strong consistent theory cannot contain its own reference functor is now known as the Hilbert–Bernays paradox. Hilbert, David, Bernays, Paul, Grundlagen der Mathematik, II, Die Grundlehren der mathematischen Wissenschaften,50, Berlin, New York, Springer-Verlag, ISBN 978-3-540-05110-7, JFM65.0021. Mathematical Logic and the Foundation of Mathematics, a gentle introduction to some of the ideas in the Grundlagen der Mathematic. Sets and classes. 1007/BF01801939, ISSN 0044-2216, MR546580 Sieg, Wilfried, Ravaglia, Mark, Hilbert Bernays Project OConnor, John J. Robertson, Edmund F. Paul Bernays, MacTutor History of Mathematics archive, University of St Andrews
17.
Multiple discovery
–
The concept of multiple discovery is the hypothesis that most scientific discoveries and inventions are made independently and more or less simultaneously by multiple scientists and inventors. The concept of multiple discovery opposes a traditional view—the heroic theory of invention, historians and sociologists have remarked on the occurrence, in science, of multiple independent discovery. Robert K. Merton defined such multiples as instances in which similar discoveries are made by working independently of each other. Merton contrasted a multiple with a singleton — a discovery that has been made uniquely by a single scientist or group of working together. As Merton said, Sometimes the discoveries are simultaneous or almost so, sometimes a scientist will make a new discovery which, unknown to him, somebody else has made years before. Commonly cited examples of multiple independent discovery are the 17th-century independent formulation of calculus by Isaac Newton, Gottfried Wilhelm Leibniz and others, what holds for discoveries, also goes for inventions. Examples are the blast furnace, the crossbow, and magnetism, Multiple independent discovery, however, is not limited to only a few historic instances involving giants of scientific research. Merton believed that it is multiple discoveries, rather than unique ones, Multiple discoveries in the history of science provide evidence for evolutionary models of science and technology, such as memetics, evolutionary epistemology, and cultural selection theory. A recombinant-DNA-inspired paradigm of paradigms has been posited, that describes a mechanism of recombinant conceptualization and this paradigm predicates that a new concept arises through the crossing of pre-existing concepts and facts. This is what is meant when one says that a scientist or artist has been influenced by another—etymologically, not every new concept so formed will be viable, adapting social Darwinist Herbert Spencers phrase, only the fittest concepts survive. Gutenbergs invention of printing substantially facilitated the transition from the Middle Ages to modern times, all these communication developments have catalyzed and accelerated the process of recombinant conceptualization, and thus also of multiple independent discovery. Multiple independent discoveries show an increased incidence beginning in the 17th century and it is the recurrence of patterns that lends a degree of prognostic power—and, thus, additional scientific validity—to the findings of history. Lamb and Easton, and others, have argued that science, discoverers understandably take pleasure in their accomplishments and generally seek to claim primacy to their discoveries. When it transpires that a discovery has multiple originators, they may agree to share the credit or insist on their own exclusive primacy. In 1699, however, a Swiss mathematician suggested to Britains Royal Society that Leibniz had borrowed his calculus from Newton, in 1705 Leibniz, in an anonymous review of Newtons Opticks, implied that Newtons fluxions were an adaptation of Leibnizs calculus. In 1712 the Royal Society appointed a committee to examine the documents in question, the same year and it is now accepted that Newton and Leibniz discovered calculus independently of each other. In another classic case of discovery, the two discoverers showed more civility. The letter summarized Wallaces theory of selection, with conclusions identical to Darwins own
18.
Stephen Cole Kleene
–
Stephen Cole Kleene /ˈkleɪniː/ KLAY-nee was an American mathematician. Kleenes work grounds the study of functions are computable. A number of concepts are named after him, Kleene hierarchy, Kleene algebra, the Kleene star, Kleenes recursion theorem. He also invented regular expressions, and made significant contributions to the foundations of mathematical intuitionism, although his last name is commonly pronounced /ˈkliːniː/ KLEE-nee or /ˈkliːn/ kleen, Kleene himself pronounced it /ˈkleɪniː/ KLAY-nee. His son, Ken Kleene, wrote, As far as I am aware this pronunciation is incorrect in all known languages, I believe that this novel pronunciation was invented by my father. Kleene was awarded the BA degree from Amherst College in 1930 and he was awarded the Ph. D. in mathematics from Princeton University in 1934. His thesis, entitled A Theory of Positive Integers in Formal Logic, was supervised by Alonzo Church, in the 1930s, he did important work on Churchs lambda calculus. In 1935, he joined the department at the University of Wisconsin–Madison. After two years as an instructor, he was appointed assistant professor in 1937, while a visiting scholar at the Institute for Advanced Study in Princeton, 1939–40, he laid the foundation for recursion theory, an area that would be his lifelong research interest. In 1941, he returned to Amherst College, where he spent one year as a professor of mathematics. During World War II, Kleene was a lieutenant commander in the United States Navy. He was an instructor of navigation at the U. S. Naval Reserves Midshipmens School in New York, in 1946, Kleene returned to Wisconsin, becoming a full professor in 1948 and the Cyrus C. MacDuffee professor of mathematics in 1964 and he was chair of the Department of Mathematics and Computer Science, 1962–63, and Dean of the College of Letters and Science from 1969 to 1974. The latter appointment he took on despite the considerable student unrest of the day and he retired from the University of Wisconsin in 1979. In 1999 the mathematics library at the University of Wisconsin was renamed in his honor, Kleenes teaching at Wisconsin resulted in three texts in mathematical logic, Kleene and Kleene and Vesley, often cited and still in print. Kleene wrote alternative proofs to the Gödels incompleteness theorems that enhanced their status and made them easier to teach. Kleene and Vesley is the classic American introduction to intuitionist logic, Kleene served as president of the Association for Symbolic Logic, 1956–58, and of the International Union of History and Philosophy of Science,1961. In 1990, he was awarded the National Medal of Science, the importance of Kleenes work led to the saying that Kleeneness is next to Gödelness
19.
Diophantine equation
–
In mathematics, a Diophantine equation is a polynomial equation, usually in two or more unknowns, such that only the integer solutions are sought or studied. A linear Diophantine equation is an equation between two sums of monomials of degree zero or one, an exponential Diophantine equation is one in which exponents on terms can be unknowns. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations, in more technical language, they define an algebraic curve, algebraic surface, or more general object, and ask about the lattice points on it. The mathematical study of Diophantine problems that Diophantus initiated is now called Diophantine analysis, the solutions are described by the following theorem, This Diophantine equation has a solution if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if is a solution, then the solutions have the form, where k is an arbitrary integer. Proof, If d is this greatest common divisor, Bézouts identity asserts the existence of integers e and f such that ae + bf = d, If c is a multiple of d, then c = dh for some integer h, and is a solution. On the other hand, for pair of integers x and y. Thus, if the equation has a solution, then c must be a multiple of d. If a = ud and b = vd, then for every solution, we have a + b = ax + by + k = ax + by + k = ax + by, showing that is another solution. Finally, given two solutions such that ax1 + by1 = ax2 + by2 = c, one deduces that u + v =0. As u and v are coprime, Euclids lemma shows that exists a integer k such that x2 − x1 = kv. Therefore, x2 = x1 + kv and y2 = y1 − ku, the system to be solved may thus be rewritten as B = UC. Calling yi the entries of V−1X and di those of D = UC and it follows that the system has a solution if and only if bi, i divides di for i ≤ k and di =0 for i > k. If this condition is fulfilled, the solutions of the system are V. Hermite normal form may also be used for solving systems of linear Diophantine equations, however, Hermite normal form does not directly provide the solutions, to get the solutions from the Hermite normal form, one has to successively solve several linear equations. Nevertheless, Richard Zippel wrote that the Smith normal form is more than is actually needed to solve linear diophantine equations. Instead of reducing the equation to diagonal form, we only need to make it triangular, the Hermite normal form is substantially easier to compute than the Smith normal form. Integer linear programming amounts to finding some integer solutions of systems that include also inequations
20.
Yuri Matiyasevich
–
Yuri Vladimirovich Matiyasevich, is a Russian mathematician and computer scientist. He is best known for his solution of Hilberts tenth problem. As a winner of IMO Yuri Matiyasevich was accepted without exams to LSU, in 1966, he presented a talk at International Congress of Mathematicians held in Moscow. He was an undergraduate student at that time. In 1969–1970, he pursued Ph. D. studies at Leningrad Department of Steklov Institute of Mathematics under supervision of Sergey Maslov, in 1970, he received his Ph. D. degree at LOMI. In 1970–1974, he was a researcher at LOMI, in 1972, he obtained a second doctoral degree. In 1974–1980, he was a researcher at LOMI. Since 1980, Yuri Matiyasevich has been the head of Laboratory of mathematical logic at LOMI, since 1995, he has been a professor of Saint-Petersburg State University, initially at the chair of software engineering, later at the chair of algebra and number theory. In 1997, he was elected as a member of Russian Academy of Sciences. Since 1998, Yuri Matiyasevich has been a vice-president of St. Petersburg Mathematical Society, since 2002, he has been a head of St. Petersburg City Mathematical Olympiad. Since 2003, Matiyasevich has been a co-director of annual German–Russian student school JASS, in 2008, he was elected as a full member of Russian Academy of Sciences. 1964, Gold medal at the International Mathematical Olympiad held in Moscow,1970, Young mathematician prize of the Leningrad Mathematical Society. 1980, Markov Prize of Academy of Sciences of the USSR,1998, He received Humboldt Research Award to Outstanding Scholars. 2003, Honorary Degree, Université Pierre et Marie Curie,2007, Member of the Bayern Academy of Sciences. A polynomial related to the colorings of a triangulation of a sphere was named after Matiyasevich, see The Matiyasevich polynomial, four colour theorem, notable students include, Eldar Musayev, Maxim Vsemirnov, Alexei Pastor, Dmitri Karpov. Yuri Matiyasevich Hilberts 10th Problem, Foreword by Martin Davis and Hilary Putnam, real-time recognition of the inclusion relation. Reduction of an arbitrary Diophantine equation to one in 13 unknowns, decision Problems for Semi-Thue Systems with a Few Rules. Yuri Matiyasevich, Proof Procedures as Bases for Metamathematical Proofs in Discrete Mathematics, Yuri Matiyasevich, Elimination of bounded universal quantifiers standing in front of a quantifier-free arithmetical formula, Personal Journal of Yuri Matiyasevich
21.
Programming language
–
A programming language is a formal computer language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to programs to control the behavior of a machine or to express algorithms. From the early 1800s, programs were used to direct the behavior of such as Jacquard looms. Thousands of different programming languages have created, mainly in the computer field. Many programming languages require computation to be specified in an imperative form while other languages use forms of program specification such as the declarative form. The description of a language is usually split into the two components of syntax and semantics. Some languages are defined by a document while other languages have a dominant implementation that is treated as a reference. Some languages have both, with the language defined by a standard and extensions taken from the dominant implementation being common. A programming language is a notation for writing programs, which are specifications of a computation or algorithm, some, but not all, authors restrict the term programming language to those languages that can express all possible algorithms. For example, PostScript programs are created by another program to control a computer printer or display. More generally, a language may describe computation on some, possibly abstract. It is generally accepted that a specification for a programming language includes a description, possibly idealized. In most practical contexts, a programming language involves a computer, consequently, abstractions Programming languages usually contain abstractions for defining and manipulating data structures or controlling the flow of execution. Expressive power The theory of computation classifies languages by the computations they are capable of expressing, all Turing complete languages can implement the same set of algorithms. ANSI/ISO SQL-92 and Charity are examples of languages that are not Turing complete, markup languages like XML, HTML, or troff, which define structured data, are not usually considered programming languages. Programming languages may, however, share the syntax with markup languages if a computational semantics is defined, XSLT, for example, is a Turing complete XML dialect. Moreover, LaTeX, which is used for structuring documents. The term computer language is used interchangeably with programming language
22.
Natural number
–
In mathematics, the natural numbers are those used for counting and ordering. In common language, words used for counting are cardinal numbers, texts that exclude zero from the natural numbers sometimes refer to the natural numbers together with zero as the whole numbers, but in other writings, that term is used instead for the integers. These chains of extensions make the natural numbers canonically embedded in the number systems. Properties of the numbers, such as divisibility and the distribution of prime numbers, are studied in number theory. Problems concerning counting and ordering, such as partitioning and enumerations, are studied in combinatorics, the most primitive method of representing a natural number is to put down a mark for each object. Later, a set of objects could be tested for equality, excess or shortage, by striking out a mark, the first major advance in abstraction was the use of numerals to represent numbers. This allowed systems to be developed for recording large numbers, the ancient Egyptians developed a powerful system of numerals with distinct hieroglyphs for 1,10, and all the powers of 10 up to over 1 million. A stone carving from Karnak, dating from around 1500 BC and now at the Louvre in Paris, depicts 276 as 2 hundreds,7 tens, and 6 ones, and similarly for the number 4,622. A much later advance was the development of the idea that 0 can be considered as a number, with its own numeral. The use of a 0 digit in place-value notation dates back as early as 700 BC by the Babylonians, the Olmec and Maya civilizations used 0 as a separate number as early as the 1st century BC, but this usage did not spread beyond Mesoamerica. The use of a numeral 0 in modern times originated with the Indian mathematician Brahmagupta in 628, the first systematic study of numbers as abstractions is usually credited to the Greek philosophers Pythagoras and Archimedes. Some Greek mathematicians treated the number 1 differently than larger numbers, independent studies also occurred at around the same time in India, China, and Mesoamerica. In 19th century Europe, there was mathematical and philosophical discussion about the nature of the natural numbers. A school of Naturalism stated that the numbers were a direct consequence of the human psyche. Henri Poincaré was one of its advocates, as was Leopold Kronecker who summarized God made the integers, in opposition to the Naturalists, the constructivists saw a need to improve the logical rigor in the foundations of mathematics. In the 1860s, Hermann Grassmann suggested a recursive definition for natural numbers thus stating they were not really natural, later, two classes of such formal definitions were constructed, later, they were shown to be equivalent in most practical applications. The second class of definitions was introduced by Giuseppe Peano and is now called Peano arithmetic and it is based on an axiomatization of the properties of ordinal numbers, each natural number has a successor and every non-zero natural number has a unique predecessor. Peano arithmetic is equiconsistent with several systems of set theory
23.
Peano axioms
–
These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete. In 1881, Charles Sanders Peirce provided an axiomatization of natural-number arithmetic, the Peano axioms contain three types of statements. The first axiom asserts the existence of at least one member of the set of natural numbers, the next four are general statements about equality, in modern treatments these are often not taken as part of the Peano axioms, but rather as axioms of the underlying logic. The next three axioms are first-order statements about natural numbers expressing the fundamental properties of the successor operation, the ninth, final axiom is a second order statement of the principle of mathematical induction over the natural numbers. When Peano formulated his axioms, the language of logic was in its infancy. Peano was unaware of Freges work and independently recreated his logical apparatus based on the work of Boole, the Peano axioms define the arithmetical properties of natural numbers, usually represented as a set N or N. The non-logical symbols for the axioms consist of a constant symbol 0, the first axiom states that the constant 0 is a natural number, The next four axioms describe the equality relation. Since they are valid in first-order logic with equality, they are not considered to be part of the Peano axioms in modern treatments. The remaining axioms define the properties of the natural numbers. The naturals are assumed to be closed under a successor function S. Peanos original formulation of the axioms used 1 instead of 0 as the first natural number. This choice is arbitrary, as axiom 1 does not endow the constant 0 with any additional properties, however, because 0 is the additive identity in arithmetic, most modern formulations of the Peano axioms start from 0. Axioms 1,6,7,8 define a representation of the intuitive notion of natural numbers. However, considering the notion of natural numbers as can be derived from the axioms, axioms 1,6,7,8 do not imply that the successor function generates all the natural numbers different from 0. Put differently, they do not guarantee that every natural number other than zero must succeed some other natural number, the intuitive notion that all natural numbers observe a succession relation with one or two other numbers requires an additional axiom, which is sometimes called the axiom of induction. The induction axiom is stated in the following form, In Peanos original formulation. It is now common to replace this second-order principle with a weaker first-order induction scheme, there are important differences between the second-order and first-order formulations, as discussed in the section § Models below. The Peano axioms can be augmented with the operations of addition and multiplication, the respective functions and relations are constructed in set theory or second-order logic, and can be shown to be unique using the Peano axioms. Addition is a function that maps two natural numbers to another one and it is defined recursively as, a +0 = a, a + S = S
24.
Boolean satisfiability problem
–
In computer science, the Boolean Satisfiability Problem is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable, on the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula a AND NOT b is satisfiable because one can find the values a = TRUE and b = FALSE, in contrast, a AND NOT a is unsatisfiable. SAT is one of the first problems that was proven to be NP-complete and this means that all problems in the complexity class NP, which includes a wide range of natural decision and optimization problems, are at most as difficult to solve as SAT. g. Artificial intelligence, circuit design, and automatic theorem proving, a propositional logic formula, also called Boolean expression, is built from variables, operators AND, OR, NOT, and parentheses. A formula is said to be if it can be made TRUE by assigning appropriate logical values to its variables. The Boolean satisfiability problem is, given a formula, to whether it is satisfiable. This decision problem is of importance in various areas of computer science, including theoretical computer science, complexity theory, algorithmics, cryptography. There are several cases of the Boolean satisfiability problem in which the formulas are required to have a particular structure. A literal is either a variable, then called positive literal, or the negation of a variable, a clause is a disjunction of literals. A clause is called a Horn clause if it contains at most one positive literal, a formula is in conjunctive normal form if it is a conjunction of clauses. The formula is satisfiable, choosing x1 = FALSE, x2 = FALSE, and x3 arbitrarily, since ∧ ∧ ¬FALSE evaluates to ∧ ∧ TRUE, and in turn to TRUE ∧ TRUE ∧ TRUE. In contrast, the CNF formula a ∧ ¬a, consisting of two clauses of one literal, is unsatisfiable, since for a=TRUE and a=FALSE it evaluates to TRUE ∧ ¬TRUE and FALSE ∧ ¬FALSE, different sets of allowed boolean operators lead to different problem versions. As an example, R is a clause, and R ∧ R ∧ R is a generalized conjunctive normal form. This formula is used below, with R being the operator that is TRUE just if exactly one of its arguments is. Using the laws of Boolean algebra, every propositional logic formula can be transformed into an equivalent conjunctive normal form, for example, transforming the formula ∨ ∨. ∨ into conjunctive normal form yields ∧ ∧ ∧ ∧, ∧ ∧ ∧ ∧, while the former is a disjunction of n conjunctions of 2 variables, the latter consists of 2n clauses of n variables
25.
DPLL algorithm
–
Especially in older publications, the Davis–Logemann–Loveland algorithm is often referred to as the “Davis–Putnam method” or the “DP algorithm”. Other common names that maintain the distinction are DLL and DPLL, after more than 50 years the DPLL procedure still forms the basis for most efficient complete SAT solvers. It has recently extended for automated theorem proving for fragments of first-order logic. The SAT problem is important both from theoretical and practical points of view, as such, it was and still is a hot topic in research for many years, and competitions between SAT solvers regularly take place. DPLLs modern implementations like Chaff and zChaff, GRASP or Minisat are in the first places of the competitions these last years and this is known as the splitting rule, as it splits the problem into two simpler sub-problems. The simplification step essentially removes all clauses that become true under the assignment from the formula, in practice, this often leads to deterministic cascades of units, thus avoiding a large part of the naive search space. Pure literal elimination If a propositional variable occurs with only one polarity in the formula, pure literals can always be assigned in a way that makes all clauses containing them true. Thus, these clauses do not constrain the search anymore and can be deleted, unsatisfiability of a given partial assignment is detected if one clause becomes empty, i. e. if all its variables have been assigned in a way that makes the corresponding literals false. Satisfiability of the formula is detected either when all variables are assigned without generating the empty clause, or, in modern implementations, unsatisfiability of the complete formula can only be detected after exhaustive search. In other words, they replace every occurrence of l with true and every occurrence of not l with false in the formula Φ, the or in the return statement is a short-circuiting operator. Φ ∧ l denotes the simplified result of substituting true for l in Φ, the pseudocode DPLL function only returns whether the final assignment satisfies the formula or not. In a real implementation, the partial satisfying assignment typically is also returned on success, the Davis–Logemann–Loveland algorithm depends on the choice of branching literal, which is the literal considered in the backtracking step. As a result, this is not exactly an algorithm, but rather a family of algorithms, efficiency is strongly affected by the choice of the branching literal, there exist instances for which the running time is constant or exponential depending on the choice of the branching literals. Such choice functions are also called heuristic functions or branching heuristics, Davis, Logemann, Loveland had developed this algorithm. Some properties of this algorithm are, It is based on search. It is the basis for almost all modern SAT solvers and it DOES NOT use learning and chronological backtracking. Defining new data structures to make the algorithm faster, especially the part on unit propagation Defining variants of the backtracking algorithm. The latter direction include non-chronological backtracking and clause learning and these refinements describe a method of backtracking after reaching a conflict clause which learns the root causes of the conflict in order to avoid reaching the same conflict again
26.
Simplex algorithm
–
In mathematical optimization, Dantzigs simplex algorithm is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, the simplicial cones in question are the corners of a geometric object called a polytope. The shape of this polytope is defined by the applied to the objective function. There is a process to convert any linear program into one in standard form so this results in no loss of generality. In geometric terms, the region defined by all values of x such that A x ≤ b, x i ≥0 is a convex polytope. In this context such a point is known as a feasible solution. It can be shown that for a program in standard form. The simplex algorithm applies this insight by walking along edges of the polytope to extreme points with greater and greater objective values and this continues until the maximum value is reached or an unbounded edge is visited, concluding that the problem has no solution. The solution of a program is accomplished in two steps. In the first step, known as Phase I, an extreme point is found. Depending on the nature of the program this may be trivial, the possible results of Phase I are either that a basic feasible solution is found or that the feasible region is empty. In the latter case the program is called infeasible. In the second step, Phase II, the algorithm is applied using the basic feasible solution found in Phase I as a starting point. The possible results from Phase II are either a basic feasible solution or an infinite edge on which the objective function is unbounded below. George Dantzig worked on planning methods for the US Army Air Force during World War II using a desk calculator, during 1946 his colleague challenged him to mechanize the planning process in order to entice him into not taking another job. Dantzig formulated the problem as linear inequalities inspired by the work of Wassily Leontief, however, Dantzigs core insight was to realize that most such ground rules can be translated into a linear objective function that needs to be maximized. Development of the method was evolutionary and happened over a period of about a year
27.
Automated theorem proving
–
Automated theorem proving is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was an impetus for the development of computer science. While the roots of formalised logic go back to Aristotle, the end of the 19th and early 20th centuries saw the development of modern logic, freges Begriffsschrift introduced both a complete propositional calculus and what is essentially modern predicate logic. His Foundations of Arithmetic, published 1884, expressed mathematics in formal logic and this approach was continued by Russell and Whitehead in their influential Principia Mathematica, first published 1910–1913, and with a revised second edition in 1927. Russell and Whitehead thought they could derive all mathematical truth using axioms and inference rules of formal logic, shortly after World War II, the first general purpose computers became available. In 1954, Martin Davis programmed Presburgers algorithm for a JOHNNIAC vacuum tube computer at the Princeton Institute for Advanced Study, according to Davis, Its great triumph was to prove that the sum of two even numbers is even. More ambitious was the Logic Theory Machine, a system for the propositional logic of the Principia Mathematica, developed by Allen Newell, Herbert A. Simon. The system used heuristic guidance, and managed to prove 38 of the first 52 theorems of the Principia, the heuristic approach of the Logic Theory Machine tried to emulate human mathematicians, and could not guarantee that a proof could be found for every valid theorem even in principle. In contrast, other, more systematic algorithms achieved, at least theoretically, the propositional formulas could then be checked for unsatisfiability using a number of methods. Gilmores program used conversion to disjunctive normal form, a form in which the satisfiability of a formula is obvious, depending on the underlying logic, the problem of deciding the validity of a formula varies from trivial to impossible. For the frequent case of logic, the problem is decidable but Co-NP-complete. However, invalid formulas, cannot always be recognized, the above applies to first order theories, such as Peano Arithmetic. However, for a model that may be described by a first order theory, some statements may be true. Despite this theoretical limit, in practice, theorem provers can solve many hard problems, a simpler, but related, problem is proof verification, where an existing proof for a theorem is certified valid. For this, it is required that each individual proof step can be verified by a primitive recursive function or program. Proof assistants require a user to give hints to the system. However, these successes are sporadic, and work on hard problems usually requires a proficient user, other techniques would include model checking, which, in the simplest case, involves brute-force enumeration of many possible states. There are hybrid theorem proving systems which use model checking as an inference rule, there are also programs which were written to prove a particular theorem, with a proof that if the program finishes with a certain result, then the theorem is true
The dictionary definition of entscheidungsproblem at Wiktionary