A report on Computer science and Computability theory

Charles Babbage, sometimes referred to as the "father of computing".
Ada Lovelace published the first algorithm intended for processing on a computer.

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

- Computability theory

In an effort to answer the first question, computability theory examines which computational problems are solvable on various theoretical models of computation.

- Computer science
Charles Babbage, sometimes referred to as the "father of computing".

6 related topics with Alpha

Overall
3rd century BC Greek mathematician Euclid (holding calipers), as imagined by Raphael in this detail from The School of Athens (1509–1511)

Mathematics

2 links

Area of knowledge that includes such topics as numbers , formulas and related structures (algebra), shapes and the spaces in which they are contained (geometry), and quantities and their changes (calculus and analysis).

Area of knowledge that includes such topics as numbers , formulas and related structures (algebra), shapes and the spaces in which they are contained (geometry), and quantities and their changes (calculus and analysis).

3rd century BC Greek mathematician Euclid (holding calipers), as imagined by Raphael in this detail from The School of Athens (1509–1511)
The distribution of prime numbers is a central point of study in number theory. This Ulam spiral serves to illustrate it, hinting, in particular, at the conditional independence between being prime and being a value of certain quadratic polynomials.
The quadratic formula expresses concisely the solutions of all quadratic equations
Rubik's cube: the study of its possible moves is a concrete application of group theory
The Babylonian mathematical tablet Plimpton 322, dated to 1800 BC.
Archimedes used the method of exhaustion, depicted here, to approximate the value of pi.
The numerals used in the Bakhshali manuscript, dated between the 2nd century BC and the 2nd century AD.
A page from al-Khwārizmī's Algebra
Leonardo Fibonacci, the Italian mathematician who introduced the Hindu–Arabic numeral system invented between the 1st and 4th centuries by Indian mathematicians, to the Western World.
Leonhard Euler created and popularized much of the mathematical notation used today.
Carl Friedrich Gauss, known as the prince of mathematicians
The front side of the Fields Medal
Euler's identity, which American physicist Richard Feynman once called "the most remarkable formula in mathematics".

Mathematics is essential in many fields, including natural sciences, engineering, medicine, finance, computer science and social sciences.

Other first-level areas emerged during the 20th century (for example category theory; homological algebra, and computer science) or had not previously been considered as mathematics, such as Mathematical logic and foundations (including model theory, computability theory, set theory, proof theory, and algebraic logic).

Mathematical logic

2 links

Study of formal logic within mathematics.

Study of formal logic within mathematics.

Major subareas include model theory, proof theory, set theory, and recursion theory.

Computer scientists often focus on concrete programming languages and feasible computability, while researchers in mathematical logic often focus on computability as a theoretical concept and on noncomputability.

Flowchart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" or "true" (more accurately, the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).

Algorithm

1 links

Flowchart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" or "true" (more accurately, the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).
Ada Lovelace's diagram from "note G", the first published computer algorithm
Logical NAND algorithm implemented electronically in 7400 chip
Flowchart examples of the canonical Böhm-Jacopini structures: the SEQUENCE (rectangles descending the page), the WHILE-DO and the IF-THEN-ELSE. The three structures are made of the primitive conditional GOTO (IF test THEN GOTO step xxx, shown as diamond), the unconditional GOTO (rectangle), various assignment operators (rectangle), and HALT (rectangle). Nesting of these structures inside assignment-blocks result in complex diagrams (cf. Tausworthe 1977:100, 114).
The example-diagram of Euclid's algorithm from T.L. Heath (1908), with more detail added. Euclid does not go beyond a third measuring and gives no numerical examples. Nicomachus gives the example of 49 and 21: "I subtract the less from the greater; 28 is left; then again I subtract from this the same 21 (for this is possible); 7 is left; I subtract this from 21, 14 is left; from which I again subtract 7 (for this is possible); 7 is left, but 7 cannot be subtracted from 7." Heath comments that "The last phrase is curious, but the meaning of it is obvious enough, as also the meaning of the phrase about ending 'at one and the same number'."(Heath 1908:300).
A graphical expression of Euclid's algorithm to find the greatest common divisor for 1599 and 650.
"Inelegant" is a translation of Knuth's version of the algorithm with a subtraction-based remainder-loop replacing his use of division (or a "modulus" instruction). Derived from Knuth 1973:2–4. Depending on the two numbers "Inelegant" may compute the g.c.d. in fewer steps than "Elegant".
Alan Turing's statue at Bletchley Park

In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

Gurevich: '… Turing's informal argument in favor of his thesis justifies a stronger thesis: every algorithm can be simulated by a Turing machine … according to Savage [1987], an algorithm is a computational process defined by a Turing machine'."Turing machines can define computational processes that do not terminate. The informal definitions of algorithms generally require that the algorithm always terminates. This requirement renders the task of deciding whether a formal procedure is an algorithm impossible in the general case—due to a major theorem of computability theory known as the halting problem.

Structure of the syntactically well-formed, although nonsensical, English sentence, "Colorless green ideas sleep furiously" (historical example from Chomsky 1957).

Formal language

1 links

Structure of the syntactically well-formed, although nonsensical, English sentence, "Colorless green ideas sleep furiously" (historical example from Chomsky 1957).
This diagram shows the syntactic divisions within a formal system. Strings of symbols may be broadly divided into nonsense and well-formed formulas. The set of well-formed formulas is divided into theorems and non-theorems.

In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.

Therefore, formal language theory is a major application area of computability theory and complexity theory.

Model of computation

0 links

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input.

An artistic representation of a Turing machine. Turing machines are frequently used as theoretical models for computing.

Theory of computation

0 links

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 .

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 .

An artistic representation of a Turing machine. Turing machines are frequently used as theoretical models for computing.
Set inclusions described by the Chomsky hierarchy
A representation of the relation among complexity classes

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?".

Perhaps the most important open problem in all of computer science is the question of whether a certain broad class of problems denoted NP can be solved efficiently.