|
Theory Of Computation
In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: ''"What are the fundamental capabilities and limitations of computers?".'' In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine. Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" mo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alonzo Church
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, the Church–Turing thesis, proving the unsolvability of the Entscheidungsproblem, the Frege–Church ontology, and the Church–Rosser theorem. He also worked on philosophy of language (see e.g. Church 1970). Alongside his student Alan Turing, Church is considered one of the founders of computer science. Life Alonzo Church was born on June 14, 1903, in Washington, D.C., where his father, Samuel Robbins Church, was a Justice of the Peace and the judge of the Municipal Court for the District of Columbia. He was the grandson of Alonzo Webster Church (1829-1909), United States Senate Librarian from 1881-1901, and great grandson of Alonzo Church, a Professor of Mathematics and Astronomy and 6th Pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Finite State Automaton
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of '' states'' at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a ''transition''. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types— deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one. The behavior of state machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are vending machines, which dispense p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Grammar
In theoretical computer science and formal language theory, a regular grammar is a grammar that is ''right-regular'' or ''left-regular''. While their exact definition varies from textbook to textbook, they all require that * all production rules have at most one non-terminal symbol; * that symbol is either always at the end or always at the start of the rule's right-hand side. Every regular grammar describes a regular language. Strictly regular grammars A right-regular grammar (also called right-linear grammar) is a formal grammar (''N'', Σ, ''P'', ''S'') in which all production rules in ''P'' are of one of the following forms: # ''A'' → ''a'' # ''A'' → ''aB'' # ''A'' → ε where ''A'', ''B'', ''S'' ∈ ''N'' are non-terminal symbols, ''a'' ∈ Σ is a terminal symbol, and ε denotes the empty string, i.e. the string of length 0. ''S'' is called the start symbol. In a left-regular grammar, (also called left-linear grammar), all rules obey the forms # ''A'' → ''a'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pushdown Automaton
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines (see below). Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design. The term "pushdown" refers to the fact that the stack can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than pushdown automata. A nested stack automaton allows full access, and also allows stacked values to be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Context-free Grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be empty). A formal grammar is "context-free" if its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar. A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture, :\langle\text\rangle \to \langle\text\rangle = \langle\text\rangle ; replaces \langle\text\rangle with \langle\text\rangle = \langle\text\rangle ;. There can be multiple replacement rules for a given nonterminal symbol. The ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Bounded Automaton
In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine. Operation A linear bounded automaton is a nondeterministic Turing machine that satisfies the following three conditions: * Its input alphabet includes two special symbols, serving as left and right endmarkers. * Its transitions may not print other symbols over the endmarkers. * Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker. In other words: instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers. An alternative, less restrictive definition is as follows: * Like a Turing machine, an LBA possesses a tape made up of cells that can contain symbols from a finite alphabet, a head that can read from or write to one cell on the tape at a time and can be moved, a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Context-sensitive Grammar
A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by CSG but not by context-free grammars. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSG are positioned between context-free and unrestricted grammars in the Chomsky hierarchy. A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language. Some textbooks actually define CSGs as non-contracting, although this is not how Noam Chomsky defined them in 1959. This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equivalent), ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Recursively Enumerable Language
In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable. The class of all recursively enumerable languages is called RE. Definitions There are three equivalent definitions of a recursively enumerable language: # A recursively enumerable language is a recursively enumerable subset in the set of all possible words over the alphabet of the language. # A recursively enumerable language is a formal language for which there exists a Turing mach ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Claude Shannon
Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory". As a 21-year-old master's degree student at the Massachusetts Institute of Technology (MIT), he wrote A Symbolic Analysis of Relay and Switching Circuits, his thesis demonstrating that electrical applications of Boolean algebra could construct any logical numerical relationship. Shannon contributed to the field of cryptanalysis for national defense of the United States during World War II, including his fundamental work on codebreaking and secure telecommunications. Biography Childhood The Shannon family lived in Gaylord, Michigan, and Claude was born in a hospital in nearby Petoskey, Michigan, Petoskey. His father, Claude Sr. (1862–1934), was a businessman and for a while, a judge of probate in Gaylord. His mother, Mabel Wolf Shannon (1890–1945), ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
John Von Neumann
John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest coverage of any mathematician of his time and was said to have been "the last representative of the great mathematicians who were equally at home in both pure and applied mathematics". He integrated pure and applied sciences. Von Neumann made major contributions to many fields, including mathematics (foundations of mathematics, measure theory, functional analysis, ergodic theory, group theory, lattice theory, representation theory, operator algebras, matrix theory, geometry, and numerical analysis), physics (quantum mechanics, hydrodynamics, ballistics, nuclear physics and quantum statistical mechanics), economics ( game theory and general equilibrium theory), computing ( Von Neumann architecture, linear programming, numerical meteo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rózsa Péter
Rózsa Péter, born Rózsa Politzer, (17 February 1905 – 16 February 1977) was a Hungarian mathematician and logician. She is best known as the "founding mother of recursion theory". Early life and education Péter was born in Budapest, Hungary, as Rózsa Politzer (Hungarian: Politzer Rózsa). She attended Pázmány Péter University (now Eötvös Loránd University), originally studying chemistry but later switching to mathematics. She attended lectures by Lipót Fejér and József Kürschák. While at university, she met László Kalmár; they would collaborate in future years and Kalmár encouraged her to pursue her love of mathematics. After graduating in 1927, Péter could not find a permanent teaching position although she had passed her exams to qualify as a mathematics teacher. Due to the effects of the Great Depression, many university graduates could not find work and Péter began private tutoring. At this time, she also began her graduate studies. Professional ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
