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.
Chess
–
Chess is a two-player strategy board game played on a chessboard, a checkered gameboard with 64 squares arranged in an eight-by-eight grid. Chess is played by millions of people worldwide, both amateurs and professionals, each player begins the game with 16 pieces, one king, one queen, two rooks, two knights, two bishops, and eight pawns. Each of the six piece types moves differently, with the most powerful being the queen, the objective is to checkmate the opponents king by placing it under an inescapable threat of capture. To this end, a players pieces are used to attack and capture the opponents pieces, in addition to checkmate, the game can be won by voluntary resignation by the opponent, which typically occurs when too much material is lost, or if checkmate appears unavoidable. A game may result in a draw in several ways. Chess is believed to have originated in India, some time before the 7th century, chaturanga is also the likely ancestor of the Eastern strategy games xiangqi, janggi and shogi. The pieces took on their current powers in Spain in the late 15th century, the first generally recognized World Chess Champion, Wilhelm Steinitz, claimed his title in 1886. Since 1948, the World Championship has been controlled by FIDE, the international governing body. There is also a Correspondence Chess World Championship and a World Computer Chess Championship, online chess has opened amateur and professional competition to a wide and varied group of players. There are also many variants, with different rules, different pieces. FIDE awards titles to skilled players, the highest of which is grandmaster, many national chess organizations also have a title system. However, these are not recognised by FIDE, the term master may refer to a formal title or may be used more loosely for any skilled player. Until recently, chess was a sport of the International Olympic Committee. Chess was included in the 2006 and 2010 Asian Games, since the 1990s, computer analysis has contributed significantly to chess theory, particularly in the endgame. The computer IBM Deep Blue was the first machine to overcome a reigning World Chess Champion in a match when it defeated Garry Kasparov in 1997, the rise of strong computer programs that can be run on hand-held devices has led to increasing concerns about cheating during tournaments. The official rules of chess are maintained by FIDE, chesss international governing body, along with information on official chess tournaments, the rules are described in the FIDE Handbook, Laws of Chess section. Chess is played on a board of eight rows and eight columns. The colors of the 64 squares alternate and are referred to as light, the chessboard is placed with a light square at the right-hand end of the rank nearest to each player
3.
Draughts
–
Draughts or checkers is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. The name derives from the verb to draw or to move, there are many other variants played on an 8×8, and Canadian checkers is played on a 12×12 board. The 8×8 variant of draughts was weakly solved in 2007 by the team of Canadian computer scientist Jonathan Schaeffer, from the standard starting position, both players can guarantee a draw with perfect play. Draughts is played by two opponents, on sides of the gameboard. One player has the pieces, the other has the light pieces. A player may not move an opponents piece, a move consists of moving a piece diagonally to an adjacent unoccupied square. If the adjacent square contains a piece, and the square immediately beyond it is vacant. Only the dark squares of the board are used. A piece may move only diagonally into an unoccupied square, capturing is mandatory in most official rules, although some rule variations make capturing optional when presented. In almost all variants, the player without pieces remaining, or who cannot move due to being blocked, uncrowned pieces move one step diagonally forward, and capture an opponents piece by moving two consecutive steps in the same line, jumping over the piece on the first step. Multiple opposing pieces may be captured in a single turn provided this is done by successive jumps made by a single piece, in English draughts men can capture only forward, but in international draughts and Russian draughts they may also capture backwards. As with non-king men, a king may make successive jumps in a single turn provided that each jump captures an opponent man or king. In international draughts, kings move any distance along unblocked diagonals, flying kings are not used in English draughts, in which a kings only advantage over a man is the ability to move and capture backwards as well as forwards. Once a game has been gridlocked, where back and forth moves between same locations on the board avoid jumps, the player with the majority of free space wins the games. In most non-English languages, draughts is called dame, dames, damas, the pieces are usually called men, stones, peón or a similar term, men promoted to kings are called dames or ladies. In these languages, the queen in chess or in games is usually called by the same term as the kings in draughts. A case in point includes the Greek terminology, in which draughts is called ντάμα, the World Championship in English draughts began in 1840. The winners in mens have been from the United Kingdom, United States, Barbados, the womens championship in English draughts started in 1993
4.
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
5.
Christos Papadimitriou
–
Christos Harilaos Papadimitriou is a Greek theoretical computer scientist, and professor of Computer Science at the University of California, Berkeley. Papadimitriou studied at the National Technical University of Athens, where in 1972 he received his Bachelor of Arts degree in Electrical Engineering. He continued to study at Princeton University, where he received his MS in Electrical Engineering in 1974 and his PhD in Electrical Engineering, Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, and UCSD, and is currently the C. Lester Hogan Professor of Electrical Engineering and Computer Science at U. C, in 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize. He became fellow of the U. S. National Academy of Engineering for contributions to complexity theory, database theory, in 2009 he was elected to the US National Academy of Sciences. During the 36th International Colloquium on Automata, Languages and Programming, in 2012, he, along with Elias Koutsoupias, was awarded the Gödel Prize for their joint work on the concept of the price of anarchy. Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of complexity theory. He has also co-authored the textbook Algorithms with Sanjoy Dasgupta and Umesh Vazirani, and his name was listed in the 19th position on the CiteSeer search engine academic database and digital library. In 2011, Papadimitriou received a honoris causa from the National Technical University of Athens. In 2013, Papadimitriou received a honoris causa from the École polytechnique fédérale de Lausanne. Papadimitriou was awarded the IEEE John von Neumann Medal in 2016, the EATCS Award in 2015, the Gödel Prize in 2012, elements of the Theory of Computation. Prentice-Hall,1982, second edition September 1997, Greek edition Combinatorial Optimization, Algorithms and Complexity. Prentice-Hall,1982, second edition, Dover,1998, the Theory of Database Concurrency Control. A compilation of articles written for the Greek newspaper To Vima, mcGraw-Hill, September 2006 Logicomix, An Epic Search for Truth. Bloomsbury Publishing and Bloomsbury USA, September 2009 and he co-authored a paper with Bill Gates, co-founder of Microsoft. At UC Berkeley, in 2006, he joined a professor-and-graduate-student band called Lady X and The Positive Eigenvalues
6.
Aviezri Fraenkel
–
Aviezri Siegmund Fraenkel is an Israeli mathematician who has made notable contributions to combinatorial game theory. Aviezri Siegmund Fraenkel was born in Munich, Germany, but his family moved to Switzerland soon after, in 1939 his family moved once more, to Jerusalem. Fraenkel is married to Shaula and father of six, one of his grandchildren, Yaacov Naftali Fraenkel, was kidnapped and murdered by Hamas members in June 2014. Fraenkel received his Ph. D. in 1961 from the University of California and he was a recipient of the 2005 Euler Medal. On December 5,2006, he received the WEIZAC Medal from the IEEE, as a member of the team built the WEIZAC. Fraenkel was the founder of the Bar Ilan Responsa Project, serving as its initial director and his research also delves into computational complexity, as it is important to study the complexity of algorithms which solve games. Biography by Shaula Fraenkel Personal Homepage The official citation from the Israel Prize for the Responsa Project The official Responsa Project CV from the Israel Prize committee
