Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed; the machine operates on an infinite memory tape divided into discrete "cells". The machine positions its "head" over a cell and "reads" or "scans" the symbol there; as per the symbol and its present place in a "finite table" of user-specified instructions, the machine writes a symbol in the cell either moves the tape one cell left or right either proceeds to a subsequent instruction or halts the computation. The Turing machine was invented in 1936 by Alan Turing, who called it an "a-machine". With this model, Turing was able to answer two questions in the negative: Does a machine exist that can determine whether any arbitrary machine on its tape is "circular", thus by providing a mathematical description of a simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the Entscheidungsproblem.

Thus, Turing machines prove fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalistic design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory. Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language, Turing complete is theoretically capable of expressing all tasks accomplishable by computers. 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 it is a machine capable of enumerating some arbitrary subset of valid strings of an alphabet. A Turing machine has a tape of infinite length on which it can perform write operations. Assuming a black box, the Turing machine cannot know whether it will enumerate any one specific string of the subset with a given program.

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 further 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, able to simulate any other Turing machine is called a universal Turing machine. A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis; the thesis states that Turing machines indeed capture the informal notion of effective methods in logic and mathematics, provide a precise definition of an algorithm or "mechanical procedure". Studying their abstract properties yields many insights into computer science and complexity theory. In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed.

At any moment there is one symbol in the machine. The machine can alter the scanned symbol, its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. 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 have an innings; the Turing machine mathematically models a machine. On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1. In the original article, Turing imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly. More a Turing machine consists of: A tape divided into cells, one next to the other; each cell contains a symbol from some finite alphabet. The alphabet contains one or more other symbols.

The tape is assumed to be arbitrarily extendable to the left and to the right, i.e. the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol. In some models the tape has a left e

Natural number

In mathematics, the natural numbers are those used for counting and ordering. In common mathematical terminology, words colloquially used for counting are "cardinal numbers" and words connected to ordering represent "ordinal numbers"; the natural numbers can, at times, appear as a convenient set of codes. Some definitions, including the standard ISO 80000-2, begin the natural numbers with 0, corresponding to the non-negative integers 0, 1, 2, 3, …, whereas others start with 1, corresponding to the positive integers 1, 2, 3, …. 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; the natural numbers are a basis from which many other number sets may be built by extension: the integers, by including the neutral element 0 and an additive inverse for each nonzero natural number n. These chains of extensions make the natural numbers canonically embedded in the other number systems.

Properties of the natural 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. In common language, for example in primary school, natural numbers may be called counting numbers both to intuitively exclude the negative integers and zero, to contrast the discreteness of counting to the continuity of measurement, established by the real numbers; the most primitive method of representing a natural number is to put down a mark for each object. A set of objects could be tested for equality, excess or shortage, by striking out a mark and removing an object from the set; 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, 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, 6 ones. The Babylonians had a place-value system based on the numerals for 1 and 10, using base sixty, so that the symbol for sixty was the same as the symbol for one, its value being determined from context. A much 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, but they omitted such a digit when it would have been the last symbol in the number. 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. However, 0 had been used as a number in the medieval computus, beginning with Dionysius Exiguus in 525, without being denoted by a numeral; the first systematic study of numbers as abstractions is credited to the Greek philosophers Pythagoras and Archimedes.

Some Greek mathematicians treated the number 1 differently than larger numbers, sometimes not as a number at all. Independent studies occurred at around the same time in India and Mesoamerica. In 19th century Europe, there was mathematical and philosophical discussion about the exact nature of the natural numbers. A school of Naturalism stated that the natural 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, all else is the work of man". 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 natural but a consequence of definitions. Two classes of such formal definitions were constructed. Set-theoretical definitions of natural numbers were initiated by Frege and he defined a natural number as the class of all sets that are in one-to-one correspondence with a particular set, but this definition turned out to lead to paradoxes including Russell's paradox.

Therefore, this formalism was modified so that a natural number is defined as a particular set, any set that can be put into one-to-one correspondence with that set is said to have that number of elements. The second class of definitions was introduced by Charles Sanders Peirce, refined by Richard Dedekind, further explored by Giuseppe Peano, it is based on an axiomatization of the properties of ordinal numbers: each natural number has a