Feeds:
Posts
Comments

Archive for June 18th, 2009

Computation

Computation

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Computation is a general term for any type of information processing. This includes phenomena ranging from human thinking to calculations with a more narrow meaning. Computation is a process following a well-defined model that is understood and can be expressed in an algorithm, protocol, network topology, etc. Computation is also a major subject matter of computer science: it investigates what can or cannot be done in a computational manner.

Sister project Look up computation in Wiktionary, the free dictionary.

Contents

[hide]

[edit] Classes of computation

Computation can be classified by at least three orthogonal criteria: digital vs analog, sequential vs parallel vs concurrent, batch vs interactive.

In practice, digital computation is often used to simulate natural processes (for example, Evolutionary computation), including those that are more naturally described by analog models of computation (for example, Artificial neural network). In this situation, it is important to distinguish between the mechanism of computation and the simulated model.

[edit] Computations as a physical phenomenon

A computation can be seen as a purely physical phenomenon occurring inside a closed physical system called a computer. Examples of such physical systems include digital computers, quantum computers, DNA computers, molecular computers, analog computers or wetware computers. This point of view is the one adopted by the branch of theoretical physics called the physics of computation.

An even more radical point of view is the postulate of digital physics that the evolution of the universe itself is a computation – Pancomputationalism.

[edit] Mathematical models of computation

In the theory of computation, a diversity of mathematical models of computers have been developed. Typical mathematical models of computers are the following:

  • State models including Turing Machine, Push-down automaton, Finite state automaton, and PRAM
  • Functional models including lambda calculus
  • Logical models including logic programming
  • Concurrent models including Actor model and process calculi

[edit] History

The word computation has an archaic meaning (from its Latin etymological roots), but the word has come back in use with the arising of a new scientific discipline: computer science.

[edit] See also

Computer Science portal
  This computer science article is a stub. You can help Wikipedia by expanding it.

Read Full Post »

Computational problem

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring

“Given a positive integer n, find a nontrivial prime factor of n.”

is a computational problem. Computational problems are one of the main objects of study in theoretical computer science. The field of algorithms studies methods of solving computational problems efficiently. The complementary field of computational complexity attempts to explain why certain computational problems are intractable for computers.

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. For example in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n.

It is conventional to represent both instances and solutions by binary strings, namely elements of {0, 1}*. For example, numbers can be represented as binary strings using the binary encoding. (For readability, we identify numbers with their binary encodings in the examples below.)

[edit] Types of computational problems

A decision problem is a computational problem where the answer for every instance is either yes or no. An example of a decision problem is primality testing:

“Given a positive integer n, determine if n is prime.”

A decision problem is typically represented as the set of all instances for which the answer is yes. For example, primality testing can be represented as the infinite set

L = {2, 3, 5, 7, 11, …}

In a search problem, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes.

A search problem is represented as a relation over consisting of all the instance-solution pairs, called a search relation. For example, primality can be represented as the relation

R = {(4, 2), (6, 2), (6, 3), (8, 2), (8, 4), (9, 3), …}

which consist of all pairs of numbers (n, p), where p is a nontrivial prime factor of n.

A counting problem asks for the number of solutions to a given search problem. For example, the counting problem associated with primality is

“Given a positive integer n, count the number of nontrivial prime factors of n.”

A counting problem can be represented by a function f from {0, 1}* to the nonnegative integers. For a search relation R, the counting problem associated to R is the function

fR(x) = |{y: (x, y) ∈ R}|.

An optimization problem asks for finding the “best possible” solution among the set of all possible solutions to a search problem. One example is the maximum independent set problem:

“Given a graph G, find an independent set of G of maximum size.”

Optimization problems can be represented by their search relations.

[edit] Promise problems

In computational complexity theory, it is usually implicitly assumed that any string in {0, 1}* represents an instance of the computational problem in question. However, sometimes not all strings {0, 1}* represent valid instances, and one specifies a proper subset of {0, 1}* as the set of “valid instances”. Computational problems of this type are called promise problems.

The following is an example of a (decision) promise problem:

“Given a graph G, determine if G has an independent set of size at most 5, or every independent set in G has size at least 10.”

Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.

Decision promise problems are usually represented as pairs of disjoint subsets (Lyes, Lno) of {0, 1}*. The valid instances are those in LyesLno. Lyes and Lno represent the instances whose answer is yes and no, respectively.

Promise problems play an important role in several areas of computational complexity, including hardness of approximation, property testing, and interactive proof systems.

[edit] References

Read Full Post »

Computer

Computer

From Wikipedia, the free encyclopedia

Jump to: navigation, search

This article is about the machine. For other uses, see Computer (disambiguation).
“Computer technology” redirects here. For the company, see Computer Technology Limited.

This article may be too long to comfortably read and navigate. Please consider splitting content into sub-articles and using this article for a summary of the key points of the subject. (June 2009)

A computer is a machine that manipulates data according to a set of instructions.

Although mechanical examples of computers have existed through much of recorded human history, the first resembling a modern computer were developed in the mid-20th century (1940–1945). The first electronic computers were the size of a large room, consuming as much power as several hundred modern personal computers (PC).[1] Modern computers based on tiny integrated circuits are millions to billions of times more capable than the early machines, and occupy a fraction of the space.[2] Simple computers are small enough to fit into a wristwatch, and can be powered by a watch battery. Personal computers in their various forms are icons of the Information Age, what most people think of as a “computer”, but the embedded computers found in devices ranging from fighter aircraft to industrial robots, digital cameras, and toys are the most numerous.

The ability to store and execute lists of instructions called programs makes computers extremely versatile, distinguishing them from calculators. The Church–Turing thesis is a mathematical statement of this versatility: any computer with a certain minimum capability is, in principle, capable of performing the same tasks that any other computer can perform. Therefore computers ranging from a personal digital assistant to a supercomputer are all able to perform the same computational tasks, given enough time and storage capacity.

Contents

[hide]

[edit] History of computing

Main article: History of computer hardware

The Jacquard loom was one of the first programmable devices.

The first use of the word “computer” was recorded in 1613, referring to a person who carried out calculations, or computations, and the word continued to be used in that sense until the middle of the 20th century. From the end of the 19th century onwards though, the word began to take on its more familiar meaning, describing a machine that carries out computations.[3]

The history of the modern computer begins with two separate technologies—automated calculation and programmability—but no single device can be identified as the earliest computer, partly because of the inconsistent application of that term. Examples of early mechanical calculating devices include the abacus, the slide rule and arguably the astrolabe and the Antikythera mechanism (which dates from about 150–100 BC). Hero of Alexandria (c. 10–70 AD) built a mechanical theater which performed a play lasting 10 minutes and was operated by a complex system of ropes and drums that might be considered to be a means of deciding which parts of the mechanism performed which actions and when.[4] This is the essence of programmability.

The “castle clock”, an astronomical clock invented by Al-Jazari in 1206, is considered to be the earliest programmable analog computer.[5] It displayed the zodiac, the solar and lunar orbits, a crescent moon-shaped pointer travelling across a gateway causing automatic doors to open every hour,[6][7] and five robotic musicians who played music when struck by levers operated by a camshaft attached to a water wheel. The length of day and night could be re-programmed to compensate for the changing lengths of day and night throughout the year.[5]

The end of the Middle Ages saw a re-invigoration of European mathematics and engineering. Wilhelm Schickard‘s 1623 device was the first of a number of mechanical calculators constructed by European engineers, but none fit the modern definition of a computer, because they could not be programmed.

In 1801, Joseph Marie Jacquard made an improvement to the textile loom by introducing a series of punched paper cards as a template which allowed his loom to weave intricate patterns automatically. The resulting Jacquard loom was an important step in the development of computers because the use of punched cards to define woven patterns can be viewed as an early, albeit limited, form of programmability.

It was the fusion of automatic calculation with programmability that produced the first recognizable computers. In 1837, Charles Babbage was the first to conceptualize and design a fully programmable mechanical computer, his analytical engine.[8] Limited finances and Babbage’s inability to resist tinkering with the design meant that the device was never completed.

In the late 1880s Herman Hollerith invented the recording of data on a machine readable medium. Prior uses of machine readable media, above, had been for control, not data. “After some initial trials with paper tape, he settled on punched cards …”[9] To process these punched cards he invented the tabulator, and the key punch machines. These three inventions were the foundation of the modern information processing industry. Large-scale automated data processing of punched cards was performed for the 1890 United States Census by Hollerith’s company, which later became the core of IBM. By the end of the 19th century a number of technologies that would later prove useful in the realization of practical computers had begun to appear: the punched card, Boolean algebra, the vacuum tube (thermionic valve) and the teleprinter.

During the first half of the 20th century, many scientific computing needs were met by increasingly sophisticated analog computers, which used a direct mechanical or electrical model of the problem as a basis for computation. However, these were not programmable and generally lacked the versatility and accuracy of modern digital computers.

Alan Turing is widely regarded to be the father of modern computer science. In 1936 Turing provided an influential formalisation of the concept of the algorithm and computation with the Turing machine. Of his role in the modern computer, Time Magazine in naming Turing one of the 100 most influential people of the 20th century, states: “The fact remains that everyone who taps at a keyboard, opening a spreadsheet or a word-processing program, is working on an incarnation of a Turing machine.” [10]

George Stibitz is internationally recognized as a father of the modern digital computer. While working at Bell Labs in November of 1937, Stibitz invented and built a relay-based calculator he dubbed the “Model K” (for “kitchen table”, on which he had assembled it), which was the first to use binary circuits to perform an arithmetic operation. Later models added greater sophistication including complex arithmetic and programmability.[11]

Defining characteristics of some early digital computers of the 1940s (In the history of computing hardware)
Name First operational Numeral system Computing mechanism Programming Turing complete
Zuse Z3 (Germany) May 1941 Binary Electro-mechanical Program-controlled by punched film stock (but no conditional branch) Yes (1998)
Atanasoff–Berry Computer (US) 1942 Binary Electronic Not programmable—single purpose No
Colossus Mark 1 (UK) February 1944 Binary Electronic Program-controlled by patch cables and switches No
Harvard Mark I – IBM ASCC (US) May 1944 Decimal Electro-mechanical Program-controlled by 24-channel punched paper tape (but no conditional branch) No
Colossus Mark 2 (UK) June 1944 Binary Electronic Program-controlled by patch cables and switches No
ENIAC (US) July 1946 Decimal Electronic Program-controlled by patch cables and switches Yes
Manchester Small-Scale Experimental Machine (UK) June 1948 Binary Electronic Stored-program in Williams cathode ray tube memory Yes
Modified ENIAC (US) September 1948 Decimal Electronic Program-controlled by patch cables and switches plus a primitive read-only stored programming mechanism using the Function Tables as program ROM Yes
EDSAC (UK) May 1949 Binary Electronic Stored-program in mercury delay line memory Yes
Manchester Mark 1 (UK) October 1949 Binary Electronic Stored-program in Williams cathode ray tube memory and magnetic drum memory Yes
CSIRAC (Australia) November 1949 Binary Electronic Stored-program in mercury delay line memory Yes

A succession of steadily more powerful and flexible computing devices were constructed in the 1930s and 1940s, gradually adding the key features that are seen in modern computers. The use of digital electronics (largely invented by Claude Shannon in 1937) and more flexible programmability were vitally important steps, but defining one point along this road as “the first digital electronic computer” is difficult (Shannon 1940). Notable achievements include:

EDSAC was one of the first computers to implement the stored program (von Neumann) architecture.

  • Konrad Zuse‘s electromechanical “Z machines”. The Z3 (1941) was the first working machine featuring binary arithmetic, including floating point arithmetic and a measure of programmability. In 1998 the Z3 was proved to be Turing complete, therefore being the world’s first operational computer.
  • The non-programmable Atanasoff–Berry Computer (1941) which used vacuum tube based computation, binary numbers, and regenerative capacitor memory. The use of regenerative memory allowed it to be much more compact then its peers (being approximately the size of a large desk or workbench), since intermediate results could be stored and then fed back into the same set of computation elements.
  • The secret British Colossus computers (1943),[12] which had limited programmability but demonstrated that a device using thousands of tubes could be reasonably reliable and electronically reprogrammable. It was used for breaking German wartime codes.
  • The Harvard Mark I (1944), a large-scale electromechanical computer with limited programmability.
  • The U.S. Army’s Ballistics Research Laboratory ENIAC (1946), which used decimal arithmetic and is sometimes called the first general purpose electronic computer (since Konrad Zuse‘s Z3 of 1941 used electromagnets instead of electronics). Initially, however, ENIAC had an inflexible architecture which essentially required rewiring to change its programming.

Several developers of ENIAC, recognizing its flaws, came up with a far more flexible and elegant design, which came to be known as the “stored program architecture” or von Neumann architecture. This design was first formally described by John von Neumann in the paper First Draft of a Report on the EDVAC, distributed in 1945. A number of projects to develop computers based on the stored-program architecture commenced around this time, the first of these being completed in Great Britain. The first to be demonstrated working was the Manchester Small-Scale Experimental Machine (SSEM or “Baby”), while the EDSAC, completed a year after SSEM, was the first practical implementation of the stored program design. Shortly thereafter, the machine originally described by von Neumann’s paper—EDVAC—was completed but did not see full-time use for an additional two years.

Nearly all modern computers implement some form of the stored-program architecture, making it the single trait by which the word “computer” is now defined. While the technologies used in computers have changed dramatically since the first electronic, general-purpose computers of the 1940s, most still use the von Neumann architecture.

Microprocessors are miniaturized devices that often implement stored program CPUs.

Computers using vacuum tubes as their electronic elements were in use throughout the 1950s, but by the 1960s had been largely replaced by transistor-based machines, which were smaller, faster, cheaper to produce, required less power, and were more reliable. The first transistorised computer was demonstrated at the University of Manchester in 1953.[13] In the 1970s, integrated circuit technology and the subsequent creation of microprocessors, such as the Intel 4004, further decreased size and cost and further increased speed and reliability of computers. By the late 1970s, many products such as video recorders contained dedicated computers called microcontrollers, and they started to appear as a replacement to mechanical controls in domestic appliances such as washing machines. The 1980s witnessed home computers and the now ubiquitous personal computer. With the evolution of the Internet, personal computers are becoming as common as the television and the telephone in the household.

Modern smartphones are fully-programmable computers in their own right, and as of 2009 may well be the most common form of such computers in existence.

[edit] Stored program architecture

The defining feature of modern computers which distinguishes them from all other machines is that they can be programmed. That is to say that a list of instructions (the program) can be given to the computer and it will store them and carry them out at some time in the future.

In most cases, computer instructions are simple: add one number to another, move some data from one location to another, send a message to some external device, etc. These instructions are read from the computer’s memory and are generally carried out (executed) in the order they were given. However, there are usually specialized instructions to tell the computer to jump ahead or backwards to some other place in the program and to carry on executing from there. These are called “jump” instructions (or branches). Furthermore, jump instructions may be made to happen conditionally so that different sequences of instructions may be used depending on the result of some previous calculation or some external event. Many computers directly support subroutines by providing a type of jump that “remembers” the location it jumped from and another instruction to return to the instruction following that jump instruction.

Program execution might be likened to reading a book. While a person will normally read each word and line in sequence, they may at times jump back to an earlier place in the text or skip sections that are not of interest. Similarly, a computer may sometimes go back and repeat the instructions in some section of the program over and over again until some internal condition is met. This is called the flow of control within the program and it is what allows the computer to perform tasks repeatedly without human intervention.

Comparatively, a person using a pocket calculator can perform a basic arithmetic operation such as adding two numbers with just a few button presses. But to add together all of the numbers from 1 to 1,000 would take thousands of button presses and a lot of time—with a near certainty of making a mistake. On the other hand, a computer may be programmed to do this with just a few simple instructions. For example:

mov #0,sum ; set sum to 0
mov #1,num ; set num to 1
loop: add num,sum ; add num to sum
add #1,num ; add 1 to num
cmp num,#1000 ; compare num to 1000
ble loop ; if num <= 1000, go back to 'loop'
halt ; end of program. stop running

Once told to run this program, the computer will perform the repetitive addition task without further human intervention. It will almost never make a mistake and a modern PC can complete the task in about a millionth of a second.[14]

However, computers cannot “think” for themselves in the sense that they only solve problems in exactly the way they are programmed to. An intelligent human faced with the above addition task might soon realize that instead of actually adding up all the numbers one can simply use the equation

1+2+3+...+n = {{n(n+1)} \over 2}

and arrive at the correct answer (500,500) with little work.[15] In other words, a computer programmed to add up the numbers one by one as in the example above would do exactly that without regard to efficiency or alternative solutions.

[edit] Programs

A 1970s punched card containing one line from a FORTRAN program. The card reads: “Z(1) = Y + W(1)” and is labelled “PROJ039” for identification purposes.

In practical terms, a computer program may run from just a few instructions to many millions of instructions, as in a program for a word processor or a web browser. A typical modern computer can execute billions of instructions per second (gigahertz or GHz) and rarely make a mistake over many years of operation. Large computer programs consisting of several million instructions may take teams of programmers years to write, and due to the complexity of the task almost certainly contain errors.

Errors in computer programs are called “bugs“. Bugs may be benign and not affect the usefulness of the program, or have only subtle effects. But in some cases they may cause the program to “hang“—become unresponsive to input such as mouse clicks or keystrokes, or to completely fail or “crash“. Otherwise benign bugs may sometimes may be harnessed for malicious intent by an unscrupulous user writing an “exploit“—code designed to take advantage of a bug and disrupt a program’s proper execution. Bugs are usually not the fault of the computer. Since computers merely execute the instructions they are given, bugs are nearly always the result of programmer error or an oversight made in the program’s design.[16]

In most computers, individual instructions are stored as machine code with each instruction being given a unique number (its operation code or opcode for short). The command to add two numbers together would have one opcode, the command to multiply them would have a different opcode and so on. The simplest computers are able to perform any of a handful of different instructions; the more complex computers have several hundred to choose from—each with a unique numerical code. Since the computer’s memory is able to store numbers, it can also store the instruction codes. This leads to the important fact that entire programs (which are just lists of instructions) can be represented as lists of numbers and can themselves be manipulated inside the computer just as if they were numeric data. The fundamental concept of storing programs in the computer’s memory alongside the data they operate on is the crux of the von Neumann, or stored program, architecture. In some cases, a computer might store some or all of its program in memory that is kept separate from the data it operates on. This is called the Harvard architecture after the Harvard Mark I computer. Modern von Neumann computers display some traits of the Harvard architecture in their designs, such as in CPU caches.

While it is possible to write computer programs as long lists of numbers (machine language) and this technique was used with many early computers,[17] it is extremely tedious to do so in practice, especially for complicated programs. Instead, each basic instruction can be given a short name that is indicative of its function and easy to remember—a mnemonic such as ADD, SUB, MULT or JUMP. These mnemonics are collectively known as a computer’s assembly language. Converting programs written in assembly language into something the computer can actually understand (machine language) is usually done by a computer program called an assembler. Machine languages and the assembly languages that represent them (collectively termed low-level programming languages) tend to be unique to a particular type of computer. For instance, an ARM architecture computer (such as may be found in a PDA or a hand-held videogame) cannot understand the machine language of an Intel Pentium or the AMD Athlon 64 computer that might be in a PC.[18]

Though considerably easier than in machine language, writing long programs in assembly language is often difficult and error prone. Therefore, most complicated programs are written in more abstract high-level programming languages that are able to express the needs of the computer programmer more conveniently (and thereby help reduce programmer error). High level languages are usually “compiled” into machine language (or sometimes into assembly language and then into machine language) using another computer program called a compiler.[19] Since high level languages are more abstract than assembly language, it is possible to use different compilers to translate the same high level language program into the machine language of many different types of computer. This is part of the means by which software like video games may be made available for different computer architectures such as personal computers and various video game consoles.

The task of developing large software systems presents a significant intellectual challenge. Producing software with an acceptably high reliability within a predictable schedule and budget has historically been difficult; the academic and professional discipline of software engineering concentrates specifically on this problem.

[edit] Example

A traffic light showing red

Suppose a computer is being employed to drive a traffic signal at an intersection between two streets. The computer has the following three basic instructions.

  1. ON(Streetname, Color) Turns the light on Streetname with a specified Color on.
  2. OFF(Streetname, Color) Turns the light on Streetname with a specified Color off.
  3. WAIT(Seconds) Waits a specifed number of seconds.
  4. START Starts the program
  5. REPEAT Tells the computer to repeat a specified part of the program in a loop.

Comments are marked with a // on the left margin. Assume the streetnames are Broadway and Main.

START

//Let Broadway traffic go
OFF(Broadway, Red)
ON(Broadway, Green)
WAIT(60 seconds)

//Stop Broadway traffic
OFF(Broadway, Green)
ON(Broadway, Yellow)
WAIT(3 seconds)
OFF(Broadway, Yellow)
ON(Broadway, Red)

//Let Main traffic go
OFF(Main, Red)
ON(Main, Green)
WAIT(60 seconds)

//Stop Main traffic
OFF(Main, Green)
ON(Main, Yellow)
WAIT(3 seconds)
OFF(Main, Yellow)
ON(Main, Red)

//Tell computer to continuously repeat the program.
REPEAT ALL

With this set of instructions, the computer would cycle the light continually through red, green, yellow and back to red again on both streets.

However, suppose there is a simple on/off switch connected to the computer that is intended to be used to make the light flash red while some maintenance operation is being performed. The program might then instruct the computer to:

START

IF Switch == OFF then: //Normal traffic signal operation
{
//Let Broadway traffic go
OFF(Broadway, Red)
ON(Broadway, Green)
WAIT(60 seconds)

//Stop Broadway traffic
OFF(Broadway, Green)
ON(Broadway, Yellow)
WAIT(3 seconds)
OFF(Broadway, Yellow)
ON(Broadway, Red)

//Let Main traffic go
OFF(Main, Red)
ON(Main, Green)
WAIT(60 seconds)

//Stop Main traffic
OFF(Main, Green)
ON(Main, Yellow)
WAIT(3 seconds)
OFF(Main, Yellow)
ON(Main, Red)

//Tell the computer to repeat this section continuously.
REPEAT THIS SECTION
}

IF Switch == ON THEN: //Maintenance Mode
{
//Turn the red lights on and wait 1 second.
ON(Broadway, Red)
ON(Main, Red)
WAIT(1 second)

//Turn the red lights off and wait 1 second.
OFF(Broadway, Red)
OFF(Main, Red)
WAIT(1 second)

//Tell the comptuer to repeat the statements in this section.
REPEAT THIS SECTION
}

In this manner, the traffic signal will run a flash-red program when the switch is on, and will run the normal program when the switch is off. Both of these program examples show the basic layout of a computer program in a simple, familiar context of a traffic signal. Any experienced programmer can spot many software bugs in the program, for instance, not making sure that the green light is off when the switch is set to flash red. However, to remove all possible bugs would make this program much longer and more complicated, and would be confusing to nontechnical readers: the aim of this example is a simple demonstration of how computer instructions are laid out.

[edit] How computers work

A general purpose computer has four main components: the arithmetic and logic unit (ALU), the control unit, the memory, and the input and output devices (collectively termed I/O). These parts are interconnected by busses, often made of groups of wires.

The control unit, ALU, registers, and basic I/O (and often other hardware closely linked with these) are collectively known as a central processing unit (CPU). Early CPUs were composed of many separate components but since the mid-1970s CPUs have typically been constructed on a single integrated circuit called a microprocessor.

[edit] Control unit

Main articles: CPU design and Control unit

The control unit (often called a control system or central controller) manages the computer’s various components; it reads and interprets (decodes) the program instructions, transforming them into a series of control signals which activate other parts of the computer.[20] Control systems in advanced computers may change the order of some instructions so as to improve performance.

A key component common to all CPUs is the program counter, a special memory cell (a register) that keeps track of which location in memory the next instruction is to be read from.[21]

Diagram showing how a particular MIPS architecture instruction would be decoded by the control system.

The control system’s function is as follows—note that this is a simplified description, and some of these steps may be performed concurrently or in a different order depending on the type of CPU:

  1. Read the code for the next instruction from the cell indicated by the program counter.
  2. Decode the numerical code for the instruction into a set of commands or signals for each of the other systems.
  3. Increment the program counter so it points to the next instruction.
  4. Read whatever data the instruction requires from cells in memory (or perhaps from an input device). The location of this required data is typically stored within the instruction code.
  5. Provide the necessary data to an ALU or register.
  6. If the instruction requires an ALU or specialized hardware to complete, instruct the hardware to perform the requested operation.
  7. Write the result from the ALU back to a memory location or to a register or perhaps an output device.
  8. Jump back to step (1).

Since the program counter is (conceptually) just another set of memory cells, it can be changed by calculations done in the ALU. Adding 100 to the program counter would cause the next instruction to be read from a place 100 locations further down the program. Instructions that modify the program counter are often known as “jumps” and allow for loops (instructions that are repeated by the computer) and often conditional instruction execution (both examples of control flow).

It is noticeable that the sequence of operations that the control unit goes through to process an instruction is in itself like a short computer program—and indeed, in some more complex CPU designs, there is another yet smaller computer called a microsequencer that runs a microcode program that causes all of these events to happen.

[edit] Arithmetic/logic unit (ALU)

Main article: Arithmetic logic unit

The ALU is capable of performing two classes of operations: arithmetic and logic.[22]

The set of arithmetic operations that a particular ALU supports may be limited to adding and subtracting or might include multiplying or dividing, trigonometry functions (sine, cosine, etc) and square roots. Some can only operate on whole numbers (integers) whilst others use floating point to represent real numbers—albeit with limited precision. However, any computer that is capable of performing just the simplest operations can be programmed to break down the more complex operations into simple steps that it can perform. Therefore, any computer can be programmed to perform any arithmetic operation—although it will take more time to do so if its ALU does not directly support the operation. An ALU may also compare numbers and return boolean truth values (true or false) depending on whether one is equal to, greater than or less than the other (“is 64 greater than 65?”).

Logic operations involve Boolean logic: AND, OR, XOR and NOT. These can be useful both for creating complicated conditional statements and processing boolean logic.

Superscalar computers may contain multiple ALUs so that they can process several instructions at the same time.[23] Graphics processors and computers with SIMD and MIMD features often provide ALUs that can perform arithmetic on vectors and matrices.

[edit] Memory

Main article: Computer storage

Magnetic core memory was the computer memory of choice throughout the 1960s, until it was replaced by semiconductor memory.

A computer’s memory can be viewed as a list of cells into which numbers can be placed or read. Each cell has a numbered “address” and can store a single number. The computer can be instructed to “put the number 123 into the cell numbered 1357” or to “add the number that is in cell 1357 to the number that is in cell 2468 and put the answer into cell 1595”. The information stored in memory may represent practically anything. Letters, numbers, even computer instructions can be placed into memory with equal ease. Since the CPU does not differentiate between different types of information, it is the software’s responsibility to give significance to what the memory sees as nothing but a series of numbers.

In almost all modern computers, each memory cell is set up to store binary numbers in groups of eight bits (called a byte). Each byte is able to represent 256 different numbers (2^8 = 256); either from 0 to 255 or -128 to +127. To store larger numbers, several consecutive bytes may be used (typically, two, four or eight). When negative numbers are required, they are usually stored in two’s complement notation. Other arrangements are possible, but are usually not seen outside of specialized applications or historical contexts. A computer can store any kind of information in memory if it can be represented numerically. Modern computers have billions or even trillions of bytes of memory.

The CPU contains a special set of memory cells called registers that can be read and written to much more rapidly than the main memory area. There are typically between two and one hundred registers depending on the type of CPU. Registers are used for the most frequently needed data items to avoid having to access main memory every time data is needed. As data is constantly being worked on, reducing the need to access main memory (which is often slow compared to the ALU and control units) greatly increases the computer’s speed.

Computer main memory comes in two principal varieties: random access memory or RAM and read-only memory or ROM. RAM can be read and written to anytime the CPU commands it, but ROM is pre-loaded with data and software that never changes, so the CPU can only read from it. ROM is typically used to store the computer’s initial start-up instructions. In general, the contents of RAM are erased when the power to the computer is turned off, but ROM retains its data indefinitely. In a PC, the ROM contains a specialized program called the BIOS that orchestrates loading the computer’s operating system from the hard disk drive into RAM whenever the computer is turned on or reset. In embedded computers, which frequently do not have disk drives, all of the required software may be stored in ROM. Software stored in ROM is often called firmware, because it is notionally more like hardware than software. Flash memory blurs the distinction between ROM and RAM, as it retains its data when turned off but is also rewritable. It is typically much slower than conventional ROM and RAM however, so its use is restricted to applications where high speed is unnecessary.[24]

In more sophisticated computers there may be one or more RAM cache memories which are slower than registers but faster than main memory. Generally computers with this sort of cache are designed to move frequently needed data into the cache automatically, often without the need for any intervention on the programmer’s part.

[edit] Input/output (I/O)

Main article: Input/output

Hard disks are common I/O devices used with computers.

I/O is the means by which a computer exchanges information with the outside world.[25] Devices that provide input or output to the computer are called peripherals.[26] On a typical personal computer, peripherals include input devices like the keyboard and mouse, and output devices such as the display and printer. Hard disk drives, floppy disk drives and optical disc drives serve as both input and output devices. Computer networking is another form of I/O.

Often, I/O devices are complex computers in their own right with their own CPU and memory. A graphics processing unit might contain fifty or more tiny computers that perform the calculations necessary to display 3D graphics[citation needed]. Modern desktop computers contain many smaller computers that assist the main CPU in performing I/O.

[edit] Multitasking

Main article: Computer multitasking

While a computer may be viewed as running one gigantic program stored in its main memory, in some systems it is necessary to give the appearance of running several programs simultaneously. This is achieved by multitasking i.e. having the computer switch rapidly between running each program in turn.[27]

One means by which this is done is with a special signal called an interrupt which can periodically cause the computer to stop executing instructions where it was and do something else instead. By remembering where it was executing prior to the interrupt, the computer can return to that task later. If several programs are running “at the same time”, then the interrupt generator might be causing several hundred interrupts per second, causing a program switch each time. Since modern computers typically execute instructions several orders of magnitude faster than human perception, it may appear that many programs are running at the same time even though only one is ever executing in any given instant. This method of multitasking is sometimes termed “time-sharing” since each program is allocated a “slice” of time in turn.[28]

Before the era of cheap computers, the principle use for multitasking was to allow many people to share the same computer.

Seemingly, multitasking would cause a computer that is switching between several programs to run more slowly — in direct proportion to the number of programs it is running. However, most programs spend much of their time waiting for slow input/output devices to complete their tasks. If a program is waiting for the user to click on the mouse or press a key on the keyboard, then it will not take a “time slice” until the event it is waiting for has occurred. This frees up time for other programs to execute so that many programs may be run at the same time without unacceptable speed loss.

[edit] Multiprocessing

Main article: Multiprocessing

Cray designed many supercomputers that used multiprocessing heavily.

Some computers are designed to distribute their work across several CPUs in a multiprocessing configuration, a technique once employed only in large and powerful machines such as supercomputers, mainframe computers and servers. Multiprocessor and multi-core (multiple CPUs on a single integrated circuit) personal and laptop computers are now widely available, and are being increasingly used in lower-end markets as a result.

Supercomputers in particular often have highly unique architectures that differ significantly from the basic stored-program architecture and from general purpose computers.[29] They often feature thousands of CPUs, customized high-speed interconnects, and specialized computing hardware. Such designs tend to be useful only for specialized tasks due to the large scale of program organization required to successfully utilize most of the available resources at once. Supercomputers usually see usage in large-scale simulation, graphics rendering, and cryptography applications, as well as with other so-called “embarrassingly parallel” tasks.

[edit] Networking and the Internet

Main articles: Computer networking and Internet

Visualization of a portion of the routes on the Internet.

Computers have been used to coordinate information between multiple locations since the 1950s. The U.S. military’s SAGE system was the first large-scale example of such a system, which led to a number of special-purpose commercial systems like Sabre.[30]

In the 1970s, computer engineers at research institutions throughout the United States began to link their computers together using telecommunications technology. This effort was funded by ARPA (now DARPA), and the computer network that it produced was called the ARPANET.[31] The technologies that made the Arpanet possible spread and evolved.

In time, the network spread beyond academic and military institutions and became known as the Internet. The emergence of networking involved a redefinition of the nature and boundaries of the computer. Computer operating systems and applications were modified to include the ability to define and access the resources of other computers on the network, such as peripheral devices, stored information, and the like, as extensions of the resources of an individual computer. Initially these facilities were available primarily to people working in high-tech environments, but in the 1990s the spread of applications like e-mail and the World Wide Web, combined with the development of cheap, fast networking technologies like Ethernet and ADSL saw computer networking become almost ubiquitous. In fact, the number of computers that are networked is growing phenomenally. A very large proportion of personal computers regularly connect to the Internet to communicate and receive information. “Wireless” networking, often utilizing mobile phone networks, has meant networking is becoming increasingly ubiquitous even in mobile computing environments.

[edit] Further topics

[edit] Hardware

Main article: Computer hardware

The term hardware covers all of those parts of a computer that are tangible objects. Circuits, displays, power supplies, cables, keyboards, printers and mice are all hardware.

History of computing hardware
First Generation (Mechanical/Electromechanical) Calculators Antikythera mechanism, Difference Engine, Norden bombsight
Programmable Devices Jacquard loom, Analytical Engine, Harvard Mark I, Z3
Second Generation (Vacuum Tubes) Calculators Atanasoff–Berry Computer, IBM 604, UNIVAC 60, UNIVAC 120
Programmable Devices Colossus, ENIAC, Manchester Small-Scale Experimental Machine, EDSAC, Manchester Mark 1, Ferranti Pegasus, Ferranti Mercury, CSIRAC, EDVAC, UNIVAC I, IBM 701, IBM 702, IBM 650, Z22
Third Generation (Discrete transistors and SSI, MSI, LSI Integrated circuits) Mainframes IBM 7090, IBM 7080, System/360, BUNCH
Minicomputer PDP-8, PDP-11, System/32, System/36
Fourth Generation (VLSI integrated circuits) Minicomputer VAX, IBM System i
4-bit microcomputer Intel 4004, Intel 4040
8-bit microcomputer Intel 8008, Intel 8080, Motorola 6800, Motorola 6809, MOS Technology 6502, Zilog Z80
16-bit microcomputer Intel 8088, Zilog Z8000, WDC 65816/65802
32-bit microcomputer Intel 80386, Pentium, Motorola 68000, ARM architecture
64-bit microcomputer[32] Alpha, MIPS, PA-RISC, PowerPC, SPARC, x86-64
Embedded computer Intel 8048, Intel 8051
Personal computer Desktop computer, Home computer, Laptop computer, Personal digital assistant (PDA), Portable computer, Tablet computer, Wearable computer
Theoretical/experimental Quantum computer, Chemical computer, DNA computing, Optical computer, Spintronics based computer
Other Hardware Topics
Peripheral device (Input/output) Input Mouse, Keyboard, Joystick, Image scanner
Output Monitor, Printer
Both Floppy disk drive, Hard disk, Optical disc drive, Teleprinter
Computer busses Short range RS-232, SCSI, PCI, USB
Long range (Computer networking) Ethernet, ATM, FDDI

[edit] Software

Main article: Computer software

Software refers to parts of the computer which do not have a material form, such as programs, data, protocols, etc. When software is stored in hardware that cannot easily be modified (such as BIOS ROM in an IBM PC compatible), it is sometimes called “firmware” to indicate that it falls into an uncertain area somewhere between hardware and software.

Computer software
Operating system Unix and BSD UNIX System V, AIX, HP-UX, Solaris (SunOS), IRIX, List of BSD operating systems
GNU/Linux List of Linux distributions, Comparison of Linux distributions
Microsoft Windows Windows 95, Windows 98, Windows NT, Windows 2000, Windows XP, Windows Vista, Windows CE
DOS 86-DOS (QDOS), PC-DOS, MS-DOS, FreeDOS
Mac OS Mac OS classic, Mac OS X
Embedded and real-time List of embedded operating systems
Experimental Amoeba, Oberon/Bluebottle, Plan 9 from Bell Labs
Library Multimedia DirectX, OpenGL, OpenAL
Programming library C standard library, Standard template library
Data Protocol TCP/IP, Kermit, FTP, HTTP, SMTP
File format HTML, XML, JPEG, MPEG, PNG
User interface Graphical user interface (WIMP) Microsoft Windows, GNOME, KDE, QNX Photon, CDE, GEM
Text-based user interface Command-line interface, Text user interface
Application Office suite Word processing, Desktop publishing, Presentation program, Database management system, Scheduling & Time management, Spreadsheet, Accounting software
Internet Access Browser, E-mail client, Web server, Mail transfer agent, Instant messaging
Design and manufacturing Computer-aided design, Computer-aided manufacturing, Plant management, Robotic manufacturing, Supply chain management
Graphics Raster graphics editor, Vector graphics editor, 3D modeler, Animation editor, 3D computer graphics, Video editing, Image processing
Audio Digital audio editor, Audio playback, Mixing, Audio synthesis, Computer music
Software Engineering Compiler, Assembler, Interpreter, Debugger, Text Editor, Integrated development environment, Performance analysis, Revision control, Software configuration management
Educational Edutainment, Educational game, Serious game, Flight simulator
Games Strategy, Arcade, Puzzle, Simulation, First-person shooter, Platform, Massively multiplayer, Interactive fiction
Misc Artificial intelligence, Antivirus software, Malware scanner, Installer/Package management systems, File manager

[edit] Programming languages

Programming languages provide various ways of specifying programs for computers to run. Unlike natural languages, programming languages are designed to permit no ambiguity and to be concise. They are purely written languages and are often difficult to read aloud. They are generally either translated into machine language by a compiler or an assembler before being run, or translated directly at run time by an interpreter. Sometimes programs are executed by a hybrid method of the two techniques. There are thousands of different programming languages—some intended to be general purpose, others useful only for highly specialized applications.

Programming Languages
Lists of programming languages Timeline of programming languages, Categorical list of programming languages, Generational list of programming languages, Alphabetical list of programming languages, Non-English-based programming languages
Commonly used Assembly languages ARM, MIPS, x86
Commonly used High level languages Ada, BASIC, C, C++, C#, COBOL, Fortran, Java, Lisp, Pascal, Object Pascal
Commonly used Scripting languages Bourne script, JavaScript, Python, Ruby, PHP, Perl

[edit] Professions and organizations

As the use of computers has spread throughout society, there are an increasing number of careers involving computers.

Computer-related professions
Hardware-related Electrical engineering, Electronics engineering, Computer engineering, Telecommunications engineering, Optical engineering, Nanoscale engineering
Software-related Computer science, Desktop publishing, Human-computer interaction, Information technology, Scientific computing, Software engineering, Video game industry, Web design

The need for computers to work well together and to be able to exchange information has spawned the need for many standards organizations, clubs and societies of both a formal and informal nature.

Organizations
Standards groups ANSI, IEC, IEEE, IETF, ISO, W3C
Professional Societies ACM, ACM Special Interest Groups, IET, IFIP
Free/Open source software groups Free Software Foundation, Mozilla Foundation, Apache Software Foundation

[edit] See also

Sister project Look up computer in Wiktionary, the free dictionary.
Sister projectWikiquote has a collection of quotations related to: Computers
Sister projectWikimedia Commons has media related to: Computer
Sister project Wikiversity has learning materials about Introduction to Computers

 

[edit] Notes

  1. ^ In 1946, ENIAC consumed an estimated 174 kW. By comparison, a typical personal computer may use around 400 W; over four hundred times less. (Kempf 1961)
  2. ^ Early computers such as Colossus and ENIAC were able to process between 5 and 100 operations per second. A modern “commodity” microprocessor (as of 2007) can process billions of operations per second, and many of these operations are more complicated and useful than early computer operations.
  3. ^ computer, n., Oxford English Dictionary (2 ed.), Oxford University Press, 1989, http://dictionary.oed.com/, retrieved on 2009-04-10 
  4. ^ “Heron of Alexandria”. http://www.mlahanas.de/Greeks/HeronAlexandria2.htm. Retrieved on 2008-01-15. 
  5. ^ a b Ancient Discoveries, Episode 11: Ancient Robots, History Channel, http://www.youtube.com/watch?v=rxjbaQl0ad8, retrieved on 2008-09-06 
  6. ^ Howard R. Turner (1997), Science in Medieval Islam: An Illustrated Introduction, p. 184, University of Texas Press, ISBN 0-292-78149-0
  7. ^ Donald Routledge Hill, “Mechanical Engineering in the Medieval Near East”, Scientific American, May 1991, pp. 64-9 (cf. Donald Routledge Hill, Mechanical Engineering)
  8. ^ The analytical engine should not be confused with Babbage’s difference engine which was a non-programmable mechanical calculator.
  9. ^ Columbia University Computing History: Herman Hollerith
  10. ^ http://www.time.com/time/time100/scientist/profile/turing.html
  11. ^ “Inventor Profile: George R. Stibitz”. National Inventors Hall of Fame Foundation, Inc.. http://www.invent.org/hall_of_fame/140.html. 
  12. ^ B. Jack Copeland, ed., Colossus: The Secrets of Bletchley Park’s Codebreaking Computers, Oxford University Press, 2006
  13. ^ Lavington 1998, p. 37
  14. ^ This program was written similarly to those for the PDP-11 minicomputer and shows some typical things a computer can do. All the text after the semicolons are comments for the benefit of human readers. These have no significance to the computer and are ignored. (Digital Equipment Corporation 1972)
  15. ^ Attempts are often made to create programs that can overcome this fundamental limitation of computers. Software that mimics learning and adaptation is part of artificial intelligence.
  16. ^ It is not universally true that bugs are solely due to programmer oversight. Computer hardware may fail or may itself have a fundamental problem that produces unexpected results in certain situations. For instance, the Pentium FDIV bug caused some Intel microprocessors in the early 1990s to produce inaccurate results for certain floating point division operations. This was caused by a flaw in the microprocessor design and resulted in a partial recall of the affected devices.
  17. ^ Even some later computers were commonly programmed directly in machine code. Some minicomputers like the DEC PDP-8 could be programmed directly from a panel of switches. However, this method was usually used only as part of the booting process. Most modern computers boot entirely automatically by reading a boot program from some non-volatile memory.
  18. ^ However, there is sometimes some form of machine language compatibility between different computers. An x86-64 compatible microprocessor like the AMD Athlon 64 is able to run most of the same programs that an Intel Core 2 microprocessor can, as well as programs designed for earlier microprocessors like the Intel Pentiums and Intel 80486. This contrasts with very early commercial computers, which were often one-of-a-kind and totally incompatible with other computers.
  19. ^ High level languages are also often interpreted rather than compiled. Interpreted languages are translated into machine code on the fly by another program called an interpreter.
  20. ^ The control unit’s role in interpreting instructions has varied somewhat in the past. Although the control unit is solely responsible for instruction interpretation in most modern computers, this is not always the case. Many computers include some instructions that may only be partially interpreted by the control system and partially interpreted by another device. This is especially the case with specialized computing hardware that may be partially self-contained. For example, EDVAC, one of the earliest stored-program computers, used a central control unit that only interpreted four instructions. All of the arithmetic-related instructions were passed on to its arithmetic unit and further decoded there.
  21. ^ Instructions often occupy more than one memory address, so the program counters usually increases by the number of memory locations required to store one instruction.
  22. ^ David J. Eck (2000). The Most Complex Machine: A Survey of Computers and Computing. A K Peters, Ltd.. p. 54. ISBN 9781568811284. 
  23. ^ Erricos John Kontoghiorghes (2006). Handbook of Parallel Computing and Statistics. CRC Press. p. 45. ISBN 9780824740672. 
  24. ^ Flash memory also may only be rewritten a limited number of times before wearing out, making it less useful for heavy random access usage. (Verma 1988)
  25. ^ Donald Eadie (1968). Introduction to the Basic Computer. Prentice-Hall. p. 12. 
  26. ^ Arpad Barna; Dan I. Porat (1976). Introduction to Microcomputers and the Microprocessors. Wiley. p. 85. ISBN 9780471050513. 
  27. ^ Jerry Peek; Grace Todino, John Strang (2002). Learning the UNIX Operating System: A Concise Guide for the New User. O’Reilly. p. 130. ISBN 9780596002619. 
  28. ^ Gillian M. Davis (2002). Noise Reduction in Speech Applications. CRC Press. p. 111. ISBN 9780849309496. 
  29. ^ However, it is also very common to construct supercomputers out of many pieces of cheap commodity hardware; usually individual computers connected by networks. These so-called computer clusters can often provide supercomputer performance at a much lower cost than customized designs. While custom architectures are still used for most of the most powerful supercomputers, there has been a proliferation of cluster computers in recent years. (TOP500 2006)
  30. ^ Agatha C. Hughes (2000). Systems, Experts, and Computers. MIT Press. p. 161. ISBN 9780262082853. “The experience of SAGE helped make possible the first truly large-scale commercial real-time network: the SABRE computerized airline reservations system…” 
  31. ^ “A Brief History of the Internet”. Internet Society. http://www.isoc.org/internet/history/brief.shtml. Retrieved on 2008-09-20. 
  32. ^ Most major 64-bit instruction set architectures are extensions of earlier designs. All of the architectures listed in this table, except for Alpha, existed in 32-bit forms before their 64-bit incarnations were introduced.

[edit] References

[edit] External links

  

Read Full Post »

Mathematical object

Mathematical object

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In mathematics and its philosophy, a mathematical object is an abstract object arising in mathematics. Commonly encountered mathematical objects include numbers, permutations, partitions, matrices, sets, functions, and relations. Geometry as a branch of mathematics has such objects as points, lines, triangles, circles, spheres, polyhedra, topological spaces and manifolds. Algebra, another branch, has groups, rings, fields, group-theoretic lattices and order-theoretic lattices. Categories are simultaneously homes to mathematical objects and mathematical objects in their own right.

The ontological status of mathematical objects has been apart of a long dispute as the subject of much investigation and debate by philosophers of mathematics. On this debate, see the monograph by Burgess and Rosen (1997).

One view that emerged around the turn of the 20th century with the work of Cantor is that all mathematical objects can be defined as sets. The set {0,1} is a relatively clear-cut example. On the face of it the group Z2 of integers mod 2 is also a set with two elements. However it cannot simply be the set {0,1} because this does not mention the additional structure imputed to Z2 by its operations of addition and negation mod 2: how are we to tell which of 0 or 1 is the additive identity, for example? To organize this group as a set it can first be coded as the quadruple ({0,1},+,−,0), which in turn can be coded using one of several conventions as a set representing that quadruple, which in turn entails encoding the operations + and − and the constant 0 as sets.

This approach to the ontology of mathematics raises a fundamental philosophical question of whether the ontology of mathematics needs to be beholden to either its practice or its pedagogy. Mathematicians do not work with such codings, which are neither canonical nor practical. They do not appear in any algebra texts, and neither students nor instructors in algebra courses have any familiarity with such codings. Hence if ontology is to reflect practice, mathematical objects cannot be reduced to sets in this way.

If however the goal of mathematical ontology is taken to be the internal consistency of mathematics, it is more important that mathematical objects be definable in some uniform way, for example as sets, regardless of actual practice in order to lay bare the essence of its paradoxes. This has been the viewpoint taken by foundations of mathematics, which has traditionally accorded the management of paradox higher priority than the faithful reflection of the details of mathematical practice as a justification for defining mathematical objects to be sets.

Much of the tension created by this foundational identification of mathematical objects with sets can be relieved without unduly compromising the goals of foundations by allowing two kinds of objects into the mathematical universe, sets and relations, without requiring that either be considered merely an instance of the other. These form the basis of model theory as the domain of discourse of predicate logic. In this viewpoint mathematical objects are entities satisfying the axioms of a formal theory expressed in the language of predicate logic.

A variant of this approach replaces relations with operations, the basis of universal algebra. In this variant the axioms often take the form of equations, or implications between equations.

A more abstract variant is category theory, which abstracts sets as objects and the operations thereon as morphisms between those objects. At this level of abstraction mathematical objects reduce to mere vertices of a graph whose edges as the morphisms abstract the ways in which those objects can transform and whose structure is encoded in the composition law for morphisms. Categories may arise as the models of some axiomatic theory and the homomorphisms between them (in which case they are usually concrete, meaning equipped with a faithful forgetful functor to the category Set or more generally to a suitable topos), or they may be constructed from other more primitive categories, or they may be studied as abstract objects in their own right without regard for their provenance.

[edit] References

  • Azzouni, J., 1994. Metaphysical Myths, Mathematical Practice. Cambridge University Press.
  • Burgess, John, and Rosen, Gideon, 1997. A Subject with No Object. Oxford Univ. Press.
  • Davis, Philip and Hersh, Reuben, 1999 [1981]. The Mathematical Experience. Mariner Books: 156-62.
  • Gold, Bonnie, and Simons, Roger A., 2008. Proof and Other Dilemmas: Mathematics and Philosophy. Mathematical Association of America.
  • Hersh, Reuben, 1997. What is Mathematics, Really? Oxford University Press.
  • Sfard, A., 2000, “Symbolizing mathematical reality into being, Or how mathematical discourse and mathematical objects create each other,” in Cobb, P., et al., Symbolizing and communicating in mathematics classrooms: Perspectives on discourse, tools and instructional design. Lawrence Erlbaum.
  • Stewart Shapiro, 2000. Thinking about mathematics: The philosophy of mathematics. Oxford University Press.

[edit] External links

Read Full Post »

Algorithm

Algorithm

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Flowcharts are often used to graphically represent algorithms.

In mathematics, computing, linguistics, and related subjects, an algorithm is a finite sequence of instructions, an explicit, step-by-step procedure for solving a problem, often used for calculation and data processing. It is formally a type of effective method in which a list of well-defined instructions for completing a task, will when given an initial state, proceed through a well-defined series of successive states, eventually terminating in an end-state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as probabilistic algorithms, incorporate randomness.

A partial formalization of the concept began with attempts to solve the Entscheidungsproblem (the “decision problem”) posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define “effective calculability” (Kleene 1943:274) or “effective method” (Rosser 1939:225); those formalizations included the Gödel-Herbrand-Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church‘s lambda calculus of 1936, Emil Post’s “Formulation 1” of 1936, and Alan Turing‘s Turing machines of 1936–7 and 1939.

Contents

[hide]

[edit] Etymology

Al-Khwārizmī, Persian astronomer and mathematician, wrote a treatise in 825 AD, On Calculation with Hindu Numerals. (See algorism). It was translated into Latin in the 12th century as Algoritmi de numero Indorum (al-Daffa 1977), whose title was likely intended to mean “Algoritmi on the numbers of the Indians”, where “Algoritmi” was the translator’s rendition of the author’s name; but people misunderstanding the title treated Algoritmi as a Latin plural and this led to the word “algorithm” (Latin algorismus) coming to mean “calculation method”. The intrusive “th” is most likely due to a false cognate with the Greek ἀριθμός (arithmos) meaning “number”.

[edit] Why algorithms are necessary: an informal definition

For a detailed presentation of the various points of view around the definition of “algorithm” see Algorithm characterizations. For examples of simple addition algorithms specified in the detailed manner described in Algorithm characterizations, see Algorithm examples.

While there is no generally accepted formal definition of “algorithm”, an informal definition could be “a process that performs some sequence of operations.” For some people, a program is only an algorithm if it stops eventually. For others, a program is only an algorithm if it stops before a given number of calculation steps.

A prototypical example of an “algorithm” is Euclid’s algorithm to determine the maximum common divisor of two integers (X and Y) which are greater than one: We follow a series of steps: In step i, we divide X by Y and find the remainder, which we call R1. Then we move to step i + 1, where we divide Y by R1, and find the remainder, which we call R2. If R2=0, we stop and say that R1 is the greatest common divisor of X and Y. If not, we continue, until Rn=0. Then Rn-1 is the max common division of X and Y. This procedure is known to stop always and the number of subtractions needed is always smaller than the larger of the two numbers.

We can derive clues to the issues involved and an informal meaning of the word from the following quotation from Boolos & Jeffrey (1974, 1999) (boldface added):

No human being can write fast enough or long enough or small enough to list all members of an enumerably infinite set by writing out their names, one after another, in some notation. 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. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols (Boolos & Jeffrey 1974, 1999, p. 19)

The words “enumerably infinite” mean “countable using integers perhaps extending to infinity.” Thus Boolos and Jeffrey are saying that an algorithm implies instructions for a process that “creates” output integers from an arbitrary “input” integer or integers that, in theory, can be chosen from 0 to infinity. Thus we might expect an algorithm to be an algebraic equation such as y = m + n — two arbitrary “input variables” m and n that produce an output y. As we see in Algorithm characterizations — the word algorithm implies much more than this, something on the order of (for our addition example):

Precise instructions (in language understood by “the computer”) for a “fast, efficient, good” process that specifies the “moves” of “the computer” (machine or human, equipped with the necessary internally-contained information and capabilities) to find, decode, and then munch arbitrary input integers/symbols m and n, symbols + and = … and (reliably, correctly, “effectively”) produce, in a “reasonable” time, output-integer y at a specified place and in a specified format.

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 small set of axioms and rules. In logic, the time that an algorithm requires to complete cannot be measured, as it is not apparently related with our customary physical dimension. From such uncertainties, that characterize ongoing work, stems the unavailability of a definition of algorithm that suits both concrete (in some sense) and abstract usage of the term.

[edit] Formalization

Algorithms are essential to the way computers process information. Many computer programs contain algorithms that specify the specific instructions a computer should perform (in a specific order) to carry out a specified task, such as calculating employees’ paychecks or printing students’ report cards. Thus, an algorithm can be considered to be any sequence of operations that can be simulated by a Turing-complete system. Authors who assert this thesis include Savage (1987) and Gurevich (2000):

…Turing’s informal argument in favor of his thesis justifies a stronger thesis: every algorithm can be simulated by a Turing machine (Gurevich 2000:1)…according to Savage [1987], an algorithm is a computational process defined by a Turing machine. (Gurevich 2000:3)

Typically, when an algorithm is associated with processing information, data is read from an input source, written to an output device, and/or stored for further processing. Stored data is regarded as part of the internal state of the entity performing the algorithm. In practice, the state is stored in one or more data structures.

For any 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 systematically dealt with, case-by-case; the criteria for each case must be clear (and computable).

Because an algorithm is a precise list of precise steps, the order of computation will always be critical to the functioning of the algorithm. Instructions are usually assumed to be listed explicitly, and are described as starting “from the top” and going “down to the bottom”, an idea that is described more formally by flow of control.

So far, this discussion of the formalization of an algorithm has assumed the premises of imperative programming. This is the most common conception, and it attempts to describe a task in discrete, “mechanical” means. Unique to this conception of formalized algorithms is the assignment operation, setting the value of a variable. It derives from the intuition of “memory” as a scratchpad. There is an example below of such an assignment.

For some alternate conceptions of what constitutes an algorithm see functional programming and logic programming .

[edit] Termination

Some writers restrict the definition of algorithm to procedures that eventually finish. In such a category Kleene places the “decision procedure or decision method or algorithm for the question” (Kleene 1952:136). Others, including Kleene, include procedures that could run forever without stopping; such a procedure has been called a “computational method” (Knuth 1997:5) or “calculation procedure or algorithm” (Kleene 1952:137); however, Kleene notes that such a method must eventually exhibit “some object” (Kleene 1952:137).

Minsky makes the pertinent observation, in regards to determining whether an algorithm will eventually terminate (from a particular starting state):

But if the length of the process is not known in advance, then “trying” it may not be decisive, because if the process does go on forever — then at no time will we ever be sure of the answer (Minsky 1967:105).

As it happens, no other method can do any better, as was shown by Alan Turing with his celebrated result on the undecidability of the so-called halting problem. There is no algorithmic procedure for determining of arbitrary algorithms whether or not they terminate from given starting states. The analysis of algorithms for their likelihood of termination is called termination analysis.

See the examples of (im-)”proper” subtraction at partial function for more about what can happen when an algorithm fails for certain of its input numbers — e.g., (i) non-termination, (ii) production of “junk” (output in the wrong format to be considered a number) or no number(s) at all (halt ends the computation with no output), (iii) wrong number(s), or (iv) a combination of these. Kleene proposed that the production of “junk” or failure to produce a number is solved by having the algorithm detect these instances and produce e.g., an error message (he suggested “0”), or preferably, force the algorithm into an endless loop (Kleene 1952:322). Davis does this to his subtraction algorithm — he fixes his algorithm in a second example so that it is proper subtraction (Davis 1958:12-15). Along with the logical outcomes “true” and “false” Kleene also proposes the use of a third logical symbol “u” — undecided (Kleene 1952:326) — thus an algorithm will always produce something when confronted with a “proposition”. The problem of wrong answers must be solved with an independent “proof” of the algorithm e.g., using induction:

We normally require auxiliary evidence for this (that the algorithm correctly defines a mu recursive function), e.g., in the form of an inductive proof that, for each argument value, the computation terminates with a unique value (Minsky 1967:186).

[edit] Expressing algorithms

Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, and programming languages. Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms. Pseudocode and flowcharts are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements, while remaining independent of a particular implementation language. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but are often used as a way to define or document algorithms.

There is a wide variety of representations possible and one can express a given Turing machine program as a sequence of machine tables (see more at finite state machine and state transition table), as flowcharts (see more at state diagram), or as a form of rudimentary machine code or assembly code called “sets of quadruples” (see more at Turing machine).

Sometimes it is helpful in the description of an algorithm to supplement small “flow charts” (state diagrams) with natural-language and/or arithmetic expressions written inside “block diagrams” to summarize what the “flow charts” are accomplishing.

Representations of algorithms are generally classed into three accepted levels of Turing machine description (Sipser 2006:157):

  • 1 High-level description:
“…prose to describe an algorithm, ignoring the implementation details. At this level we do not need to mention how the machine manages its tape or head”
  • 2 Implementation description:
“…prose used to define the way the Turing machine uses its head and the way that it stores data on its tape. At this level we do not give details of states or transition function”
  • 3 Formal description:
Most detailed, “lowest level”, gives the Turing machine’s “state table”.
For an example of the simple algorithm “Add m+n” described in all three levels see Algorithm examples.

[edit] Implementation

Most algorithms are intended to be implemented as computer programs. However, algorithms are also implemented by other means, such as in a biological neural network (for example, the human brain implementing arithmetic or an insect looking for food), in an electrical circuit, or in a mechanical device.

[edit] Example

An animation of the quicksort algorithm sorting an array of randomized values. The red bars mark the pivot element; at the start of the animation, the element farthest to the right hand side is chosen as the pivot.

One of the simplest algorithms is to find the largest number in an (unsorted) list of numbers. The solution necessarily requires looking at every number in the list, but only once at each. From this follows a simple algorithm, which can be stated in a high-level description English prose, as:

High-level description:

  1. Assume the first item is largest.
  2. Look at each of the remaining items in the list and if it is larger than the largest item so far, make a note of it.
  3. The last noted item is the largest in the list when the process is complete.

(Quasi-)formal description: Written in prose but much closer to the high-level language of a computer program, the following is the more formal coding of the algorithm in pseudocode or pidgin code:

Algorithm LargestNumber
  Input: A non-empty list of numbers L.
  Output: The largest number in the list L.

  largestL0
  for each item in the list L≥1, do
    if the item > largest, then
      largest ← the item
  return largest
  • “←” is a loose shorthand for “changes to”. For instance, “largestitem” means that the value of largest changes to the value of item.
  • return” terminates the algorithm and outputs the value that follows.

For a more complex example of an algorithm, see Euclid’s algorithm for the greatest common divisor, one of the earliest algorithms known.

[edit] Algorithmic analysis

It is frequently important to know how much of a particular resource (such as time or storage) is required for a given algorithm. Methods have been developed for the analysis of algorithms to obtain such quantitative answers; for example, the algorithm above has a time requirement of O(n), using the big O notation with n as the length of the list. At all times the algorithm only needs to remember two values: the largest number found so far, and its current position in the input list. Therefore it is said to have a space requirement of O(1), if the space required to store the input numbers is not counted, or O(n) if it is counted.

Different algorithms may complete the same task with a different set of instructions in less or more time, space, or ‘effort’ than others. For example, a binary search algorithm will usually outperform a brute force sequential search when used for table lookups on sorted lists.

[edit] Abstract versus empirical

The analysis and study of algorithms is a discipline of computer science, and is often practiced abstractly without the use of a specific programming language or implementation. In this sense, algorithm analysis resembles other mathematical disciplines in that it focuses on the underlying properties of the algorithm and not on the specifics of any particular implementation. Usually pseudocode is used for analysis as it is the simplest and most general representation. However, ultimately, most algorithms are usually implemented on particular hardware / software platforms and their algorithmic efficiency is eventually put to the test using real code.

Empirical testing is useful because it may uncover unexpected interactions that affect performance. For instance an algorithm that has no locality of reference may have much poorer performance than predicted because it thrashes the cache.

[edit] Classification

There are various ways to classify algorithms, each with its own merits.

[edit] By implementation

One way to classify algorithms is by implementation means.

  • Recursion or iteration: A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to functional programming. Iterative algorithms use repetitive constructs like loops and sometimes additional data structures like stacks to solve the given problems. Some problems are naturally suited for one implementation or the other. For example, towers of Hanoi is well understood in recursive implementation. Every recursive version has an equivalent (but possibly more or less complex) iterative version, and vice versa.
  • Logical: An algorithm may be viewed as controlled logical deduction. This notion may be expressed as: Algorithm = logic + control (Kowalski 1979). The logic component expresses the axioms that may be used in the computation and the control component determines the way in which deduction is applied to the axioms. This is the basis for the logic programming paradigm. In pure logic programming languages the control component is fixed and algorithms are specified by supplying only the logic component. The appeal of this approach is the elegant semantics: a change in the axioms has a well defined change in the algorithm.
  • Serial or parallel or distributed: Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time. Those computers are sometimes called serial computers. An algorithm designed for such an environment is called a serial algorithm, as opposed to parallel algorithms or distributed algorithms. Parallel algorithms take advantage of computer architectures where several processors can work on a problem at the same time, whereas distributed algorithms utilize multiple machines connected with a network. Parallel or distributed algorithms divide the problem into more symmetrical or asymmetrical subproblems and collect the results back together. The resource consumption in such algorithms is not only processor cycles on each processor but also the communication overhead between the processors. Sorting algorithms can be parallelized efficiently, but their communication overhead is expensive. Iterative algorithms are generally parallelizable. Some problems have no parallel algorithms, and are called inherently serial problems.
  • Deterministic or non-deterministic: Deterministic algorithms solve the problem with exact decision at every step of the algorithm whereas non-deterministic algorithms solve problems via guessing although typical guesses are made more accurate through the use of heuristics.
  • Exact or approximate: While many algorithms reach an exact solution, approximation algorithms seek an approximation that is close to the true solution. Approximation may use either a deterministic or a random strategy. Such algorithms have practical value for many hard problems.

[edit] By design paradigm

Another way of classifying algorithms is by their design methodology or paradigm. There is a certain number of paradigms, each different from the other. Furthermore, each of these categories will include many different types of algorithms. Some commonly found paradigms include:

  • Divide and conquer. A divide and conquer algorithm repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively) until the instances are small enough to solve easily. One such example of divide and conquer is merge sorting. Sorting can be done on each segment of data after dividing data into segments and sorting of entire data can be obtained in the conquer phase by merging the segments. A simpler variant of divide and conquer is called a decrease and conquer algorithm, that solves an identical subproblem and uses the solution of this subproblem to solve the bigger problem. Divide and conquer divides the problem into multiple subproblems and so the conquer stage will be more complex than decrease and conquer algorithms. An example of decrease and conquer algorithm is the binary search algorithm.
  • Dynamic programming. When a problem shows optimal substructure, meaning the optimal solution to a problem can be constructed from optimal solutions to subproblems, and overlapping subproblems, meaning the same subproblems are used to solve many different problem instances, a quicker approach called dynamic programming avoids recomputing solutions that have already been computed. For example, the shortest path to a goal from a vertex in a weighted graph can be found by using the shortest path to the goal from all adjacent vertices. Dynamic programming and memoization go together. The main difference between dynamic programming and divide and conquer is that subproblems are more or less independent in divide and conquer, whereas subproblems overlap in dynamic programming. The difference between dynamic programming and straightforward recursion is in caching or memoization of recursive calls. When subproblems are independent and there is no repetition, memoization does not help; hence dynamic programming is not a solution for all complex problems. By using memoization or maintaining a table of subproblems already solved, dynamic programming reduces the exponential nature of many problems to polynomial complexity.
  • The greedy method. A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the subproblems do not have to be known at each stage; instead a “greedy” choice can be made of what looks best for the moment. The greedy method extends the solution with the best possible decision (not all feasible decisions) at an algorithmic stage based on the current local optimum and the best decision (not all possible decisions) made in a previous stage. It is not exhaustive, and does not give accurate answer to many problems. But when it works, it will be the fastest method. The most popular greedy algorithm is finding the minimal spanning tree as given by Kruskal.
  • Linear programming. When solving a problem using linear programming, specific inequalities involving the inputs are found and then an attempt is made to maximize (or minimize) some linear function of the inputs. Many problems (such as the maximum flow for directed graphs) can be stated in a linear programming way, and then be solved by a ‘generic’ algorithm such as the simplex algorithm. A more complex variant of linear programming is called integer programming, where the solution space is restricted to the integers.
  • Reduction. This technique involves solving a difficult problem by transforming it into a better known problem for which we have (hopefully) asymptotically optimal algorithms. The goal is to find a reducing algorithm whose complexity is not dominated by the resulting reduced algorithm’s. For example, one selection algorithm for finding the median in an unsorted list involves first sorting the list (the expensive portion) and then pulling out the middle element in the sorted list (the cheap portion). This technique is also known as transform and conquer.
  • Search and enumeration. Many problems (such as playing chess) can be modeled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. This category also includes search algorithms, branch and bound enumeration and backtracking.
  • The probabilistic and heuristic paradigm. Algorithms belonging to this class fit the definition of an algorithm more loosely.
  1. Probabilistic algorithms are those that make some choices randomly (or pseudo-randomly); for some problems, it can in fact be proven that the fastest solutions must involve some randomness.
  2. Genetic algorithms attempt to find solutions to problems by mimicking biological evolutionary processes, with a cycle of random mutations yielding successive generations of “solutions”. Thus, they emulate reproduction and “survival of the fittest”. In genetic programming, this approach is extended to algorithms, by regarding the algorithm itself as a “solution” to a problem.
  3. Heuristic algorithms, whose general purpose is not to find an optimal solution, but an approximate solution where the time or resources are limited. They are not practical to find perfect solutions. An example of this would be local search, tabu search, or simulated annealing algorithms, a class of heuristic probabilistic algorithms that vary the solution of a problem by a random amount. The name “simulated annealing” alludes to the metallurgic term meaning the heating and cooling of metal to achieve freedom from defects. The purpose of the random variance is to find close to globally optimal solutions rather than simply locally optimal ones, the idea being that the random element will be decreased as the algorithm settles down to a solution.

[edit] By field of study

Every field of science has its own problems and needs efficient algorithms. Related problems in one field are often studied together. Some example classes are search algorithms, sorting algorithms, merge algorithms, numerical algorithms, graph algorithms, string algorithms, computational geometric algorithms, combinatorial algorithms, machine learning, cryptography, data compression algorithms and parsing techniques.

Fields tend to overlap with each other, and algorithm advances in one field may improve those of other, sometimes completely unrelated, fields. For example, dynamic programming was originally invented for optimization of resource consumption in industry, but is now used in solving a broad range of problems in many fields.

[edit] By complexity

Algorithms can be classified by the amount of time they need to complete compared to their input size. There is a wide variety: some algorithms complete in linear time relative to input size, some do so in an exponential amount of time or even worse, and some never halt. Additionally, some problems may have multiple algorithms of differing complexity, while other problems might have no algorithms or no known efficient algorithms. There are also mappings from some problems to other problems. Owing to this, it was found to be more suitable to classify the problems themselves instead of the algorithms into equivalence classes based on the complexity of the best possible algorithms for them.

[edit] By computing power

Another way to classify algorithms is by computing power. This is typically done by considering some collection (class) of algorithms. A recursive class of algorithms is one that includes algorithms for all Turing computable functions. Looking at classes of algorithms allows for the possibility of restricting the available computational resources (time and memory) used in a computation. A subrecursive class of algorithms is one in which not all Turing computable functions can be obtained. For example, the algorithms that run in polynomial time suffice for many important types of computation but do not exhaust all Turing computable functions. The class of algorithms implemented by primitive recursive functions is another subrecursive class.

Burgin (2005, p. 24) uses a generalized definition of algorithms that relaxes the common requirement that the output of the algorithm that computes a function must be determined after a finite number of steps. He defines a super-recursive class of algorithms as “a class of algorithms in which it is possible to compute functions not computable by any Turing machine” (Burgin 2005, p. 107). This is closely related to the study of methods of hypercomputation.

[edit] Legal issues

See also: Software patents for a general overview of the patentability of software, including computer-implemented algorithms.

Algorithms, by themselves, are not usually patentable. In the United States, a claim consisting solely of simple manipulations of abstract concepts, numbers, or signals does not constitute “processes” (USPTO 2006), and hence algorithms are not patentable (as in Gottschalk v. Benson). However, practical applications of algorithms are sometimes patentable. For example, in Diamond v. Diehr, the application of a simple feedback algorithm to aid in the curing of synthetic rubber was deemed patentable. The patenting of software is highly controversial, and there are highly criticized patents involving algorithms, especially data compression algorithms, such as UnisysLZW patent.

Additionally, some cryptographic algorithms have export restrictions (see export of cryptography).

[edit] History: Development of the notion of “algorithm”

[edit] Origin of the word

The word algorithm comes from the name of the 9th century Persian mathematician Abu Abdullah Muhammad ibn Musa al-Khwarizmi whose works introduced Indian numerals and algebraic concepts. He worked in Baghdad at the time when it was the centre of scientific studies and trade. The word algorism originally referred only to the rules of performing arithmetic using Arabic numerals but evolved via European Latin translation of al-Khwarizmi’s name into algorithm by the 18th century. The word evolved to include all definite procedures for solving problems or performing tasks.

[edit] Discrete and distinguishable symbols

Tally-marks: To keep track of their flocks, their sacks of grain and their money the ancients used tallying: accumulating stones or marks scratched on sticks, or making discrete symbols in clay. Through the Babylonian and Egyptian use of marks and symbols, eventually Roman numerals and the abacus evolved (Dilson, p.16–41). Tally marks appear prominently in unary numeral system arithmetic used in Turing machine and Post-Turing machine computations.

[edit] Manipulation of symbols as “place holders” for numbers: algebra

The work of the ancient Greek geometers, Persian mathematician Al-Khwarizmi (often considered the “father of algebra” and from whose name the terms “algorism” and “algorithm” are derived), and Western European mathematicians culminated in Leibniz’s notion of the calculus ratiocinator (ca 1680):

“A good century and a half ahead of his time, Leibniz proposed an algebra of logic, an algebra that would specify the rules for manipulating logical concepts in the manner that ordinary algebra specifies the rules for manipulating numbers” (Davis 2000:1)

[edit] Mechanical contrivances with discrete states

The clock: Bolter credits the invention of the weight-driven clock as “The key invention [of Europe in the Middle Ages]”, in particular the verge escapement (Bolter 1984:24) that provides us with the tick and tock of a mechanical clock. “The accurate automatic machine” (Bolter 1984:26) led immediately to “mechanical automata” beginning in the thirteenth century and finally to “computational machines” – the difference engine and analytical engines of Charles Babbage and Countess Ada Lovelace (Bolter p.33–34, p.204–206).

Jacquard loom, Hollerith punch cards, telegraphy and telephony — the electromechanical relay: Bell and Newell (1971) indicate that the Jacquard loom (1801), precursor to Hollerith cards (punch cards, 1887), and “telephone switching technologies” were the roots of a tree leading to the development of the first computers (Bell and Newell diagram p. 39, cf. Davis 2000). By the mid-1800s the telegraph, the precursor of the telephone, was in use throughout the world, its discrete and distinguishable encoding of letters as “dots and dashes” a common sound. By the late 1800s the ticker tape (ca 1870s) was in use, as was the use of Hollerith cards in the 1890 U.S. census. Then came the Teletype (ca. 1910) with its punched-paper use of Baudot code on tape.

Telephone-switching networks of electromechanical relays (invented 1835) was behind the work of George Stibitz (1937), the inventor of the digital adding device. As he worked in Bell Laboratories, he observed the “burdensome’ use of mechanical calculators with gears. “He went home one evening in 1937 intending to test his idea… When the tinkering was over, Stibitz had constructed a binary adding device”. (Valley News, p. 13).

Davis (2000) observes the particular importance of the electromechanical relay (with its two “binary states” open and closed):

It was only with the development, beginning in the 1930s, of electromechanical calculators using electrical relays, that machines were built having the scope Babbage had envisioned.” (Davis, p. 14).

[edit] Mathematics during the 1800s up to the mid-1900s

Symbols and rules: In rapid succession the mathematics of George Boole (1847, 1854), Gottlob Frege (1879), and Giuseppe Peano (1888–1889) reduced arithmetic to a sequence of symbols manipulated by rules. Peano’s The principles of arithmetic, presented by a new method (1888) was “the first attempt at an axiomatization of mathematics in a symbolic language” (van Heijenoort:81ff).

But Heijenoort gives Frege (1879) this kudos: Frege’s is “perhaps the most important single work ever written in logic. … in which we see a ” ‘formula language’, that is a lingua characterica, a language written with special symbols, “for pure thought”, that is, free from rhetorical embellishments … constructed from specific symbols that are manipulated according to definite rules” (van Heijenoort:1). The work of Frege was further simplified and amplified by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1910–1913).

The paradoxes: At the same time a number of disturbing paradoxes appeared in the literature, in particular the Burali-Forti paradox (1897), the Russell paradox (1902–03), and the Richard Paradox (Dixon 1906, cf. Kleene 1952:36–40). The resultant considerations led to Kurt Gödel’s paper (1931) — he specifically cites the paradox of the liar — that completely reduces rules of recursion to numbers.

Effective calculability: In an effort to solve the Entscheidungsproblem defined precisely by Hilbert in 1928, mathematicians first set about to define what was meant by an “effective method” or “effective calculation” or “effective calculability” (i.e., a calculation that would succeed). In rapid succession the following appeared: Alonzo Church, Stephen Kleene and J.B. Rosser’s λ-calculus, (cf. footnote in Alonzo Church 1936a:90, 1936b:110) a finely-honed definition of “general recursion” from the work of Gödel acting on suggestions of Jacques Herbrand (cf. Gödel’s Princeton lectures of 1934) and subsequent simplifications by Kleene (1935-6:237ff, 1943:255ff). Church’s proof (1936:88ff) that the Entscheidungsproblem was unsolvable, Emil Post’s definition of effective calculability as a worker mindlessly following a list of instructions to move left or right through a sequence of rooms and while there either mark or erase a paper or observe the paper and make a yes-no decision about the next instruction (cf. “Formulation I”, Post 1936:289-290). Alan Turing‘s proof of that the Entscheidungsproblem was unsolvable by use of his “a- [automatic-] machine”(Turing 1936-7:116ff) — in effect almost identical to Post’s “formulation”, J. Barkley Rosser‘s definition of “effective method” in terms of “a machine” (Rosser 1939:226). S. C. Kleene’s proposal of a precursor to “Church thesis” that he called “Thesis I” (Kleene 1943:273–274), and a few years later Kleene’s renaming his Thesis “Church’s Thesis” (Kleene 1952:300, 317) and proposing “Turing’s Thesis” (Kleene 1952:376).

[edit] Emil Post (1936) and Alan Turing (1936-7, 1939)

Here is a remarkable coincidence of two men not knowing each other but describing a process of men-as-computers working on computations — and they yield virtually identical definitions.

Emil Post (1936) described the actions of a “computer” (human being) as follows:

“…two concepts are involved: that of a symbol space in which the work leading from problem to answer is to be carried out, and a fixed unalterable set of directions.

His symbol space would be

“a two way infinite sequence of spaces or boxes… The problem solver or worker is to move and work in this symbol space, being capable of being in, and operating in but one box at a time…. a box is to admit of but two possible conditions, i.e., being empty or unmarked, and having a single mark in it, say a vertical stroke.
“One box is to be singled out and called the starting point. …a specific problem is to be given in symbolic form by a finite number of boxes [i.e., INPUT] being marked with a stroke. Likewise the answer [i.e., OUTPUT] is to be given in symbolic form by such a configuration of marked boxes….
“A set of directions applicable to a general problem sets up a deterministic process when applied to each specific problem. This process will terminate only when it comes to the direction of type (C ) [i.e., STOP].” (U p. 289–290) See more at Post-Turing machine

Alan Turing’s work (1936, 1939:160) preceded that of Stibitz (1937); it is unknown whether Stibitz knew of the work of Turing. Turing’s biographer believed that Turing’s use of a typewriter-like model derived from a youthful interest: “Alan had dreamt of inventing typewriters as a boy; Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter ‘mechanical'” (Hodges, p. 96). Given the prevalence of Morse code and telegraphy, ticker tape machines, and Teletypes we might conjecture that all were influences.

Turing — his model of computation is now called a Turing machine — begins, as did Post, with an analysis of a human computer that he whittles down to a simple set of basic motions and “states of mind”. But he continues a step further and creates a machine as a model of computation of numbers (Turing 1936-7:116).

“Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child’s arithmetic book….I assume then that the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite….
“The behavior of the computer at any moment is determined by the symbols which he is observing, and his “state of mind” at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite…
“Let us imagine that the operations performed by the computer to be split up into ‘simple operations’ which are so elementary that it is not easy to imagine them further divided” (Turing 1936-7:136).

Turing’s reduction yields the following:

“The simple operations must therefore include:

“(a) Changes of the symbol on one of the observed squares
“(b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares.

“It may be that some of these change necessarily invoke a change of state of mind. The most general single operation must therefore be taken to be one of the following:

“(A) A possible change (a) of symbol together with a possible change of state of mind.
“(B) A possible change (b) of observed squares, together with a possible change of state of mind”
“We may now construct a machine to do the work of this computer.” (Turing 1936-7:136)

A few years later, Turing expanded his analysis (thesis, definition) with this forceful expression of it:

“A function is said to be “effectively calculable” if its values can be found by some purely mechanical process. Although it is fairly easy to get an intuitive grasp of this idea, it is nevertheless desirable to have some more definite, mathematical expressible definition . . . [he discusses the history of the definition pretty much as presented above with respect to Gödel, Herbrand, Kleene, Church, Turing and Post] . . . We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author’s definition of a computable function, and to an identification of computability † with effective calculability . . . .

“† We shall use the expression “computable function” to mean a function calculable by a machine, and we let “effectively calculable” refer to the intuitive idea without particular identification with any one of these definitions.”(Turing 1939:160)

[edit] J. B. Rosser (1939) and S. C. Kleene (1943)

J. Barkley Rosser boldly defined an ‘effective [mathematical] method’ in the following manner (boldface added):

“‘Effective method’ is used here in the rather special sense of a method each step of which is precisely determined and which is certain to produce the answer in a finite number of steps. With this special meaning, three different precise definitions have been given to date. [his footnote #5; see discussion immediately below]. The simplest of these to state (due to Post and Turing) says essentially that an effective method of solving certain sets of problems exists if one can build a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer. All three definitions are equivalent, so it doesn’t matter which one is used. Moreover, the fact that all three are equivalent is a very strong argument for the correctness of any one.” (Rosser 1939:225–6)

Rosser’s footnote #5 references the work of (1) Church and Kleene and their definition of λ-definability, in particular Church’s use of it in his An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand and Gödel and their use of recursion in particular Gödel’s use in his famous paper On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931); and (3) Post (1936) and Turing (1936-7) in their mechanism-models of computation.

Stephen C. Kleene defined as his now-famous “Thesis I” known as the Church-Turing thesis. But he did this in the following context (boldface in original):

“12. Algorithmic theories… In setting up a complete algorithmic theory, what we do is to describe a procedure, performable for each set of values of the independent variables, which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, “yes” or “no,” to the question, “is the predicate value true?”” (Kleene 1943:273)

[edit] History after 1950

A number of efforts have been directed toward further refinement of the definition of “algorithm”, and activity is on-going because of issues surrounding, in particular, foundations of mathematics (especially the Church-Turing Thesis) and philosophy of mind (especially arguments around artificial intelligence). For more, see Algorithm characterizations.

[edit] See also

Sister projectWikibooks has a book on the topic of

Sister project At Wikiversity you can learn more and teach others about Algorithm at:

[edit] References

  • Axt, P. (1959) On a Subrecursive Hierarchy and Primitive Recursive Degrees, Transactions of the American Mathematical Society 92, pp. 85–105
  • Blass, Andreas; Gurevich, Yuri (2003). “Algorithms: A Quest for Absolute Definitions“. Bulletin of European Association for Theoretical Computer Science 81. http://research.microsoft.com/~gurevich/Opera/164.pdf. . Includes an excellent bibliography of 56 references.
  • Boolos, George; Jeffrey, Richard (1974, 1980, 1989, 1999). Computability and Logic (4th ed.). Cambridge University Press, London. ISBN 0-521-20402-X. : cf. Chapter 3 Turing machines where they discuss “certain enumerable sets not effectively (mechanically) enumerable”.
  • Burgin, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005. ISBN 0387955690
  • Campagnolo, M.L., Moore, C., and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In Proc. of the 4th Conference on Real Numbers and Computers, Odense University, pp. 91–109
  • Church, Alonzo (1936a). “An Unsolvable Problem of Elementary Number Theory”. The American Journal of Mathematics 58: 345–363. doi:10.2307/2371045.  Reprinted in The Undecidable, p. 89ff. The first expression of “Church’s Thesis”. See in particular page 100 (The Undecidable) where he defines the notion of “effective calculability” in terms of “an algorithm”, and he uses the word “terminates”, etc.
  • Church, Alonzo (1936b). “A Note on the Entscheidungsproblem”. Journal of Symbolic Logic 1 no. 1 and volume 1 no. 3.  Reprinted in The Undecidable, p. 110ff. Church shows that the Entscheidungsproblem is unsolvable in about 3 pages of text and 3 pages of footnotes.
  • Daffa’, Ali Abdullah al- (1977). The Muslim contribution to mathematics. London: Croom Helm. ISBN 0-85664-464-1. 
  • Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press.  Davis gives commentary before each article. Papers of Gödel, Alonzo Church, Turing, Rosser, Kleene, and Emil Post are included; those cited in the article are listed here by author’s name.
  • Davis, Martin (2000). Engines of Logic: Mathematicians and the Origin of the Computer. New York: W. W. Nortion.  Davis offers concise biographies of Leibniz, Boole, Frege, Cantor, Hilbert, Gödel and Turing with von Neumann as the show-stealing villain. Very brief bios of Joseph-Marie Jacquard, Babbage, Ada Lovelace, Claude Shannon, Howard Aiken, etc.
  • Paul E. Black, algorithm at the NIST Dictionary of Algorithms and Data Structures.
  • Dennett, Daniel (1995). Darwin’s Dangerous Idea. New York: Touchstone/Simon & Schuster. 
  • Yuri Gurevich, Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pages 77–111. Includes bibliography of 33 sources.
  • Kleene C., Stephen (1936). “General Recursive Functions of Natural Numbers”. Mathematische Annalen Band 112, Heft 5: 727–742. doi:10.1007/BF01565439+.  Presented to the American Mathematical Society, September 1935. Reprinted in The Undecidable, p. 237ff. Kleene’s definition of “general recursion” (known now as mu-recursion) was used by Church in his 1935 paper An Unsolvable Problem of Elementary Number Theory that proved the “decision problem” to be “undecidable” (i.e., a negative result).
  • Kleene C., Stephen (1943). “Recursive Predicates and Quantifiers”. American Mathematical Society Transactions Volume 54, No. 1: 41–73. doi:10.2307/1990131.  Reprinted in The Undecidable, p. 255ff. Kleene refined his definition of “general recursion” and proceeded in his chapter “12. Algorithmic theories” to posit “Thesis I” (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it “Church’s Thesis”(Kleene 1952:317) (i.e., the Church thesis).
  • Kleene, Stephen C. (First Edition 1952). Introduction to Metamathematics (Tenth Edition 1991 ed.). North-Holland Publishing Company.  Excellent — accessible, readable — reference source for mathematical “foundations”.
  • Knuth, Donald (1997). Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison-Wesley. ISBN 0201896834. 
  • Kosovsky, N. K. Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, LSU Publ., Leningrad, 1981
  • Kowalski, Robert (1979). “Algorithm=Logic+Control”. Communications of the ACM (ACM Press) 22 (7): 424–436. doi:10.1145/359131.359136. ISSN 0001-0782. 
  • A. A. Markov (1954) Theory of algorithms. [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e., Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.]
  • Minsky, Marvin (1967). Computation: Finite and Infinite Machines (First ed.). Prentice-Hall, Englewood Cliffs, NJ.  Minsky expands his “…idea of an algorithm — an effective procedure…” in chapter 5.1 Computability, Effective Procedures and Algorithms. Infinite machines.”
  • Post, Emil (1936). “Finite Combinatory Processes, Formulation I”. The Journal of Symbolic Logic 1: pp.103–105. doi:10.2307/2269031.  Reprinted in The Undecidable, p. 289ff. Post defines a simple algorithmic-like process of a man writing marks or erasing marks and going from box to box and eventually halting, as he follows a list of simple instructions. This is cited by Kleene as one source of his “Thesis I”, the so-called Church-Turing thesis.
  • Rosser, J.B. (1939). “An Informal Exposition of Proofs of Godel’s Theorem and Church’s Theorem”. Journal of Symbolic Logic 4.  Reprinted in The Undecidable, p. 223ff. Herein is Rosser’s famous definition of “effective method”: “…a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps… a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer” (p. 225–226, The Undecidable)
  • Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing Company. 
  • Stone, Harold S.. Introduction to Computer Organization and Data Structures (1972 ed.). McGraw-Hill, New York.  Cf. in particular the first chapter titled: Algorithms, Turing Machines, and Programs. His succinct informal definition: “…any sequence of instructions that can be obeyed by a robot, is called an algorithm” (p. 4).
  • Turing, Alan M. (1936-7). “On Computable Numbers, With An Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society series 2, volume 42: 230–265. doi:10.1112/plms/s2-42.1.230. . Corrections, ibid, vol. 43(1937) pp.544–546. Reprinted in The Undecidable, p. 116ff. Turing’s famous paper completed as a Master’s dissertation while at King’s College Cambridge UK.
  • Turing, Alan M. (1939). “Systems of Logic Based on Ordinals”. Proceedings of the London Mathematical Society series 2, volume 45: 161–228. doi:10.1112/plms/s2-45.1.161.  Reprinted in The Undecidable, p. 155ff. Turing’s paper that defined “the oracle” was his PhD thesis while at Princeton USA.
  • United States Patent and Trademark Office (2006), 2106.02 **>Mathematical Algorithms< – 2100 Patentability, Manual of Patent Examining Procedure (MPEP). Latest revision August 2006

[edit] Secondary references

[edit] External links

Read Full Post »

Computer programming

From Wikipedia, the free encyclopedia

Jump to: navigation, search

“Programming” redirects here. For other uses, see Programming (disambiguation).
Software development process
Activities and steps
Requirements · Specification
Architecture · Design
Implementation · Testing
Deployment · Maintenance
Models
Agile · Cleanroom · DSDM
Iterative · RAD  · RUP  · Spiral
Waterfall · XP · Scrum  · Lean
V-Model  · FDD
Supporting disciplines
Configuration management
Documentation
Quality assurance (SQA)
Project management
User experience design
Tools
Compiler  · Debugger  · Profiler
GUI designer
Integrated development environment
This box: view  talk

Computer programming (often shortened to programming or coding) is the process of writing, testing, debugging/troubleshooting, and maintaining the source code of computer programs. This source code is written in a programming language. The code may be a modification of an existing source or something completely new. The purpose of programming is to create a program that exhibits a certain desired behaviour (customization). The process of writing source code often requires expertise in many different subjects, including knowledge of the application domain, specialized algorithms and formal logic.

Contents

[hide]

[edit] Overview

Within software engineering, programming (the implementation) is regarded as one phase in a software development process.

There is an ongoing debate on the extent to which the writing of programs is an art, a craft or an engineering discipline.[1] Good programming is generally considered to be the measured application of all three, with the goal of producing an efficient and evolvable software solution (the criteria for “efficient” and “evolvable” vary considerably). The discipline differs from many other technical professions in that programmers generally do not need to be licensed or pass any standardized (or governmentally regulated) certification tests in order to call themselves “programmers” or even “software engineers.” However, representing oneself as a “Professional Software Engineer” without a license from an accredited institution is illegal in many parts of the world.[citation needed]

Another ongoing debate is the extent to which the programming language used in writing computer programs affects the form that the final program takes. This debate is analogous to that surrounding the Sapir-Whorf hypothesis [2] in linguistics, that postulates that a particular language’s nature influences the habitual thought of its speakers. Different language patterns yield different patterns of thought. This idea challenges the possibility of representing the world perfectly with language, because it acknowledges that the mechanisms of any language condition the thoughts of its speaker community.

Said another way, programming is the craft of transforming requirements into something that a computer can execute.

[edit] History of programming

Wired plug board for an IBM 402 Accounting Machine.

The concept of devices that operate following a pre-defined set of instructions traces back to Greek Mythology, notably Hephaestus and his mechanical servants[3]. The Antikythera mechanism was a calculator utilizing gears of various sizes and configuration to determine its operation. The earliest known programmable machines (machines whose behavior can be controlled and predicted with a set of instructions) were Al-Jazari‘s programmable Automata in 1206.[4] One of Al-Jazari’s robots was originally a boat with four automatic musicians that floated on a lake to entertain guests at royal drinking parties. Programming this mechanism‘s behavior meant placing pegs and cams into a wooden drum at specific locations. These would then bump into little levers that operate a percussion instrument. The output of this device was a small drummer playing various rhythms and drum patterns.[5][6] Another sophisticated programmable machine by Al-Jazari was the castle clock, notable for its concept of variables which the operator could manipulate as necessary (i.e. the length of day and night). The Jacquard Loom, which Joseph Marie Jacquard developed in 1801, uses a series of pasteboard cards with holes punched in them. The hole pattern represented the pattern that the loom had to follow in weaving cloth. The loom could produce entirely different weaves using different sets of cards. Charles Babbage adopted the use of punched cards around 1830 to control his Analytical Engine. The synthesis of numerical calculation, predetermined operation and output, along with a way to organize and input instructions in a manner relatively easy for humans to conceive and produce, led to the modern development of computer programming. Development of computer programming accelerated through the Industrial Revolution.

In the late 1880s Herman Hollerith invented the recording of data on a medium that could then be read by a machine. Prior uses of machine readable media, above, had been for control, not data. “After some initial trials with paper tape, he settled on punched cards…”[7] To process these punched cards, first known as “Hollerith cards” he invented the tabulator, and the key punch machines. These three inventions were the foundation of the modern information processing industry. In 1896 he founded the Tabulating Machine Company (which later became the core of IBM). The addition of a control panel to his 1906 Type I Tabulator allowed it to do different jobs without having to be physically rebuilt. By the late 1940s there were a variety of plug-board programmable machines, called unit record equipment, to perform data processing tasks (card reading). Early computer programmers used plug-boards for the variety of complex calculations requested of the newly invented machines.

Data and instructions could be stored on external punch cards, which were kept in order and arranged in program decks.

The invention of the Von Neumann architecture allowed computer programs to be stored in computer memory. Early programs had to be painstakingly crafted using the instructions of the particular machine, often in binary notation. Every model of computer would be likely to need different instructions to do the same task. Later assembly languages were developed that let the programmer specify each instruction in a text format, entering abbreviations for each operation code instead of a number and specifying addresses in symbolic form (e.g. ADD X, TOTAL). In 1954 Fortran was invented, being the first high level programming language to have a functional implementation.[8][9] It allowed programmers to specify calculations by entering a formula directly (e.g. Y = X*2 + 5*X + 9). The program text, or source, is converted into machine instructions using a special program called a compiler. Many other languages were developed, including some for commercial programming, such as COBOL. Programs were mostly still entered using punch cards or paper tape. (See computer programming in the punch card era). By the late 1960s, data storage devices and computer terminals became inexpensive enough so programs could be created by typing directly into the computers. Text editors were developed that allowed changes and corrections to be made much more easily than with punch cards.

As time has progressed, computers have made giant leaps in the area of processing power. This has brought about newer programming languages that are more abstracted from the underlying hardware. Although these high-level languages usually incur greater overhead, the increase in speed of modern computers has made the use of these languages much more practical than in the past. These increasingly abstracted languages typically are easier to learn and allow the programmer to develop applications much more efficiently and with less code. However, high-level languages are still impractical for many programs, such as those where low-level hardware control is necessary or where processing speed is at a premium.

Throughout the second half of the twentieth century, programming was an attractive career in most developed countries. Some forms of programming have been increasingly subject to offshore outsourcing (importing software and services from other countries, usually at a lower wage), making programming career decisions in developed countries more complicated, while increasing economic opportunities in less developed areas. It is unclear how far this trend will continue and how deeply it will impact programmer wages and opportunities.

[edit] Modern programming

[edit] Quality requirements

Whatever the approach to software development may be, the final program must satisfy some fundamental properties. The following five properties are among the most relevant:

  • Efficiency/performance: the amount of system resources a program consumes (processor time, memory space, slow devices such as disks, network bandwidth and to some extent even user interaction): the less, the better. This also includes correct disposal of some resources, such as cleaning up temporary files and lack of memory leaks.
  • Reliability: how often the results of a program are correct. This depends on conceptual correctness of algorithms, and minimization of programming mistakes, such as mistakes in resource management (e.g. buffer overflows and race conditions) and logic errors (such as division by zero).
  • Robustness: how well a program anticipates problems not due to programmer error. This includes situations such as incorrect, inappropriate or corrupt data, unavailability of needed resources such as memory, operating system services and network connections, and user error.
  • Usability: the ergonomics of a program: the ease with which a person can use the program for its intended purpose, or in some cases even unanticipated purposes. Such issues can make or break its success even regardless of other issues. This involves a wide range of textual, graphical and sometimes hardware elements that improve the clarity, intuitiveness, cohesiveness and completeness of a program’s user interface.
  • Portability: the range of computer hardware and operating system platforms on which the source code of a program can be compiled/interpreted and run. This depends on differences in the programming facilities provided by the different platforms, including hardware and operating system resources, expected behaviour of the hardware and operating system, and availability of platform specific compilers (and sometimes libraries) for the language of the source code.

[edit] Algorithmic complexity

The academic field and the engineering practice of computer programming are both largely concerned with discovering and implementing the most efficient algorithms for a given class of problem. For this purpose, algorithms are classified into orders using so-called Big O notation, O(n), which expresses resource use, such as execution time or memory consumption, in terms of the size of an input. Expert programmers are familiar with a variety of well-established algorithms and their respective complexities and use this knowledge to choose algorithms that are best suited to the circumstances.

[edit] Methodologies

The first step in most formal software development projects is requirements analysis, followed by testing to determine value modeling, implementation, and failure elimination (debugging). There exist a lot of differing approaches for each of those tasks. One approach popular for requirements analysis is Use Case analysis.

Popular modeling techniques include Object-Oriented Analysis and Design (OOAD) and Model-Driven Architecture (MDA). The Unified Modeling Language (UML) is a notation used for both OOAD and MDA.

A similar technique used for database design is Entity-Relationship Modeling (ER Modeling).

Implementation techniques include imperative languages (object-oriented or procedural), functional languages, and logic languages.

[edit] Measuring language usage

It is very difficult to determine what are the most popular of modern programming languages. Some languages are very popular for particular kinds of applications (e.g., COBOL is still strong in the corporate data center, often on large mainframes, FORTRAN in engineering applications, scripting languages in web development, and C in embedded applications), while some languages are regularly used to write many different kinds of applications.

Methods of measuring language popularity include: counting the number of job advertisements that mention the language[10], the number of books teaching the language that are sold (this overestimates the importance of newer languages), and estimates of the number of existing lines of code written in the language (this underestimates the number of users of business languages such as COBOL).

[edit] Debugging

A bug which was debugged in 1947.

Debugging is a very important task in the software development process, because an incorrect program can have significant consequences for its users. Some languages are more prone to some kinds of faults because their specification does not require compilers to perform as much checking as other languages. Use of a static analysis tool can help detect some possible problems.

Debugging is often done with IDEs like Visual Studio, NetBeans, and Eclipse. Standalone debuggers like gdb are also used, and these often provide less of a visual environment, usually using a command line.

[edit] Programming languages

Different programming languages support different styles of programming (called programming paradigms). The choice of language used is subject to many considerations, such as company policy, suitability to task, availability of third-party packages, or individual preference. Ideally, the programming language best suited for the task at hand will be selected. Trade-offs from this ideal involve finding enough programmers who know the language to build a team, the availability of compilers for that language, and the efficiency with which programs written in a given language execute.

Allen Downey, in his book How To Think Like A Computer Scientist, writes:

The details look different in different languages, but a few basic instructions appear in just about every language:

  • input: Get data from the keyboard, a file, or some other device.
  • output: Display data on the screen or send data to a file or other device.
  • arithmetic: Perform basic arithmetical operations like addition and multiplication.
  • conditional execution: Check for certain conditions and execute the appropriate sequence of statements.
  • repetition: Perform some action repeatedly, usually with some variation.

Many computer languages provide a mechanism to call functions provided by libraries. Provided the functions in a library follow the appropriate runtime conventions (eg, method of passing arguments), then these functions may be written in any other language.

[edit] Programmers

Main article: Programmer

Computer programmers are those who write computer software. Their jobs usually involve:

[edit] References

  1. ^ Paul Graham (2003). Hackers and Painters. http://www.paulgraham.com/hp.html. Retrieved on 2006-08-22. 
  2. ^ Kenneth E. Iverson, the originator of the APL programming language, believed that the Sapir–Whorf hypothesis applied to computer languages (without actually mentioning the hypothesis by name). His Turing award lecture, “Notation as a tool of thought”, was devoted to this theme, arguing that more powerful notations aided thinking about computer algorithms. Iverson K.E.,”Notation as a tool of thought“, Communications of the ACM, 23: 444-465 (August 1980).
  3. ^ New World Encyclopedia Online Edition New World Encyclopedia
  4. ^ Al-Jazari – the Mechanical Genius, MuslimHeritage.com
  5. ^ A 13th Century Programmable Robot, University of Sheffield
  6. ^ Fowler, Charles B. (October 1967), “The Museum of Music: A History of Mechanical Instruments”, Music Educators Journal 54 (2): 45–49, doi:10.2307/3391092 
  7. ^ Columbia University Computing History – Herman Hollerith
  8. ^ [1]
  9. ^ [2]
  10. ^ Survey of Job advertisements mentioning a given language>

[edit] Further reading

  • Weinberg, Gerald M., The Psychology of Computer Programming, New York: Van Nostrand Reinhold, 1971

[edit] See also

[edit] External links

Sister projectWikibooks has a book on the topic of

Sister projectWikibooks has a book on the topic of

[show]

v  d  e

Major fields of computer science

Mathematical foundations

Theory of computation

Algorithms and data structures

Programming languages and Compilers

Concurrent, Parallel, and Distributed systems

Software engineering

System architecture

Telecommunication & Networking

Databases

Artificial intelligence

Computer graphics

Human computer interaction

Scientific computing

NOTE: Computer science can also be split up into different topics or fields according to the ACM Computing Classification System.
 
 
 
 
 
 
 
Computer architecture · Computer organization · Operating systems
 
Computer audio · Routing · Network topology · Cryptography
 
Data mining · Relational databases · SQL • OLAP
 
 
Visualization · Image processing
 
 
 
[show]

v  d  e

Software engineering

Fields

Concepts

Orientations

Models

Software
engineers

Related fields

 
 
 
 
Development models: AgileIterative modelRUPScrumSpiral modelWaterfall modelXPV-Model
Other models: CMMIData modelFunction modelIDEFInformation modelMetamodelingObject modelView modelUML
 
 

Read Full Post »

Programming language

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Programming language
lists

A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that specify the behavior of a machine, to express algorithms precisely, or as a mode of human communication.

Many programming languages have some form of written specification of their syntax and semantics, since computers require precisely defined instructions. Some (such as C) are defined by a specification document (for example, an ISO Standard), while others (such as Perl) have a dominant implementation.

The earliest programming languages predate the invention of the computer, and were used to direct the behavior of machines such as Jacquard looms and player pianos. Thousands of different programming languages have been created, mainly in the computer field,[1] with many more being created every year.

Contents

[hide]

[edit] Definitions

Traits often considered important for constituting a programming language:

  • Target: Programming languages differ from natural languages in that natural languages are only used for interaction between people, while programming languages also allow humans to communicate instructions to machines. Some programming languages are used by one device to control another. For example PostScript programs are frequently created by another program to control a computer printer or display.
  • 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 and Charity are examples of languages that are not Turing complete, yet often called programming languages.[4][5]

Some authors restrict the term “programming language” to those languages that can express all possible algorithms;[6] sometimes the term “computer language” is used for more limited artificial languages.

Non-computational languages, such as markup languages like HTML or formal grammars like BNF, are usually not considered programming languages. A programming language (which may or may not be Turing complete) may be embedded in these non-computational (host) languages.

[edit] Usage

A programming language provides a structured mechanism for defining pieces of data, and the operations or transformations that may be carried out automatically on that data. A programmer uses the abstractions present in the language to represent the concepts involved in a computation. These concepts are represented as a collection of the simplest elements available (called primitives). [7]

Programming languages differ from most other forms of human expression in that they require a greater degree of precision and completeness. When using a natural language to communicate with other people, human authors and speakers can be ambiguous and make small errors, and still expect their intent to be understood. However, figuratively speaking, computers “do exactly what they are told to do”, and cannot “understand” what code the programmer intended to write. The combination of the language definition, a program, and the program’s inputs must fully specify the external behavior that occurs when the program is executed, within the domain of control of that program.

Programs for a computer might be executed in a batch process without human interaction, or a user might type commands in an interactive session of an interpreter. In this case the “commands” are simply programs, whose execution is chained together. When a language is used to give commands to a software application (such as a shell) it is called a scripting language[citation needed].

Many languages have been designed from scratch, altered to meet new needs, combined with other languages, and eventually fallen into disuse. Although there have been attempts to design one “universal” computer language that serves all purposes, all of them have failed to be generally accepted as filling this role.[8] The need for diverse computer languages arises from the diversity of contexts in which languages are used:

  • Programs range from tiny scripts written by individual hobbyists to huge systems written by hundreds of programmers.
  • Programmers range in expertise from novices who need simplicity above all else, to experts who may be comfortable with considerable complexity.
  • Programs must balance speed, size, and simplicity on systems ranging from microcontrollers to supercomputers.
  • Programs may be written once and not change for generations, or they may undergo nearly constant modification.
  • Finally, programmers may simply differ in their tastes: they may be accustomed to discussing problems and expressing them in a particular language.

One common trend in the development of programming languages has been to add more ability to solve problems using a higher level of abstraction. The earliest programming languages were tied very closely to the underlying hardware of the computer. As new programming languages have developed, features have been added that let programmers express ideas that are more remote from simple translation into underlying hardware instructions. Because programmers are less tied to the complexity of the computer, their programs can do more computing with less effort from the programmer. This lets them write more functionality per time unit.[9]

Natural language processors have been proposed as a way to eliminate the need for a specialized language for programming. However, this goal remains distant and its benefits are open to debate. Edsger Dijkstra took the position that the use of a formal language is essential to prevent the introduction of meaningless constructs, and dismissed natural……… language programming as “foolish”.[10] Alan Perlis was similarly dismissive of the idea.[11]

[edit] Elements

All programming languages have some primitive building blocks for the description of data and the processes or transformations applied to them (like the addition of two numbers or the selection of an item from a collection). These primitives are defined by syntactic and semantic rules which describe their structure and meaning respectively.

[edit] Syntax

Parse tree of Python code with inset tokenization

Syntax highlighting is often used to aid programmers in recognizing elements of source code. The language above is Python.

A programming language’s surface form is known as its syntax. Most programming languages are purely textual; they use sequences of text including words, numbers, and punctuation, much like written natural languages. On the other hand, there are some programming languages which are more graphical in nature, using visual relationships between symbols to specify a program.

The syntax of a language describes the possible combinations of symbols that form a syntactically correct program. The meaning given to a combination of symbols is handled by semantics (either formal or hard-coded in a reference implementation). Since most languages are textual, this article discusses textual syntax.

Programming language syntax is usually defined using a combination of regular expressions (for lexical structure) and Backus-Naur Form (for grammatical structure). Below is a simple grammar, based on Lisp:

 expression ::= atom   | list
 atom       ::= number | symbol
 number     ::= [+-]?['0'-'9']+
 symbol     ::= ['A'-'Z''a'-'z'].*
 list       ::= '(' expression* ')'

This grammar specifies the following:

  • an expression is either an atom or a list;
  • an atom is either a number or a symbol;
  • a number is an unbroken sequence of one or more decimal digits, optionally preceded by a plus or minus sign;
  • a symbol is a letter followed by zero or more of any characters (excluding whitespace); and
  • a list is a matched pair of parentheses, with zero or more expressions inside it.

The following are examples of well-formed token sequences in this grammar: ‘12345‘, ‘()‘, ‘(a b c232 (1))

Not all syntactically correct programs are semantically correct. Many syntactically correct programs are nonetheless ill-formed, per the language’s rules; and may (depending on the language specification and the soundness of the implementation) result in an error on translation or execution. In some cases, such programs may exhibit undefined behavior. Even when a program is well-defined within a language, it may still have a meaning that is not intended by the person who wrote it.

Using natural language as an example, it may not be possible to assign a meaning to a grammatically correct sentence or the sentence may be false:

  • Colorless green ideas sleep furiously.” is grammatically well-formed but has no generally accepted meaning.
  • “John is a married bachelor.” is grammatically well-formed but expresses a meaning that cannot be true.

The following C language fragment is syntactically correct, but performs an operation that is not semantically defined (because p is a null pointer, the operations p->real and p->im have no meaning):

complex *p = NULL;
complex abs_p = sqrt (p->real * p->real + p->im * p->im);

The grammar needed to specify a programming language can be classified by its position in the Chomsky hierarchy. The syntax of most programming languages can be specified using a Type-2 grammar, i.e., they are context-free grammars.[12]

[edit] Static semantics

The static semantics defines restrictions on the structure of valid texts that are hard or impossible to express in standard syntactic formalisms.[13] The most important of these restrictions are covered by type systems.

[edit] Type system

Main articles: Type system and Type safety

A type system defines how a programming language classifies values and expressions into types, how it can manipulate those types and how they interact. This generally includes a description of the data structures that can be constructed in the language. The design and study of type systems using formal mathematics is known as type theory.

[edit] Typed versus untyped languages

A language is typed if the specification of every operation defines types of data to which the operation is applicable, with the implication that it is not applicable to other types.[14] For example, “this text between the quotes” is a string. In most programming languages, dividing a number by a string has no meaning. Most modern programming languages will therefore reject any program attempting to perform such an operation. In some languages, the meaningless operation will be detected when the program is compiled (“static” type checking), and rejected by the compiler, while in others, it will be detected when the program is run (“dynamic” type checking), resulting in a runtime exception.

A special case of typed languages are the single-type languages. These are often scripting or markup languages, such as Rexx or SGML, and have only one data type—most commonly character strings which are used for both symbolic and numeric data.

In contrast, an untyped language, such as most assembly languages, allows any operation to be performed on any data, which are generally considered to be sequences of bits of various lengths.[14] High-level languages which are untyped include BCPL and some varieties of Forth.

In practice, while few languages are considered typed from the point of view of type theory (verifying or rejecting all operations), most modern languages offer a degree of typing.[14] Many production languages provide means to bypass or subvert the type system.

[edit] Static versus dynamic typing

In static typing all expressions have their types determined prior to the program being run (typically at compile-time). For example, 1 and (2+2) are integer expressions; they cannot be passed to a function that expects a string, or stored in a variable that is defined to hold dates.[14]

Statically typed languages can be either manifestly typed or type-inferred. In the first case, the programmer must explicitly write types at certain textual positions (for example, at variable declarations). In the second case, the compiler infers the types of expressions and declarations based on context. Most mainstream statically typed languages, such as C++, C# and Java, are manifestly typed. Complete type inference has traditionally been associated with less mainstream languages, such as Haskell and ML. However, many manifestly typed languages support partial type inference; for example, Java and C# both infer types in certain limited cases.[15]

Dynamic typing, also called latent typing, determines the type-safety of operations at runtime; in other words, types are associated with runtime values rather than textual expressions.[14] As with type-inferred languages, dynamically typed languages do not require the programmer to write explicit type annotations on expressions. Among other things, this may permit a single variable to refer to values of different types at different points in the program execution. However, type errors cannot be automatically detected until a piece of code is actually executed, making debugging more difficult. Ruby, Lisp, JavaScript, and Python are dynamically typed.

[edit] Weak and strong typing

Weak typing allows a value of one type to be treated as another, for example treating a string as a number.[14] This can occasionally be useful, but it can also allow some kinds of program faults to go undetected at compile time and even at run time.

Strong typing prevents the above. An attempt to perform an operation on the wrong type of value raises an error.[14] Strongly typed languages are often termed type-safe or safe.

An alternative definition for “weakly typed” refers to languages, such as Perl and JavaScript, which permit a large number of implicit type conversions. In JavaScript, for example, the expression 2 * x implicitly converts x to a number, and this conversion succeeds even if x is null, undefined, an Array, or a string of letters. Such implicit conversions are often useful, but they can mask programming errors.

Strong and static are now generally considered orthogonal concepts, but usage in the literature differs. Some use the term strongly typed to mean strongly, statically typed, or, even more confusingly, to mean simply statically typed. Thus C has been called both strongly typed and weakly, statically typed.[16][17]

[edit] Execution semantics

Once data has been specified, the machine must be instructed to perform operations on the data. The execution semantics of a language defines how and when the various constructs of a language should produce a program behavior.

For example, the semantics may define the strategy by which expressions are evaluated to values, or the manner in which control structures conditionally execute statements.

[edit] Core library

For more details on this topic, see Standard library.

Most programming languages have an associated core library (sometimes known as the ‘Standard library’, especially if it is included as part of the published language standard), which is conventionally made available by all implementations of the language. Core libraries typically include definitions for commonly used algorithms, data structures, and mechanisms for input and output.

A language’s core library is often treated as part of the language by its users, although the designers may have treated it as a separate entity. Many language specifications define a core that must be made available in all implementations, and in the case of standardized languages this core library may be required. The line between a language and its core library therefore differs from language to language. Indeed, some languages are designed so that the meanings of certain syntactic constructs cannot even be described without referring to the core library. For example, in Java, a string literal is defined as an instance of the java.lang.String class; similarly, in Smalltalk, an anonymous function expression (a “block”) constructs an instance of the library’s BlockContext class. Conversely, Scheme contains multiple coherent subsets that suffice to construct the rest of the language as library macros, and so the language designers do not even bother to say which portions of the language must be implemented as language constructs, and which must be implemented as parts of a library.

[edit] Practice

A Jovan language’s designers and users must construct a number of artifacts that govern and enable the practice of programming. The most important of these artifacts are the language specification and implementation.

[edit] Specification

The specification of a programming language is intended to provide a definition that the language users and the implementors can use to determine whether the behavior of a program is correct, given its source code.

A programming language specification can take several forms, including the following:

  • An explicit definition of the syntax, static semantics, and execution semantics of the language. While syntax is commonly specified using a formal grammar, semantic definitions may be written in natural language (e.g., the C language), or a formal semantics (e.g., the Standard ML[18] and Scheme[19] specifications).
  • A description of the behavior of a translator for the language (e.g., the C++ and Fortran specifications). The syntax and semantics of the language have to be inferred from this description, which may be written in natural or a formal language.
  • A reference or model implementation, sometimes written in the language being specified (e.g., Prolog or ANSI REXX[20]). The syntax and semantics of the language are explicit in the behavior of the reference implementation.

[edit] Implementation

An implementation of a programming language provides a way to execute that program on one or more configurations of hardware and software. There are, broadly, two approaches to programming language implementation: compilation and interpretation. It is generally possible to implement a language using either technique.

The output of a compiler may be executed by hardware or a program called an interpreter. In some implementations that make use of the interpreter approach there is no distinct boundary between compiling and interpreting. For instance, some implementations of the BASIC programming language compile and then execute the source a line at a time.

Programs that are executed directly on the hardware usually run several orders of magnitude faster than those that are interpreted in software.[citation needed]

One technique for improving the performance of interpreted programs is just-in-time compilation. Here the virtual machine, just before execution, translates the blocks of bytecode which are going to be used to machine code, for direct execution on the hardware.

[edit] History

A selection of textbooks that teach programming, in languages both popular and obscure. These are only a few of the thousands of programming languages and dialects that have been designed in history.

[edit] Early developments

The first programming languages predate the modern computer. The 19th century had “programmable” looms and player piano scrolls which implemented what are today recognized as examples of domain-specific programming languages. By the beginning of the twentieth century, punch cards encoded data and directed mechanical processing. In the 1930s and 1940s, the formalisms of Alonzo Church‘s lambda calculus and Alan Turing‘s Turing machines provided mathematical abstractions for expressing algorithms; the lambda calculus remains influential in language design.[21]

In the 1940s, the first electrically powered digital computers were created. The first high-level programming language to be designed for a computer was Plankalkül, developed for the German Z3 by Konrad Zuse between 1943 and 1945. However, it was not implemented until much later because of wartime damage.[citation needed]

Programmers of early 1950s computers, notably UNIVAC I and IBM 701, used machine language programs, that is, the first generation language (1GL). 1GL programming was quickly superseded by similarly machine-specific, but mnemonic, second generation languages (2GL) known as assembly languages or “assembler”. Later in the 1950s, assembly language programming, which had evolved to include the use of macro instructions, was followed by the development of “third generation” programming languages (3GL), such as FORTRAN, LISP, and COBOL. 3GLs are more abstract and are “portable”, or at least implemented similar on computers that do not support the same native machine code. Updated versions of all of these 3GLs are still in general use, and each has strongly influenced the development of later languages.[22] At the end of the 1950s, the language formalized as Algol 60 was introduced, and most later programming languages are, in many respects, descendants of Algol.[22] The format and use of the early programming languages was heavily influenced by the constraints of the interface.[23]

[edit] Refinement

The period from the 1960s to the late 1970s brought the development of the major language paradigms now in use, though many aspects were refinements of ideas in the very first Third-generation programming languages:

  • APL introduced array programming and influenced functional programming.[24]
  • PL/I (NPL) was designed in the early 1960s to incorporate the best ideas from FORTRAN and COBOL.
  • In the 1960s, Simula was the first language designed to support object-oriented programming; in the mid-1970s, Smalltalk followed with the first “purely” object-oriented language.
  • C was developed between 1969 and 1973 as a systems programming language, and remains popular.[25]
  • Prolog, designed in 1972, was the first logic programming language.
  • In 1978, ML built a polymorphic type system on top of Lisp, pioneering statically typed functional programming languages.

Each of these languages spawned an entire family of descendants, and most modern languages count at least one of them in their ancestry.

The 1960s and 1970s also saw considerable debate over the merits of structured programming, and whether programming languages should be designed to support it.[26] Edsger Dijkstra, in a famous 1968 letter published in the Communications of the ACM, argued that GOTO statements should be eliminated from all “higher level” programming languages.[27]

The 1960s and 1970s also saw expansion of techniques that reduced the footprint of a program as well as improved productivity of the programmer and user. The card deck for an early 4GL was a lot smaller for the same functionality expressed in a 3GL deck.

[edit] Consolidation and growth

The 1980s were years of relative consolidation. C++ combined object-oriented and systems programming. The United States government standardized Ada, a systems programming language derived from Pascal and intended for use by defense contractors. In Japan and elsewhere, vast sums were spent investigating so-called “fifth generation” languages that incorporated logic programming constructs.[28] The functional languages community moved to standardize ML and Lisp. Rather than inventing new paradigms, all of these movements elaborated upon the ideas invented in the previous decade.

One important trend in language design during the 1980s was an increased focus on programming for large-scale systems through the use of modules, or large-scale organizational units of code. Modula-2, Ada, and ML all developed notable module systems in the 1980s, although other languages, such as PL/I, already had extensive support for modular programming. Module systems were often wedded to generic programming constructs.[29]

The rapid growth of the Internet in the mid-1990s created opportunities for new languages. Perl, originally a Unix scripting tool first released in 1987, became common in dynamic Web sites. Java came to be used for server-side programming. These developments were not fundamentally novel, rather they were refinements to existing languages and paradigms, and largely based on the C family of programming languages.

Programming language evolution continues, in both industry and research. Current directions include security and reliability verification, new kinds of modularity (mixins, delegates, aspects), and database integration such as Microsoft’s LINQ.

The 4GLs are examples of languages which are domain-specific, such as SQL, which manipulates and returns sets of data rather than the scalar values which are canonical to most programming languages. Perl, for example, with its ‘here document‘ can hold multiple 4GL programs, as well as multiple JavaScript programs, in part of its own perl code and use variable interpolation in the ‘here document’ to support multi-language programming.[30]

[edit] Measuring language usage

It is difficult to determine which programming languages are most widely used, and what usage means varies by context. One language may occupy the greater number of programmer hours, a different one have more lines of code, and a third utilize the most CPU time. Some languages are very popular for particular kinds of applications. For example, COBOL is still strong in the corporate data center, often on large mainframes; FORTRAN in engineering applications; C in embedded applications and operating systems; and other languages are regularly used to write many different kinds of applications.

Various methods of measuring language popularity, each subject to a different bias over what is measured, have been proposed:

  • counting the number of job advertisements that mention the language[31]
  • the number of books sold that teach or describe the language[32]
  • estimates of the number of existing lines of code written in the language—which may underestimate languages not often found in public searches[33]
  • counts of language references (i.e., to the name of the language) found using a web search engine.

Combining and averaging information from various internet sites, langpop.com claims that [34] in 2008 the 10 most cited programming languages are (in alphabetical order): C, C++, C#, Java, JavaScript, Perl, PHP, Python, Ruby, and SQL.

[edit] Taxonomies

For more details on this topic, see Categorical list of programming languages.

There is no overarching classification scheme for programming languages. A given programming language does not usually have a single ancestor language. Languages commonly arise by combining the elements of several predecessor languages with new ideas in circulation at the time. Ideas that originate in one language will diffuse throughout a family of related languages, and then leap suddenly across familial gaps to appear in an entirely different family.

The task is further complicated by the fact that languages can be classified along multiple axes. For example, Java is both an object-oriented language (because it encourages object-oriented organization) and a concurrent language (because it contains built-in constructs for running multiple threads in parallel). Python is an object-oriented scripting language.

In broad strokes, programming languages divide into programming paradigms and a classification by intended domain of use. Paradigms include procedural programming, object-oriented programming, functional programming, and logic programming; some languages are hybrids of paradigms or multi-paradigmatic. An assembly language is not so much a paradigm as a direct model of an underlying machine architecture. By purpose, programming languages might be considered general purpose, system programming languages, scripting languages, domain-specific languages, or concurrent/distributed languages (or a combination of these).[35] Some general purpose languages were designed largely with educational goals.[36]

A programming language may also be classified by factors unrelated to programming paradigm. For instance, most programming languages use English language keywords, while a minority do not. Other languages may be classified as being esoteric or not.

[edit] See also

Sister projectWikibooks has a book on the topic of

Look up programming language in Wiktionary, the free dictionary.

[edit] References

  1. ^ “HOPL: an interactive Roster of Programming Languages”. Australia: Murdoch University. http://hopl.murdoch.edu.au/. Retrieved on 2009-06-01. “This site lists 8512 languages.” 
  2. ^ ACM SIGPLAN (2003). “Bylaws of the Special Interest Group on Programming Languages of the Association for Computing Machinery”. http://www.acm.org/sigs/sigplan/sigplan_bylaws.htm. Retrieved on 2006-06-19. , The scope of SIGPLAN is the theory, design, implementation, description, and application of computer programming languages – languages that permit the specification of a variety of different computations, thereby providing the user with significant control (immediate or delayed) over the computer’s operation.
  3. ^ Dean, Tom (2002). “Programming Robots”. Building Intelligent Robots. Brown University Department of Computer Science. http://www.cs.brown.edu/people/tld/courses/cs148/02/programming.html. Retrieved on 2006-09-23. 
  4. ^ Digital Equipment Corporation. “Information Technology – Database Language SQL (Proposed revised text of DIS 9075)”. ISO/IEC 9075:1992, Database Language SQL. http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt. Retrieved on June 29 2006. 
  5. ^ The Charity Development Group (December 1996). “The CHARITY Home Page”. http://pll.cpsc.ucalgary.ca/charity1/www/home.html. Retrieved on 2006-06-29. , Charity is a categorical programming language…, All Charity computations terminate.
  6. ^ In mathematical terms, this means the programming language is Turing-complete MacLennan, Bruce J. (1987). Principles of Programming Languages. Oxford University Press. p. 1. ISBN 0-19-511306-3. 
  7. ^ Abelson, Sussman, and Sussman. “Structure and Interpretation of Computer Programs”. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html. Retrieved on 2009-03-03. 
  8. ^ IBM in first publishing PL/I, for example, rather ambitiously titled its manual The universal programming language PL/I (IBM Library; 1966). The title reflected IBM’s goals for unlimited subsetting capability: PL/I is designed in such a way that one can isolate subsets from it satisfying the requirements of particular applications. (“Encyclopaedia of Mathematics » P  » PL/I”. SpringerLink. http://eom.springer.de/P/p072885.htm. Retrieved on June 29 2006. ). Ada and UNCOL had similar early goals.
  9. ^ Frederick P. Brooks, Jr.: The Mythical Man-Month, Addison-Wesley, 1982, pp. 93-94
  10. ^ Dijkstra, Edsger W. On the foolishness of “natural language programming.” EWD667.
  11. ^ Perlis, Alan, Epigrams on Programming. SIGPLAN Notices Vol. 17, No. 9, September 1982, pp. 7-13
  12. ^ Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 2.2: Pushdown Automata, pp.101–114.
  13. ^ Aaby, Anthony (2004). Introduction to Programming Languages. http://web.archive.org/web/20040407162301/cs.wwc.edu/~aabyan/PLBook/HTML/index.html. 
  14. ^ a b c d e f g Andrew Cooke. “An Introduction to Programming Languages”. http://www.acooke.org/andrew/writing/lang.html#sec-types. Retrieved on June 30 2006. [dead link]
  15. ^ Specifically, instantiations of generic types are inferred for certain expression forms. Type inference in Generic Java—the research language that provided the basis for Java 1.5’s bounded parametric polymorphism extensions—is discussed in two informal manuscripts from the Types mailing list: Generic Java type inference is unsound (Alan Jeffrey, 17 December 2001) and Sound Generic Java type inference (Martin Odersky, 15 January 2002). C#’s type system is similar to Java’s, and uses a similar partial type inference scheme.
  16. ^ “Revised Report on the Algorithmic Language Scheme (February 20, 1998)”. http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-4.html. Retrieved on June 9 2006. 
  17. ^ Luca Cardelli and Peter Wegner. “On Understanding Types, Data Abstraction, and Polymorphism”. Manuscript (1985). http://citeseer.ist.psu.edu/cardelli85understanding.html. Retrieved on June 9 2006. 
  18. ^ Milner, R.; M. Tofte, R. Harper and D. MacQueen. (1997). The Definition of Standard ML (Revised). MIT Press. ISBN 0-262-63181-4. 
  19. ^ Kelsey, Richard; William Clinger and Jonathan Rees (February 1998). “Section 7.2 Formal semantics”. Revised5 Report on the Algorithmic Language Scheme. http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html#%_sec_7.2. Retrieved on 2006-06-09. 
  20. ^ ANSI — Programming Language Rexx, X3-274.1996
  21. ^ Benjamin C. Pierce writes:
    “… the lambda calculus has seen widespread use in the specification of programming language features, in language design and implementation, and in the study of type systems.”

    Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. p. 52. ISBN 0-262-16209-1. 

  22. ^ a b O’Reilly Media. “History of programming languages” (PDF). http://www.oreilly.com/news/graphics/prog_lang_poster.pdf. Retrieved on October 5 2006. 
  23. ^ Frank da Cruz. IBM Punch Cards Columbia University Computing History.
  24. ^ Richard L. Wexelblat: History of Programming Languages, Academic Press, 1981, chapter XIV.
  25. ^ François Labelle. “Programming Language Usage Graph”. Sourceforge. http://www.cs.berkeley.edu/~flab/languages.html. Retrieved on June 21 2006. . This comparison analyzes trends in number of projects hosted by a popular community programming repository. During most years of the comparison, C leads by a considerable margin; in 2006, Java overtakes C, but the combination of C/C++ still leads considerably.
  26. ^ Hayes, Brian (2006), “The Semicolon Wars”, American Scientist 94 (4): 299–303 
  27. ^ Dijkstra, Edsger W. (March 1968). “Go To Statement Considered Harmful“. Communications of the ACM 11 (3): 147–148. doi:10.1145/362929.362947. http://www.acm.org/classics/oct95/. Retrieved on 2006-06-29. 
  28. ^ Tetsuro Fujise, Takashi Chikayama Kazuaki Rokusawa, Akihiko Nakase (December 1994). “KLIC: A Portable Implementation of KL1” Proc. of FGCS ’94, ICOT Tokyo, December 1994. KLIC is a portable implementation of a concurrent logic programming language KL1.
  29. ^ Jim Bender (March 15, 2004). “Mini-Bibliography on Modules for Functional Programming Languages”. ReadScheme.org. http://readscheme.org/modules/. Retrieved on 2006-09-27. 
  30. ^ Wall, Programming Perl ISBN 0-596-00027-8 p.66
  31. ^ Survey of Job advertisements mentioning a given language
  32. ^ Counting programming languages by book sales
  33. ^ Bieman, J.M.; Murdock, V., Finding code on the World Wide Web: a preliminary investigation, Proceedings First IEEE International Workshop on Source Code Analysis and Manipulation, 2001
  34. ^ Programming Language Popularity
  35. ^ “TUNES: Programming Languages”. http://tunes.org/wiki/programming_20languages.html. 
  36. ^ Wirth, Niklaus (1993). “Recollections about the development of Pascal“. Proc. 2nd ACM SIGPLAN conference on history of programming languages: 333–342. doi:10.1145/154766.155378. http://portal.acm.org/citation.cfm?id=155378. Retrieved on 2006-06-30. 

[edit] Further reading

  • Daniel P. Friedman, Mitchell Wand, Christopher Thomas Haynes: Essentials of Programming Languages, The MIT Press 2001.
  • David Gelernter, Suresh Jagannathan: Programming Linguistics, The MIT Press 1990.
  • Shriram Krishnamurthi: Programming Languages: Application and Interpretation, online publication.
  • Bruce J. MacLennan: Principles of Programming Languages: Design, Evaluation, and Implementation, Oxford University Press 1999.
  • John C. Mitchell: Concepts in Programming Languages, Cambridge University Press 2002.
  • Benjamin C. Pierce: Types and Programming Languages, The MIT Press 2002.
  • Ravi Sethi: Programming Languages: Concepts and Constructs, 2nd ed., Addison-Wesley 1996.
  • Michael L. Scott: Programming Language Pragmatics, Morgan Kaufmann Publishers 2005.
  • Richard L. Wexelblat (ed.): History of Programming Languages, Academic Press 1981.

[edit] External links

[show]

v  d  e

Types of programming languages

 
[show]

v  d  e

Types of Computer languages

 

  

Read Full Post »

Human–computer interaction

From Wikipedia, the free encyclopedia

  (Redirected from Human-computer interaction)
Jump to: navigation, search

This article is about the interaction between users and computers. For the direct communication between brain cells and computers, please see Brain-computer interface.

This article’s external links may not follow Wikipedia’s content policies or guidelines. Please improve this article by removing excessive or inappropriate external links.

Human–computer interaction (HCI) is the study of interaction between people (users) and computers. It is often regarded as the intersection of computer science, behavioral sciences, design and several other fields of study. Interaction between users and computers occurs at the user interface (or simply interface), which includes both software and hardware, for example, general-purpose computer peripherals and large-scale mechanical systems, such as aircraft and power plants. The following definition is given by the Association for Computing Machinery[1]:

“Human-computer interaction is a discipline concerned with the design, evaluation and implementation of interactive computing systems for human use and with the study of major phenomena surrounding them.”

Because human-computer interaction studies a human and a machine in conjunction, it draws from supporting knowledge on both the machine and the human side. On the machine side, techniques in computer graphics, operating systems, programming languages, and development environments are relevant. On the human side, communication theory, graphic and industrial design disciplines, linguistics, social sciences, cognitive psychology, and human performance are relevant. Engineering and design methods are also relevant. Due to the multidisciplinary nature of HCI, people with different backgrounds contribute to its success. HCI is also sometimes referred to as man–machine interaction (MMI) or computer–human interaction (CHI).

Contents

[hide]

[edit] Goals

A basic goal of HCI is to improve the interactions between users and computers by making computers more usable and receptive to the user’s needs. Specifically, HCI is concerned with:

  • methodologies and processes for designing interfaces (i.e., given a task and a class of users, design the best possible interface within given constraints, optimizing for a desired property such as learning ability or efficiency of use)
  • methods for implementing interfaces (e.g. software toolkits and libraries; efficient algorithms)
  • techniques for evaluating and comparing interfaces
  • developing new interfaces and interaction techniques
  • developing descriptive and predictive models and theories of interaction

A long term goal of HCI is to design systems that minimize the barrier between the human’s cognitive model of what they want to accomplish and the computer’s understanding of the user’s task.

Professional practitioners in HCI are usually designers concerned with the practical application of design methodologies to real-world problems. Their work often revolves around designing graphical user interfaces and web interfaces.

Researchers in HCI are interested in developing new design methodologies, experimenting with new hardware devices, prototyping new software systems, exploring new paradigms for interaction, and developing models and theories of interaction.

[edit] Differences with related fields

HCI differs with human factors in that there is more of a focus on users working with computers rather than other kinds of machines or designed artifacts, and an additional focus on how to implement the (software and hardware) mechanisms behind computers to support human-computer interaction. It means that human factors is a broader term, and human factors of computers can be described as HCI – albeit some experts try to differ these areas.

About some experts’ opinion, HCI also differs with ergonomics in that there is less of a focus on repetitive work-oriented tasks and procedures, and much less emphasis on physical stress and the physical form or industrial design of physical aspects of the user interface, such as the physical form of keyboards and mice. However, it is caused by the lack of information about ergonomics. The oldest areas of ergonomics were the above mentioned, but nowadays (in the last decades), ergonomics have a much broader focus: ergonomics is equal to human factors. Cognitive ergonomics is a part of ergonomics, and the old-fashioned term software ergonomics signs a part of cognitive ergonomicssoftware ergonomics means HCI.

More discussion of the nuances between these fields is at [1]

Three areas of study have substantial overlap with HCI even as the focus of inquiry shifts. In the study of personal information management (PIM) human interactions with the computer are placed in a larger informational context – people may work with many forms of information, some computer-based, many not (e.g., white boards, notebooks, sticky notes, refrigerator magnets) in order to understand and effect desired changes in their world. In computer supported cooperative work (CSCW) emphasis is placed on the use of computing systems in support of the collaborative work of a group of people. The principles of human interaction management (HIM) extend the scope of CSCW to organizational level and can be implemented without use of computer systems.

[edit] Design principles

When evaluating a current user interface, or designing a new user interface, it is important to keep in mind the following experimental design principles:

  • Early focus on user(s) and task(s): Establish how many users are needed to perform the task(s) and determine who the appropriate users should be; someone that has never used the interface, and will not use the interface in the future, is most likely not a valid user. In addition, define the task(s) the users will be performing and how often the task(s) need to be performed.
  • Empirical measurement: Test the interface early on with real users who come in contact with the interface on an everyday basis, respectively. Keep in mind that results may be altered if the performance level of the user is not an accurate depiction of the real human-computer interaction. Establish quantitative usability specifics such as: the number of users performing the task(s), the time to complete the task(s), and the number of errors made during the task(s).
  • Iterative design: After determining the users, tasks, and empirical measurements to include, perform the following iterative design steps:
  1. Design the user interface
  2. Test
  3. Analyze results
  4. Repeat

Repeat the iterative design process until a sensible, user-friendly interface is created.[2]

[edit] Design methodologies

A number of diverse methodologies outlining techniques for human–computer interaction design have emerged since the rise of the field in the 1980s. Most design methodologies stem from a model for how users, designers, and technical systems interact. Early methodologies, for example, treated users’ cognitive processes as predictable and quantifiable and encouraged design practitioners to look to cognitive science results in areas such as memory and attention when designing user interfaces. Modern models tend to focus on a constant feedback and conversation between users, designers, and engineers and push for technical systems to be wrapped around the types of experiences users want to have, rather than wrapping user experience around a completed system.

  • User-centered design: user-centered design (UCD) is a modern, widely practiced design philosophy rooted in the idea that users must take center-stage in the design of any computer system. Users, designers and technical practitioners work together to articulate the wants, needs and limitations of the user and create a system that addresses these elements. Often, user-centered design projects are informed by ethnographic studies of the environments in which users will be interacting with the system. This practice is similar, but not identical to Participatory Design, which emphasizes the possibility for end-users to contribute actively through shared design sessions and workshops.
  • Principles of User Interface Design: these are seven principles that may be considered at any time during the design of a user interface in any order, namely Tolerance, Simplicity, Visibility, Affordance, Consistency, Structure and Feedback.[3]

[edit] Display design

Displays are human-made artifacts designed to support the perception of relevant system variables and to facilitate further processing of that information. Before a display is designed, the task that the display is intended to support must be defined (e.g. navigating, controlling, decision making, learning, entertaining, etc.). A user or operator must be able to process whatever information that a system generates and displays; therefore, the information must be displayed according to principles in a manner that will support perception, situation awareness, and understanding.

THIRTEEN PRINCIPLES OF DISPLAY DESIGN[4]

These principles of human perception and information processing can be utilized to create an effective display design. A reduction in errors, a reduction in required training time, an increase in efficiency, and an increase in user satisfaction are a few of the many potential benefits that can be achieved through utilization of these principles.

Certain principles may not be applicable to different displays or situations. Some principles may seem to be conflicting, and there is no simple solution to say that one principle is more important than another. The principles may be tailored to a specific design or situation. Striking a functional balance among the principles is critical for an effective design. [5]

Perceptual Principles

1. Make displays legible (or audible)

A display’s legibility is critical and necessary for designing a usable display. If the characters or objects being displayed cannot be discernible, then the operator cannot effectively make use of them.

2. Avoid absolute judgment limits

Do not ask the user to determine the level of a variable on the basis of a single sensory variable (e.g. color, size, loudness). These sensory variables can contain many possible levels.

3. Top-down processing

Signals are likely perceived and interpreted in accordance with what is expected based on a user’s past experience. If a signal is presented contrary to the user’s expectation, more physical evidence of that signal may need to be presented to assure that it is understood correctly.

4. Redundancy gain

If a signal is presented more than once, it is more likely that it will be understood correctly. This can be done by presenting the signal in alternative physical forms (e.g. color and shape, voice and print, etc.), as redundancy does not imply repetition. A traffic light is a good example of redundancy, as color and position are redundant.

5. Similarity causes confusion: Use discriminable elements

Signals that appear to be similar will likely be confused. The ratio of similar features to different features causes signals to be similar. For example, A423B9 is more similar to A423B8 than 92 is to 93. Unnecessary similar features should be removed and dissimilar features should be highlighted.

Mental Model Principles

6. Principle of pictorial realism

A display should look like the variable that it represents (e.g. high temperature on a thermometer shown as a higher vertical level). If there are multiple elements, they can be configured in a manner that looks like it would in the represented environment.

7. Principle of the moving part

Moving elements should move in a pattern and direction compatible with the user’s mental model of how it actually moves in the system. For example, the moving element on an altimeter should move upward with increasing altitude.

Principles Based on Attention

8. Minimizing information access cost

When the user’s attention is averted from one location to another to access necessary information, there is an associated cost in time or effort. A display design should minimize this cost by allowing for frequently accessed sources to be located at the nearest possible position. However, adequate legibility should not be sacrificed to reduce this cost.

9. Proximity compatibility principle

Divided attention between two information sources may be necessary for the completion of one task. These sources must be mentally integrated and are defined to have close mental proximity. Information access costs should be low, which can be achieved in many ways (e.g. close proximity, linkage by common colors, patterns, shapes, etc.). However, close display proximity can be harmful by causing too much clutter.

10. Principle of multiple resources

A user can more easily process information across different resources. For example, visual and auditory information can be presented simultaneously rather than presenting all visual or all auditory information.

Memory Principles

11. Replace memory with visual information: knowledge in the world

A user should not need to retain important information solely in working memory or to retrieve it from long-term memory. A menu, checklist, or another display can aid the user by easing the use of their memory. However, the use of memory may sometimes benefit the user rather than the need for reference to some type of knowledge in the world (e.g. a expert computer operator would rather use direct commands from their memory rather than referring to a manual). The use of knowledge in a user’s head and knowledge in the world must be balanced for an effective design.

12. Principle of predictive aiding

Proactive actions are usually more effective than reactive actions. A display should attempt to eliminate resource-demanding cognitive tasks and replace them with simpler perceptual tasks to reduce the use of the user’s mental resources. This will allow the user to not only focus on current conditions, but also think about possible future conditions. An example of a predictive aid is a road sign displaying the distance from a certain destination.

13. Principle of consistency

Old habits from other displays will easily transfer to support processing of new displays if they are designed in a consistent manner. A user’s long-term memory will trigger actions that are expected to be appropriate. A design must accept this fact and utilize consistency among different displays.

[edit] Future developments

The means by which humans interact with computers continues to evolve rapidly. Human–computer interaction is affected by the forces shaping the nature of future computing. These forces include:

  • Decreasing hardware costs leading to larger memories and faster systems
  • Miniaturization of hardware leading to portability
  • Reduction in power requirements leading to portability
  • New display technologies leading to the packaging of computational devices in new forms
  • Specialized hardware leading to new functions
  • Increased development of network communication and distributed computing
  • Increasingly widespread use of computers, especially by people who are outside of the computing profession
  • Increasing innovation in input techniques (i.e., voice, gesture, pen), combined with lowering cost, leading to rapid computerization by people previously left out of the “computer revolution.”
  • Wider social concerns leading to improved access to computers by currently disadvantaged groups

The future for HCI is expected to include the following characteristics:

Ubiquitous communication Computers will communicate through high speed local networks, nationally over wide-area networks, and portably via infrared, ultrasonic, cellular, and other technologies. Data and computational services will be portably accessible from many if not most locations to which a user travels.

High functionality systems Systems will have large numbers of functions associated with them. There will be so many systems that most users, technical or non-technical, will not have time to learn them in the traditional way (e.g., through thick manuals).

Mass availability of computer graphics Computer graphics capabilities such as image processing, graphics transformations, rendering, and interactive animation will become widespread as inexpensive chips become available for inclusion in general workstations.

Mixed media Systems will handle images, voice, sounds, video, text, formatted data. These will be exchangeable over communication links among users. The separate worlds of consumer electronics (e.g., stereo sets, VCRs, televisions) and computers will partially merge. Computer and print worlds will continue to cross assimilate each other.

High-bandwidth interaction The rate at which humans and machines interact will increase substantially due to the changes in speed, computer graphics, new media, and new input/output devices. This will lead to some qualitatively different interfaces, such as virtual reality or computational video.

Large and thin displays New display technologies will finally mature enabling very large displays and also displays that are thin, light weight, and have low power consumption. This will have large effects on portability and will enable the development of paper-like, pen-based computer interaction systems very different in feel from desktop workstations of the present.

Embedded computation Computation will pass beyond desktop computers into every object for which uses can be found. The environment will be alive with little computations from computerized cooking appliances to lighting and plumbing fixtures to window blinds to automobile braking systems to greeting cards. To some extent, this development is already taking place. The difference in the future is the addition of networked communications that will allow many of these embedded computations to coordinate with each other and with the user. Human interfaces to these embedded devices will in many cases be very different from those appropriate to workstations.

Augmented reality A common staple of science fiction, augmented reality refers to the notion of layering relevant information into our vision of the world. Existing projects show real-time statistics to users performing difficult tasks, such as manufacturing. Future work might include augmenting our social interactions by providing additional information about those we converse with.

Group interfaces Interfaces to allow groups of people to coordinate will be common (e.g., for meetings, for engineering projects, for authoring joint documents). These will have major impacts on the nature of organizations and on the division of labor. Models of the group design process will be embedded in systems and will cause increased rationalization of design.

User Tailorability Ordinary users will routinely tailor applications to their own use and will use this power to invent new applications based on their understanding of their own domains. Users, with their deeper knowledge of their own knowledge domains, will increasingly be important sources of new applications at the expense of generic systems programmers (with systems expertise but low domain expertise).

Information Utilities Public information utilities (such as home banking and shopping) and specialized industry services (e.g., weather for pilots) will continue to proliferate. The rate of proliferation will accelerate with the introduction of high-bandwidth interaction and the improvement in quality of interfaces.

[edit] Human–computer interface

The human–computer interface can be described as the point of communication between the human user and the computer. The flow of information between the human and computer is defined as the loop of interaction. The loop of interaction has several aspects to it including:

  • Task Environment: The conditions and goals set upon the user.
  • Machine Environment: The environment that the computer is connected to, i.e a laptop in a college student’s dorm room.
  • Areas of the Interface: Non-overlapping areas involve processes of the human and computer not pertaining to their interaction. Meanwhile, the overlapping areas only concern themselves with the processes pertaining to their interaction.
  • Input Flow: Begins in the task environment as the user has some task that requires using their computer.
  • Output: The flow of information that originates in the machine environment.
  • Feedback: Loops through the interface that evaluate, moderate, and confirm processes as they pass from the human through the interface to the computer and back.

[edit] Academic conferences

One of the top academic conferences for new research in human-computer interaction, especially within computer science, is the annually held ACM‘s Conference on Human Factors in Computing Systems, usually referred to by its short name CHI (pronounced kai, or khai). CHI is organized by ACM SIGCHI Special Interest Group on Computer–Human Interaction. CHI is a large, highly competitive conference, with thousands of attendants, and is quite broad in scope.

There are also dozens of other smaller, regional or specialized HCI-related conferences held around the world each year, the most important of which include (see also [2]):

[edit] Special purpose

  • UIST: ACM Symposium on User Interface Software and Technology.
  • CSCW: ACM conference on Computer Supported Cooperative Work.
  • ECSCW: European Conference on Computer-Supported Cooperative Work. Alternates yearly with CSCW.
  • ICMI: International Conference on Multimodal Interfaces.
  • MobileHCI: International Conference on Human-Computer Interaction with Mobile Devices and Services.
  • DIS: ACM conference on Designing Interactive Systems.
  • NIME: International Conference on New Interfaces for Musical Expression.
  • HRI: ACM/IEEE International Conference on Human-robot interaction.
  • IUI: International Conference on Intelligent User Interfaces.
  • Ubicomp: International Conference on Ubiquitous computing
  • ASSETS: ACM International Conference on Computers and Accessibility

[edit] Regional and general HCI

  • INTERACT: IFIP TC13 International Conference on Human-Computer Interaction. Biennial, alternating years with AVI.
  • AVI: International Working Conference on Advanced Visual Interfaces. Held biennially in Italy, alternating years with INTERACT.
  • HCI International: International Conference on Human-Computer Interaction.
  • ACHI: International Conferences on Advances in Human-Computer Interaction.
  • HCI: British HCI Conference.
  • OZCHI: Australasian HCI Conference.
  • IHM: Annual French-speaking HCI Conference.
  • Graphics Interface: Annual Canadian computer graphics and HCI conference. The oldest regularly scheduled conference for graphics and human-computer interaction.
  • NordiCHI: Nordic Conference on Human-Computer Interaction. Biennial.

[edit] See also

[edit] Footnotes

This article includes a list of references or external links, but its sources remain unclear because it has insufficient inline citations. Please help to improve this article by introducing more precise citations where appropriate. (April 2009)

  1. ^ ACM SIGCHI Curricula for Human-Computer Interaction
  2. ^ Green, Paul (2008). Iterative Design. Lecture presented in Industrial and Operations Engineering 436 (Human Factors in Computer Systems, University of Michigan, Ann Arbor, MI, February 4, 2008.
  3. ^ Pattern Language
  4. ^ Wickens, Christopher D., John D. Lee, Yili Liu, and Sallie E. Gordon Becker. An Introduction to Human Factors Engineering. Second ed. Upper Saddle River, NJ: Pearson Prentice Hall, 2004. 185–193.
  5. ^ Brown, C. Marlin. Human-Computer Interface Design Guidelines. Intellect Books, 1998. 2–3.

[edit] Further reading

[edit] External links

Read Full Post »

Mathematical proof

Mathematical proof

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In mathematics, a proof is a convincing demonstration (within the accepted standards of the field) that some mathematical statement is necessarily true[1]. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single exception. An unproved proposition that is believed to be true is known as a conjecture.

The statement that is proved is often called a theorem[1]. Once a theorem is proved, it can be used as the basis to prove further statements. A theorem may also be referred to as a lemma, especially if it is intended for use as a stepping stone in the proof of another theorem.

Proofs employ logic but usually include some amount of natural language which usually admits some ambiguity. In fact, the vast majority of proofs in written mathematics can be considered as applications of rigorous informal logic. Purely formal proofs, written in symbolic language instead of natural language, are considered in proof theory. The distinction between formal and informal proofs has led to much examination of current and historical mathematical practice, quasi-empiricism in mathematics, and so-called folk mathematics (in both senses of that term). The philosophy of mathematics is concerned with the role of language and logic in proofs, and mathematics as a language.

Contents

[hide]

[edit] History and etymology

For more details on this topic, see History of logic.

Plausibility arguments using heuristic devices such as pictures and analogies preceded strict mathematical proof..[2] The early history of the concept of proof dates back to the early Greek and Chinese civilisations. Thales (624–546 BCE) proved some theorems in geometry. Eudoxus (408–355 BCE) and Theaetetus (417–369 BCE) formulated theorems but did not prove them. Aristotle (384–322 BCE) said definitions should describe the concept being defined in terms of other concepts already known. Euclid (300 BCE) began with undefined terms and axioms (propositions regarding the undefined terms assumed to be self-evidently true, from the Greek “axios” meaning “something worthy”) and used these to prove theorems using deductive logic. Modern proof theory treats proofs as inductively defined data structures. There is no longer an assumption that axioms are “true” in any sense; this allows for parallel mathematical theories built on alternate sets of axioms (see Axiomatic set theory and Non-Euclidean geometry for examples).

The word Proof comes from the Latin probare meaning “to test”. Related modern words are the English “probe”, “proboscis”, “probation”, and “probability”, and the Spanish “probar” (to smell or taste, or (lesser use) touch or test). The early use of “probity” was in the presentation of legal evidence. A person of authority, such as a nobleman, was said to have probity, whereby the evidence was by his relative authority, which outweighed empirical testimony.[3]

[edit] Nature and purpose

There are two different conceptions of mathematical proof.[4] The first is an informal proof, a rigorous natural-language expression that is intended to convince the audience of the truth of a theorem. Because of their use of natural language, the standards of rigor for informal proofs will depend on the audience of the proof. In order to be considered a proof, however, the argument must be rigorous enough; a vague or incomplete argument is not a proof. Informal proofs are the type of proof typically encountered in published mathematics. They are sometimes called “formal proofs” because of their rigor, but logicians use the term “formal proof” to refer to a different type of proof entirely.

In logic, a formal proof is not written in a natural language, but instead uses a formal language consisting of certain strings of symbols from a fixed alphabet. This allows the definition of a formal proof to be precisely specified without any ambiguity. The field of proof theory studies formal proofs and their properties. Although each informal proof can, in theory, be converted into a formal proof, this is rarely done in practice. The study of formal proofs is used to determine properties of provability in general, and to show that certain undecidable statements are not provable.

A classic question in philosophy asks whether mathematical proofs are analytic or synthetic. Kant, who introduced the analytic-synthetic distinction, believed mathematical proofs are synthetic.

Proofs may be viewed as aesthetic objects, admired for their mathematical beauty. The mathematician Paul Erdős was known for describing proofs he found particularly elegant as coming from “The Book”, a hypothetical tome containing the most beautiful method(s) of proving each theorem. The book Proofs from THE BOOK, published in 2003, is devoted to presenting 32 proofs its editors find particularly pleasing.

[edit] Methods of proof

[edit] Direct proof

Main article: Direct proof

In direct proof[5], the conclusion is established by logically combining the axioms, definitions, and earlier theorems. For example, direct proof can be used to establish that the sum of two even integers is always even:

For any two even integers x and y we can write x = 2a and y = 2b for some integers a and b, since both x and y are multiples of 2. But the sum x + y = 2a + 2b = 2(a + b) is also a multiple of 2, so it is therefore even by definition.

This proof uses definition of even integers, as well as distribution law.

[edit] Proof by mathematical induction

In proof by mathematical induction[6], first a “base case” is proved, and then an “induction rule” is used to prove a (often infinite) series of other cases. Since the base case is true, the infinity of other cases must also be true, even if all of them cannot be proved directly because of their infinite number. A subset of induction is infinite descent. Infinite descent can be used to prove the irrationality of the square root of two.

The principle of mathematical induction states that: Let N = { 1, 2, 3, 4, … } be the set of natural numbers and P(n) be a mathematical statement involving the natural number n belonging to N such that

  • (i) P(1) is true, i.e., P(n) is true for n = 1
  • (ii) P(n + 1) is true whenever P(n) is true, i.e., P(n) is true implies that P(n + 1) is true.

Then P(n) is true for all natural numbers n.

Mathematicians often use the term “proof by induction” as shorthand for a proof by mathematical induction.[7] However, the term “proof by induction” may also be used in logic to mean an argument that uses inductive reasoning.

[edit] Proof by transposition

Main article: Transposition (logic)

Proof by transposition establishes the conclusion “if p then q” by proving the equivalent contrapositive statement “if not q then not p“.

[edit] Proof by contradiction

In proof by contradiction (also known as reductio ad absurdum, Latin for “by reduction toward the absurd”), it is shown that if some statement were so, a logical contradiction occurs, hence the statement must be not so. This method is perhaps the most prevalent of mathematical proofs. A famous example of a proof by contradiction shows that \sqrt{2} is an Irrational number:

Suppose that \sqrt{2} is a rational number, so \sqrt{2} = {a\over b} where a and b are non-zero integers with no common factor (definition of a rational number). Thus, b\sqrt{2} = a. Squaring both sides yields 2b2 = a2. Since 2 divides the left hand side, 2 must also divide the right hand side (as they are equal and both integers). So a2 is even, which implies that a must also be even. So we can write a = 2c, where c is also an integer. Substitution into the original equation yields 2b2 = (2c)2 = 4c2. Dividing both sides by 2 yields b2 = 2c2. But then, by the same argument as before, 2 divides b2, so b must be even. However, if a and b are both even, they share a factor, namely 2. This contradicts our assumption, so we are forced to conclude that \sqrt{2} is an irrational number.

[edit] Proof by construction

Main article: Proof by construction

Proof by construction, or proof by example, is the construction of a concrete example with a property to show that something having that property exists. Joseph Liouville, for instance, proved the existence of transcendental numbers by constructing an explicit example.

[edit] Proof by exhaustion

Main article: Proof by exhaustion

In proof by exhaustion, the conclusion is established by dividing it into a finite number of cases and proving each one separately. The number of cases sometimes can become very large. For example, the first proof of the four colour theorem was a proof by exhaustion with 1,936 cases. This proof was controversial because the majority of the cases were checked by a computer program, not by hand. The shortest known proof of the four colour theorem today still has over 600 cases.

[edit] Probabilistic proof

Main article: Probabilistic method

A probabilistic proof is one in which an example is shown to exist, with certainty, by using methods of probability theory. This is not to be confused with an argument that a theorem is ‘probably’ true. The latter type of reasoning can be called a ‘plausibility argument’ and is not a proof; in the case of the Collatz conjecture it is clear how far that is from a genuine proof.[8] Probabilistic proof, like proof by construction, is one of many ways to show existence theorems.

[edit] Combinatorial proof

Main article: Combinatorial proof

A combinatorial proof establishes the equivalence of different expressions by showing that they count the same object in different ways. Often a bijection between two sets is used to show that the expressions for their two sizes are equal. Alternatively, a double counting argument provides two different expressions for the size of a single set, again showing that the two expressions are equal.

[edit] Nonconstructive proof

Main article: Nonconstructive proof

A nonconstructive proof establishes that a certain mathematical object must exist (e.g. “Some X satisfies f(X)”), without explaining how such an object can be found. Often, this takes the form of a proof by contradiction in which the nonexistence of the object is proven to be impossible. In contrast, a constructive proof establishes that a particular object exists by providing a method of finding it. A famous example of a nonconstructive proof shows that there exist two irrational numbers a and b such that ab is a rational number:

Either \sqrt{2}^{\sqrt{2}} is a rational number and we are done (take a=b=\sqrt{2}), or \sqrt{2}^{\sqrt{2}} is irrational so we can write a=\sqrt{2}^{\sqrt{2}} and b=\sqrt{2}. This then gives \left (\sqrt{2}^{\sqrt{2}}\right )^{\sqrt{2}}=\sqrt{2}^{2}=2, which is thus a rational of the form ab.

[edit] Visual proof

Visual proof for the (3, 4, 5) triangle as in the Chou Pei Suan Ching 500–200 BC.

Although not a formal proof, a visual demonstration of a mathematical theorem is sometimes called a “proof without words“. The picture at right is an example of a historic visual proof of the Pythagorean theorem in the case of the (3,4,5) triangle.

[edit] Elementary proof

Main article: Elementary proof

An elementary proof is a proof which only uses basic techniques. More specifically, the term is used in number theory to refer to proofs that make no use of complex analysis. For some time it was thought that certain theorems, like the prime number theorem, could only be proved using “higher” mathematics. However, over time, many of these results have been reproved using only elementary techniques.

[edit] Two-column proof

A two-column proof published in 1913

A particular form of proof using two parallel columns is often used in elementary geometry classes.[9] The proof is written as a series of lines in two columns. In each line, the left hand column contains propositions (or sometimes called statements), while the right hand column contains a brief explanation of how this proposition is either an axiom, a hypothesis, or can be obtained from previous lines (or sometimes just called “reasons”).

[edit] Statistical proofs in pure mathematics

Main article: Statistical proof

The expression “statistical proof” may be used technically or colloquially in areas of pure mathematics, such as involving cryptography, chaotic series, and probabilistic or analytic number theory.[10][11][12] It is less commonly used to refer to a mathematical proof in the branch of mathematics known as mathematical statistics. See also “Statistical proof using data” section below.[4].

[edit] Computer-assisted proofs

Until the twentieth century it was assumed that any proof could, in principle, be checked by a competent mathematician to confirm its validity.[2] However, computers are now used both to prove theorems and to carry out calculations that are too long for any human or team of humans to check; the first proof of the four color theorem is an example of a computer-assisted proof. Some mathematicians are concerned that the possibility of an error in a computer program or a run-time error in its calculations calls the validity of such computer-assisted proofs into question. In practice, the chances of an error invalidating a computer-assisted proof can be reduced by incorporating redundancy and self-checks into calculations, and by developing multiple independent approaches and programs.

[edit] Undecidable statements

A statement that is neither provable nor disprovable from a set of axioms is called undecidable (from those axioms). One example is the parallel postulate, which is neither provable nor refutable from the remaining axioms of Euclidean geometry.

Mathematicians have shown there are many statements that are neither provable nor disprovable in Zermelo-Fraenkel set theory with the axiom of choice (ZFC), the standard system of set theory in mathematics (assuming that ZFC is consistent); see list of statements undecidable in ZFC.

Gödel’s (first) incompleteness theorem shows that many axiom systems of mathematical interest will have undecidable statements.

[edit] Heuristic mathematics and experimental mathematics

While early mathematicians such as Eudoxus of Cnidus did not use proofs, from Euclid to the foundational mathematics developments of the late 19th and 20th centuries, proofs were an essential part of mathematics.[13] With the increase in computing power in the 1960’s, significant work began to be done investigating mathematical objects outside of the proof-theorem framework,[14] in experimental mathematics. Early pioneers of these methods intended the work ultimately to be embedded in a classical proof-theorem framework, e.g. the early development of fractal geometry[15], which was ultimately so embedded.

[edit] Related concepts

[edit] Colloquial use of “mathematical proof”

The expression “mathematical proof” is used by lay people to refer to using mathematical methods or arguing with mathematical objects, such as numbers, to demonstrate something about everyday life, or when data used in an argument are numbers. It is sometime also used to mean a “statistical proof” (below), especially when used to argue from data.

[edit] Statistical proof using data

Main article: Statistical proof

“Statistical proof” from data refers to the application of statistics, data analysis, or Bayesian analysis to infer propositions regarding the probability of data. While using mathematical proof to establish theorems in statistics, it is usually not a mathematical proof in that the assumpions from which probability statements are derived require empirical evidence from outside mathematics to verify. In physics, in addition to statistical methods, “statistical proof” can refer to the specialized mathematical methods of physics applied to analyze data in a particle physics experiment or observational study in cosmology. “Statistical proof” may also refer to raw data or a convincing diagram involving data, such as scatter plots, when the data or diagram is adequately convincing without further anaylisis.

[edit] Inductive logic proofs and Bayesian analysis

Main articles: Inductive logic and Bayesian analysis

Proofs using inductive logic, while considered mathematical in nature, seek to establish propositions with a degree of certainty, which acts in a similar manner to probability, and may be less than one certainty. Bayesian analysis establishes assertions as to the degree of a person’s subjective belief. Inductive logic should not be confused with mathematical induction.

[edit] Proofs as mental objects

Psychologism views mathematical proofs as psychological or mental objects. Mathematician philosophers, such as Leibnitz, Frege, and Carnap, have attempted to develop a semantics for what they considered to be the language of thought, whereby standards of mathematical proof might be applied to empirical science.

[edit] Influence of mathematical proof methods outside mathematics

Philosopher-mathematicians such as Schopenhauer have attempted to formulate philosophical arguments in an axiomatic manner, whereby mathematical proof standards could be applied to argumentation in general philosophy. Other mathematician-philosophers have tried to use standards of mathematical proof and reason, without empiricism, to arrive at statements outside of mathematics, but having the certainty of propositions deduced in a mathematical proof, such as Descarte’s cogito argument. Kant and Frege considered mathematical proof to be analytic apriori.

[edit] Ending a proof

Main article: Q.E.D.

Sometimes, the abbreviation “Q.E.D.” is written to indicate the end of a proof. This abbreviation stands for “Quod Erat Demonstrandum”, which is Latin for “that which was to be demonstrated”. A more common alternative is to use a square or a rectangle, such as or , known as a “tombstone” or “halmos”. Often, “which was to be shown” is verbally stated when writing “QED”, ““, or “” in an oral presentation on a board.

[edit] See also

[edit] References

  1. ^ a b Cupillari, Antonella. The Nuts and Bolts of Proofs. Academic Press, 2001. Page 3.
  2. ^ a b The History and Concept of Mathematical Proof, Steven G. Krantz. 1. February 5, 2007
  3. ^ The Emergence of Probability, Ian Hacking
  4. ^ Buss, 1997, p. 3
  5. ^ Cupillari, page 20.
  6. ^ Cupillari, page 46.
  7. ^ Proof by induction, University of Warwick Glossary of Mathematical Terminology
  8. ^ While most mathematicians do not think that probabilistic evidence ever counts as a genuine mathematical proof, a few mathematicians and philosophers have argued that at least some types of probabilistic evidence (such as Rabin’s probabilistic algorithm for testing primality) are as good as genuine mathematical proofs. See, for example, Davis, Philip J. (1972), “Fidelity in Mathematical Discourse: Is One and One Really Two?” American Mathematical Monthly 79:252-63. Fallis, Don (1997), “The Epistemic Status of Probabilistic Proof.” Journal of Philosophy 94:165-86.
  9. ^ Patricio G. Herbst, Establishing a Custom of Proving in American School Geometry: Evolution of the Two-Column Proof in the Early Twentieth Century, Educational Studies in Mathematics, Vol. 49, No. 3 (2002), pp. 283-312,
  10. ^ “in number theory and commutative algebra… in particular the statistical proof of the lemma.” [1]
  11. ^ “Whether constant π (i.e., pi) is normal is a confusing problem without any strict theoretical demonstration except for some statistical proof”” (Derogatory use.)[2]
  12. ^ “these observations suggest a statistical proof of Goldbach’s conjecture with very quickly vanishing probability of failure for large E” [3]
  13. ^What to do with the pictures? Two thoughts surfaced: the first was that they were unpublishable in the standard way, there were no theorems only very suggestive pictures. They furnished convincing evidence for many conjectures and lures to further exploration, but theorems were coins of the realm ant the conventions of that day dictated that journals only published theorems“, David Mumford, Caroline Series and David Wright, Indra’s Pearls, 2002
  14. ^Mandelbrot, working at the IBM Research Laboratory, did some computer simulations for these sets on the reasonable assumption that, if you wanted to prove something, it might be helpful to know the answer ahead of time.A Note on the History of Fractals,
  15. ^… brought home again to Benoit [Mandelbrot] that there was a ‘mathematics of the eye’, that visualization of a problem was as valid a method as any for finding a solution. Amazingly, he found himself alone with this conjecture. The teaching of mathematics in France was dominated by a handful of dogmatic mathematicians hiding behind the pseudonym ‘Bourabki’… “, Introducing Fractal Geometry, Nigel Lesmoir-Gordon

[edit] Sources

[edit] External links

[show]

v  d  e

Logic

Portal ·Category ·WikiProject ·Logic stubs ·Mathlogic stubs ·Cleanup ·Talk ·changes
 
[show]

 

History and core topics

 
History
 
Core topics
 
[show]

 

Key concepts and logics

 
Reasoning
 
Informal
 
Philosophy
of logic
 
Mathematical
 
Propositional
 
Predicate
 
Modal
 
Other non
classical
 
[show]

 

Controversies

 
 
[show]

 

Key figures

 
Alfarabi · Algazel · Alkindus · Al-Razi · Aristotle · Averroes · Avicenna · Boole · Cantor · Carnap · Church · Dharmakirti · Dignāga · Frege · Gentzen · Kanada · Gödel · Gotama · Hilbert · Ibn al-Nafis · Ibn Hazm · Ibn Taymiyyah · Kripke · Leibniz · Mozi · Nagarjuna · Pāṇini · Peano · Peirce · Putnam · Quine · Russell · Skolem · Suhrawardi · Tarski · Turing · Whitehead · Zadeh
 
[show]

 

Lists

 
Topics
Outline of logic · General · Basic · Mathematical logic · Boolean algebra · Set theory
 
Other
 

  

Read Full Post »

Mathematical logic

Mathematical logic

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Mathematical logic is a subfield of mathematics with close connections to computer science and philosophical logic.[1] The field includes the mathematical study of logic and the applications of formal logic to other areas of mathematics. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems.

Mathematical logic is often divided into the subfields of set theory, model theory, recursion theory, and proof theory and constructive mathematics. These areas share basic results on logic, particularly first-order logic, and definability.

Since its inception, mathematical logic has contributed to, and has been motivated by, the study of foundations of mathematics. This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and analysis. In the early 20th century it was shaped by David Hilbert‘s program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in proving consistency. Work in set theory showed that almost all ordinary mathematics can be formalized in terms of sets, although there are some theorems that cannot be proven in common axiom systems for set theory. Contemporary work in the foundations of mathematics often focuses on establishing which parts of mathematics can be formalized in particular formal systems, rather than trying to find theories in which all of mathematics can be developed.

Contents

[hide]

[edit] History

Mathematical logic emerged in the mid-19th century as a subfield of mathematics independent of the traditional study of logic (Ferreirós 2001, p. 443). Before this emergence, logic was studied with rhetoric, through the syllogism, and with philosophy. The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics.

[edit] Early history

Further information: History of logic

Sophisticated theories of logic were developed in many cultures, including China, India, Greece and the Islamic world. In the 18th century, attempts to treat the operations of formal logic in a symbolic or algebraic way had been made by philosophical mathematicians including Leibniz and Lambert, but their labors remained isolated and little known.

[edit] 19th century

In the middle of the nineteenth century, George Boole and then Augustus De Morgan presented systematic mathematical treatments of logic. Their work, building on work by algebraists such as George Peacock, extended the traditional Aristotelian doctrine of logic into a sufficient framework for the study of foundations of mathematics (Katz 1998, p. 686).

Charles Sanders Peirce built upon the work of Boole to develop a logical system for relations and quantifiers, which he published in several papers from 1870 to 1885. Gottlob Frege presented an independent development of logic with quantifiers in his Begriffsschrift, published in 1879. Frege’s work remained obscure, however, until Bertrand Russell began to promote it near the turn of the century. The two-dimensional notation Frege developed was never widely adopted and is unused in contemporary texts.

From 1890 to 1905, Ernst Schröder published Vorlesungen über die Algebra der Logik in three volumes. This work summarized and extended the work of Boole, De Morgan, and Peirce, and was a comprehensive reference to symbolic logic as it was understood at the end of the 19th century.

[edit] Foundational theories

Some concerns that mathematics had not been built on a proper foundation led to the development of axiomatic systems for fundamental areas of mathematics such as arithmetic, analysis, and geometry.

In logic, the term arithmetic refers to the theory of the natural numbers. Giuseppe Peano (1888) published a set of axioms for arithmetic that came to bear his name, using a variation of the logical system of Boole and Schröder but adding quantifiers. Peano was unaware of Frege’s work at the time. Around the same time Richard Dedekind showed that the natural numbers are uniquely characterized by their induction properties. Dedekind (1888) proposed a different characterization, which lacked the formal logical character of Peano’s axioms. Dedekind’s work, however, proved theorems inaccessible in Peano’s system, including the uniqueness of the set of natural numbers (up to isomorphism) and the recursive definitions of addition and multiplication from the successor function and mathematical induction.

In the mid-19th century, flaws in Euclid’s axioms for geometry became known (Katz 1998, p. 774). In addition to the independence of the parallel postulate, established by Nikolai Lobachevsky in 1826 (Lobachevsky 1840), mathematicians discovered that certain theorems taken for granted by Euclid were not in fact provable from his axioms. Among these is the theorem that a line contains at least two points, or that circles of the same radius whose centers are separated by that radius must intersect. Hilbert (1899) developed a complete set of axioms for geometry, building on previous work by Pasch (1882). The success in axiomatizing geometry motivated Hilbert to seek complete axiomatizations of other areas of mathematics, such as the natural numbers and the real line. This would prove to be a major area of research in the first half of the 20th century.

The 19th century saw great advances in the theory of real analysis, including theories of convergence of functions and Fourier series. Mathematicians such as Karl Weierstrass began to construct functions that stretched intuition, such as nowhere-differentiable continuous functions. Previous conceptions of a function as a rule for computation, or a smooth graph, were no longer adequate. Weierstrass began to advocate the arithmetization of analysis, which sought to axiomatize analysis using properties of the natural numbers. The modern “ε-δ” definition of limits and continuous functions was developed by Bolzano and Cauchy between 1817 and 1823 (Felscher 2000). In 1858, Dedekind proposed a definition of the real numbers in terms of Dedekind cuts of rational numbers (Dedekind 1872), a definition still employed in contemporary texts.

Georg Cantor developed the fundamental concepts of infinite set theory. His early results developed the theory of cardinality and proved that the reals and the natural numbers have different cardinalities (Cantor 1874). Over the next twenty years, Cantor developed a theory of transfinite numbers in a series of publications. In 1891, he published a new proof of the uncountability of the real numbers that introduced the diagonal argument, and used this method to prove Cantor’s theorem that no set can have the same cardinality as its powerset. Cantor believed that every set could be well-ordered, but was unable to produce a proof for this result, leaving it as an open problem in 1895 (Katz 1998, p. 807).

[edit] 20th century

In the early decades of the 20th century, the main areas of study were set theory and formal logic. The discovery of paradoxes in informal set theory caused some to wonder whether mathematics itself is inconsistent, and to look for proofs of consistency.

In 1900, Hilbert posed a famous list of 23 problems for the next century. The first two of these were to resolve the continuum hypothesis and prove the consistency of elementary arithmetic, respectively; the tenth was to produce a method that could decide whether a multivariate polynomial equation over the integers has a solution. Subsequent work to resolve these problems shaped the direction of mathematical logic, as did the effort to resolve Hilbert’s Entscheidungsproblem, posed in 1928. This problem asked for a procedure that would decide, given a formalized mathematical statement, whether the statement is true or false.

[edit] Set theory and paradoxes

Ernst Zermelo (1904) gave a proof that every set could be well-ordered, a result Georg Cantor had been unable to obtain. To achieve the proof, Zermelo introduced the axiom of choice, which drew heated debate and research among mathematicians and the pioneers of set theory. The immediate criticism of the method led Zermelo to publish a second exposition of his result, directly addressing criticisms of his proof (Zermelo 1908). This paper led to the general acceptance of the axiom of choice in the mathematics community.

Skepticism about the axiom of choice was reinforced by recently discovered paradoxes in naive set theory. Cesare Burali-Forti (1897) was the first to state a paradox: the Burali-Forti paradox shows that the collection of all ordinal numbers cannot form a set. Very soon thereafter, Bertrand Russell discovered Russell’s paradox in 1901, and Jules Richard (1905) discovered Richard’s paradox.

Zermelo (1908) provided the first set of axioms for set theory. These axioms, together with the additional axiom of replacement proposed by Abraham Fraenkel, are now called Zermelo–Fraenkel set theory (ZF). Zermelo’s axioms incorporated the principle of limitation of size to avoid Russell’s paradox.

In 1910, the first volume of Principia Mathematica by Russell and Alfred North Whitehead was published. This seminal work developed the theory of functions and cardinality in a completely formal framework of type theory, which Russell and Whitehead developed in an effort to avoid the paradoxes. Principia Mathematica is considered one of the most influential works of the 20th century, although the framework of type theory did not prove popular as a foundational theory for mathematics (Ferreirós 2001, p. 445).

Fraenkel (1922) proved that the axiom of choice cannot be proved from the remaining axioms of Zermelo’s set theory with urelements. Later work by Paul Cohen (1966) showed that the addition of urelements is not needed, and the axiom of choice is unprovable in ZF. Cohen’s proof developed the method of forcing, which is now an important tool for establishing independence results in set theory.

[edit] Symbolic logic

Leopold Löwenheim (1918) and Thoralf Skolem (1919) obtained the Löwenheim–Skolem theorem, which says that first-order logic cannot control the cardinalities of infinite structures. Skolem realized that this theorem would apply to first-order formalizations of set theory, and that it implies any such formalization has a countable model. This counterintuitive fact became known as Skolem’s paradox.

In his doctoral thesis, Kurt Gödel (1929) proved the completeness theorem, which establishes a correspondence between syntax and semantics in first-order logic. Gödel used the completeness theorem to prove the compactness theorem, demonstrating the finitary nature of first-order logical consequence. These results helped establish first-order logic as the dominant logic used by mathematicians.

In 1931, Gödel published On Formally Undecidable Propositions of Principia Mathematica and Related Systems, which proved the incompleteness (in a different meaning of the word) of all sufficiently strong, effective first-order theories. This result, known as Gödel’s incompleteness theorem, establishes severe limitations on axiomatic foundations for mathematics, striking a strong blow to Hilbert’s program. It showed the impossibility of providing a consistency proof of arithmetic within any formal theory of arithmetic. Hilbert, however, did not acknowledge the importance of the incompleteness theorem for some time.

Gödel’s theorem shows that a consistency proof of any sufficiently strong, effective axiom system cannot be obtained in the system itself, if the system is consistent, nor in any weaker system. This leaves open the possibility of consistency proofs that cannot be formalized within the system they consider. Gentzen (1936) proved the consistency of arithmetic using a finitistic system together with a principle of transfinite induction. Gentzen’s result introduced the ideas of cut elimination and proof-theoretic ordinals, which became key tools in proof theory. Gödel (1958) gave a different consistency proof, which reduces the consistency of classical arithmetic to that of intutitionistic arithmetic in higher types.

[edit] Beginnings of the other branches

Alfred Tarski developed the basics of model theory.

Beginning in 1935, a group of prominent mathematicians collaborated under the pseudonym Nicolas Bourbaki to publish a series of encyclopedic mathematics texts. These texts, written in an austere and axiomatic style, emphasized rigorous presentation and set-theoretic foundations. Terminology coined by these texts, such as the words bijection, injection, and surjection, and the set-theoretic foundations the texts employed, were widely adopted throughout mathematics.

The study of computability came to be known as recursion theory, because early formalizations by Gödel and Kleene relied on recursive definitions of functions.[2] When these definitions were shown equivalent to Turing’s formalization involving Turing machines, it became clear that a new concept – the computable function – had been discovered, and that this definition was robust enough to admit numerous independent characterizations. In his work on the incompleteness theorems in 1931, Gödel lacked a rigorous concept of an effective formal system; he immediately realized that the new definitions of computability could be used for this purpose, allowing him to state the incompleteness theorems in generality that could only be implied in the original paper.

Numerous results in recursion theory were obtained in the 1940s by Stephen Cole Kleene and Emil Leon Post. Kleene (1943) introduced the concepts of relative computability, foreshadowed by Turing (1939), and the arithmetical hierarchy. Kleene later generalized recursion theory to higher-order functionals. Kleene and Kreisel studied formal versions of intuitionistic mathematics, particularly in the context of proof theory.

[edit] Subfields and scope

Contemporary mathematical logic is roughly divided into four areas: set theory, model theory, recursion theory, and proof theory and constructive mathematics. Each area has a distinct focus, although many techniques and results are shared between multiple areas. The border lines between these fields, and the lines between mathematical logic and other fields of mathematics, are not always sharp. Gödel’s incompleteness theorem marks not only a milestone in recursion theory and proof theory, but has also led to Loeb’s theorem in modal logic. The method of forcing is employed in set theory, model theory, and recursion theory, as well as in the study of intuitionistic mathematics.

The mathematical field of category theory uses many formal axiomatic methods, and includes the study of categorical logic, but category theory is not ordinarily considered a subfield of mathematical logic. Because of its applicability in diverse fields of mathematics, mathematicians including Saunders Mac Lane have proposed category theory as a foundational system for mathematics, independent of set theory. These foundations use toposes, which resemble generalized models of set theory that may employ classical or nonclassical logic.

[edit] Formal logic

At its core, mathematical logic deals with mathematical concepts expressed using formal logical systems. These systems, though they differ in many details, share the common property of considering only expressions in a fixed formal language, or signature. The system of first-order logic is the most widely studied today, because of its applicability to foundations of mathematics and because of its desirable proof-theoretic properties.[3] Stronger classical logics such as second-order logic or infinitary logic are also studied, along with nonclassical logics such as intuitionistic logic.

[edit] First-order logic

Main article: First-order logic

First-order logic is a particular formal system of logic. Its syntax involves only finite expressions as well-formed formulas, while its semantics are characterized by the limitation of all quantifiers to a fixed domain of discourse.

Early results about formal logic established limitations of first-order logic. The Löwenheim–Skolem theorem (1919) showed that if a set of sentences in a countable first-order language has an infinite model then it has at least one model of each infinite cardinality. This shows that it is impossible for a set of first-order axioms to characterize the natural numbers, the real numbers, or any other infinite structure up to isomorphism. As the goal of early foundational studies was to produce axiomatic theories for all parts of mathematics, this limitation was particularly stark.

Gödel’s completeness theorem (Gödel 1929) established the equivalence between semantic and syntactic definitions of logical consequence in first-order logic. It shows that if a particular sentence is true in every model that satisfies a particular set of axioms, then there must be a finite deduction of the sentence from the axioms. The compactness theorem first appeared as a lemma in Gödel’s proof of the completeness theorem, and it took many years before logicians grasped its significance and began to apply it routinely. It says that a set of sentences has a model if and only if every finite subset has a model, or in other words that an inconsistent set of formulas must have a finite inconsistent subset. The completeness and compactness theorems allow for sophisticated analysis of logical consequence in first-order logic and the development of model theory, and they are a key reason for the prominence of first-order logic in mathematics.

Gödel’s incompleteness theorems (Gödel 1931) establish additional limits on first-order axiomatizations. The first incompleteness theorem states that no sufficiently strong, effectively given logical system can prove its own consistency unless it is actually inconsistent. Here a logical system is effectively given if it is possible to decide, given any formula in the language of the system, whether the formula is an axiom. When applied to first-order logic, the first incompleteness theorem implies that any sufficiently strong, consistent, effective first-order theory has models that are not elementarily equivalent, a stronger limitation than the one established by the Löwenheim–Skolem theorem. The second incompleteness theorem states that no sufficiently strong, consistent, effective axiom system for arithmetic can prove its own consistency, which has been interpreted to show that Hilbert’s program cannot be completed.

[edit] Other classical logics

Many logics besides first-order logic are studied. These include infinitary logics, which allow for formulas to provide an infinite amount of information, and higher-order logics, which include a portion of set theory directly in their semantics.

The most well studied infinitary logic is L_{\omega_1,\omega}. In this logic, quantifiers may only be nested to finite depths, as in first order logic, but formulas may have finite or countably infinite conjunctions and disjunctions within them. Thus, for example, it is possible to say that an object is a natural number using a formula of L_{\omega_1,\omega} such as

(x = 0) \lor (x = 1) \lor (x = 2) \lor \cdots.

Higher-order logics allow for quantification not only of elements of the domain of discourse, but subsets of the domain of discourse, sets of such subsets, and other objects of higher type. The semantics are defined so that, rather than having a separate domain for each higher-type quantifier to range over, the quantifiers instead range over all objects of the appropriate type. The logics studied before the development of first-order logic, for example Frege’s logic, had similar set-theoretic aspects. Although higher-order logics are more expressive, allowing complete axiomatizations of structures such as the natural numbers, they do not satisfy analogues of the completeness and compactness theorems from first-order logic, and are thus less amenable to proof-theoretic analysis.

[edit] Nonclassical and modal logic

Modal logics include additional modal operators, such as an operator which states that a particular formula is not only true, but necessarily true. Although modal logic is not often used to axiomatize mathematics, it has been used to study the properties of first-order provability (Solovay 1976) and set-theoretic forcing (Hamkins and Löwe 2007).

Intuitionistic logic was developed by Heyting to study Brouwer’s program of intuitionism, in which Brouwer himself avoided formalization. Intuitionistic logic specifically does not include the law of the excluded middle, which states that each sentence is either true or its negation is true. Kleene’s work with the proof theory of intuitionistic logic showed that constructive information can be recovered from intuitionistic proofs. For example, any provably total function in intuitionistic arithmetic is computable; this is not true in classical theories of arithmetic such as Peano arithmetic.

[edit] Algebraic logic

Algebraic logic uses the methods of abstract algebra to study the semantics of formal logics. A fundamental example is the use of Boolean algebras to represent truth values in classical propositional logic, and the use of Heyting algebras to represent truth values in intuitionistic propositional logic. Stronger logics, such as first-order logic and higher-order logic, are studied using more complicated algebraic structures such as cylindric algebras.

[edit] Set theory

Main article: Set theory

Set theory is the study of sets, which are abstract collections of objects. Many of the basic notions, such as ordinal and cardinal numbers, were developed informally by Cantor before formal axiomatizations of set theory were developed. The first such axiomatization, due to Zermelo (1908), was extended slightly to become Zermelo–Fraenkel set theory (ZF), which is now the most widely-used foundational theory for mathematics.

Other formalizations of set theory have been proposed, including von Neumann–Bernays–Gödel set theory (NBG), Morse–Kelley set theory (MK), and New Foundations (NF). Of these, ZF, NBG, and MK are similar in describing a cumulative hierarchy of sets. New Foundations takes a different approach; it allows objects such as the set of all sets at the cost of restrictions on its set-existence axioms. The system of Kripke-Platek set theory is closely related to generalized recursion theory.

Two famous statements in set theory are the axiom of choice and the continuum hypothesis. The axiom of choice, first stated by Zermelo (1904), was proved independent of ZF by Fraenkel (1922), but has come to be widely accepted by mathematicians. It states that given a collection of nonempty sets there is a single set C that contains exactly one element from each set in the collection. The set C is said to “choose” one element from each set in the collection. While the ability to make such a choice is considered obvious by some, since each set in the collection is nonempty, the lack of a general, concrete rule by which the choice can be made renders the axiom nonconstructive. Stefan Banach and Alfred Tarski (1924) showed that the axiom of choice can be used to decompose a solid ball into a finite number of pieces which can then be rearranged, with no scaling, to make two solid balls of the original size. This theorem, known as the Banach-Tarski paradox, is one of many counterintuitive results of the axiom of choice.

The continuum hypothesis, first proposed as a conjecture by Cantor, was listed by David Hilbert as one of his 23 problems in 1900. Gödel showed that the continuum hypothesis cannot be disproven from the axioms of Zermelo-Frankel set theory (with or without the axiom of choice), by developing the constructible universe of set theory in which the continuum hypothesis must hold. In 1963, Paul Cohen showed that the continuum hypothesis cannot be proven from the axioms of Zermelo-Frankel set theory (Cohen 1966). This independence result did not completely settle Hilbert’s question, however, as it is possible that new axioms for set theory could resolve the hypothesis. Recent work along these lines has been conducted by W. Hugh Woodin, although its importance is not yet clear (Woodin 2001).

Contemporary research in set theory includes the study of large cardinals and determinacy. Large cardinals are cardinal numbers with particular properties so strong that the existence of such cardinals cannot be proved in ZFC. The existence of the smallest large cardinal typically studied, an inaccessible cardinal, already implies the consistency of ZFC. Despite the fact that large cardinals have extremely high cardinality, their existence has many ramifications for the structure of the real line. Determinacy refers to the possible existence of winning strategies for certain two-player games (the games are said to be determined). The existence of these strategies implies structural properties of the real line and other Polish spaces.

[edit] Model theory

Main article: Model theory

Model theory studies the models of various formal theories. Here a theory is a set of formulas in a particular formal logic and signature, while a model is a structure that gives a concrete interpretation of the theory. Model theory is closely related to universal algebra and algebraic geometry, although the methods of model theory focus more on logical considerations than those fields.

The set of all models of a particular theory is called an elementary class; classical model theory seeks to determine the properties of models in a particular elementary class, or determine whether certain classes of structures form elementary classes.

The method of quantifier elimination can be used to show that definable sets in particular theories cannot be too complicated. Tarski (1948) established quantifier elimination for real-closed fields, a result which also shows the theory of the field of real numbers is decidable. (He also noted that his methods were equally applicable to algebraically closed fields of arbitrary characteristic.) A modern subfield developing from this is concerned with o-minimal structures.

Morley’s categoricity theorem, proved by Michael D. Morley (1965), states that if a first-order theory in a countable language is categorical in some uncountable cardinality, i.e. all models of this cardinality are isomorphic, then it is categorical in all uncountable cardinalities.

A trivial consequence of the continuum hypothesis is that a complete theory with less than continuum many nonisomorphic countable models can have only countably many. Vaught’s conjecture, named after Robert Lawson Vaught, says that this is true even independently of the continuum hypothesis. Many special cases of this conjecture have been established.

[edit] Recursion theory

Main article: Recursion theory

Recursion theory, also called computability theory, studies the properties of computable functions and the Turing degrees, which divide the uncomputable functions into sets which have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from of the work of Alonzo Church and Alan Turing in the 1930s, which was greatly extended by Kleene and Post in the 1940s.

Classical recursion theory focuses on the computability of functions from the natural numbers to the natural numbers. The fundamental results establish a robust, canonical class of computable functions with numerous independent, equivalent characterizations using Turing machines, λ calculus, and other systems. More advanced results concern the structure of the Turing degrees and the lattice of recursively enumerable sets.

Generalized recursion theory extends the ideas of recursion theory to computations that are no longer necessarily finite. It includes the study of computability in higher types as well as areas such as hyperarithmetical theory and α-recursion theory.

Contemporary research in recursion theory includes the study of applications such as algorithmic randomness and computable model theory as well as new results in pure recursion theory.

[edit] Algorithmically unsolvable problems

An important subfield of recursion theory studies algorithmic unsolvability; a problem is algorithmically unsolvable if there is no computable function which, given any instance of the problem, returns the correct answer. The first results about unsolvability, obtained independently by Church and Turing in 1936, showed that the Entscheidungsproblem is algorithmically unsolvable. Turing proved this by establishing the unsolvability of the halting problem, a result with far-ranging implications in both recursion theory and computer science.

There are many known examples of undecidable problems from ordinary mathematics. The word problem for groups was proved algorithmically unsolvable by Pyotr Sergeyevich Novikov in 1955 and independently by W. Boone in 1959. The busy beaver problem, developed by Tibor Radó in 1962, is another well-known example.

Hilbert's tenth problem asked for an algorithm to determine whether a multivariate polynomial equation with integer coefficients has a solution in the integers. Partial progress was made by Julia Robinson, Martin Davis, and Hilary Putnam. The algorithmic unsolvability of the problem was proved by Yuri Matiyasevich in 1970 (Davis 1973).

[edit] Proof theory and constructive mathematics

Main article: Proof theory

Proof theory is the study of formal proofs in various logical deduction systems. These proofs are represented as formal mathematical objects, facilitating their analysis by mathematical techniques. Several deduction systems are commonly considered, including Hilbert-style deduction systems, systems of natural deduction, and the sequent calculus developed by Gentzen.

The study of constructive mathematics, in the context of mathematical logic, includes the study of systems in non-classical logic such as intuitionistic logic, as well as the study of predicative systems. An early proponent of predicativism was Hermann Weyl, who showed it is possible to develop a large part of real analysis using only predicative methods (Weyl 1918).

Because proofs are entirely finitary, whereas truth in a structure is not, it is common for work in constructive mathematics to emphasize provability. The relationship between provability in classical (or nonconstructive) systems and provability in intuitionistic (or constructive, respectively) systems is of particular interest. Results such as the Gödel–Gentzen negative translation show that it is possible to embed (or translate) classical logic into intuitionistic logic, allowing some properties about intuitionistic proofs to be transferred back to classical proofs.

Recent developments in proof theory include the study of proof mining by Ulrich Kohlenbach and the study of proof-theoretic ordinals by Michael Rathjen.

[edit] Connections with computer science

The study of computability theory in computer science is closely related to the study of computability in mathematical logic. There is a difference of emphasis, however. 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.

The study of programming language semantics is related to model theory, as is program verification (in particular, model checking). The Curry-Howard isomorphism between proofs and programs relates to proof theory, especially intuitionistic logic. Formal calculi such as the lambda calculus and combinatory logic are now studied as idealized programming languages.

Computer science also contributes to mathematics by developing techniques for the automatic checking or even finding of proofs, such as automated theorem proving and logic programming.

[edit] Foundations of mathematics

In the 19th century, mathematicians became aware of logical gaps and inconsistencies in their field. It was shown that Euclid's axioms for geometry, which had been taught for centuries as an example of the axiomatic method, were incomplete. The use of infinitesimals, and the very definition of function, came into question in analysis, as pathological examples such as Weierstrass' nowhere-differentiable continuous function were discovered.

Cantor's study of arbitrary infinite sets also drew criticism. Leopold Kronecker famously stated "God made the integers; all else is the work of man," endorsing a return to the study of finite, concrete objects in mathematics. Although Kronecker's argument was carried forward by constructivists in the 20th century, the mathematical community as a whole rejected them. David Hilbert argued in favor of the study of the infinite, saying "No one shall expel us from the Paradise that Cantor has created."

Mathematicians began to search for axiom systems that could be used to formalize large parts of mathematics. In addition to removing ambiguity from previously-naive terms such as function, it was hoped that this axiomatization would allow for consistency proofs. In the 19th century, the main method of proving the consistency of a set of axioms was to provide a model for it. Thus, for example, non-Euclidean geometry can be proved consistent by defining point to mean a point on a fixed sphere and line to mean a great circle on the sphere. The resulting structure, a model of elliptic geometry, satisfies the axioms of plane geometry except the parallel postulate.

With the development of formal logic, Hilbert asked whether it would be possible to prove that an axiom system is consistent by analyzing the structure of possible proofs in the system, and showing through this analysis that it is impossible to prove a contradiction. This idea led to the study of proof theory. Moreover, Hilbert proposed that the analysis should be entirely concrete, using the term finitary to refer to the methods he would allow but not precisely defining them. This project, known as Hilbert's program, was seriously affected by Gödel's incompleteness theorems, which show that the consistency of formal theories of arithmetic cannot be established using methods formalizable in those theories. Gentzen showed that it is possible to produce a proof of the consistency of arithmetic in a finitary system augmented with axioms of transfinite induction, and the techniques he developed to so do were seminal in proof theory.

A second thread in the history of foundations of mathematics involves nonclassical logics and constructive mathematics. The study of constructive mathematics includes many different programs with various definitions of constructive. At the most accommodating end, proofs in ZF set theory that do not use the axiom of choice are called constructive by many mathematicians. More limited versions of constructivism limit themselves to natural numbers, number-theoretic functions, and sets of natural numbers (which can be used to represent real numbers, facilitating the study of mathematical analysis). A common idea is that in order to assert that a number-theoretic function exists, a concrete means of computing the values of the function must be known.

In the early 20th century, Luitzen Egbertus Jan Brouwer founded intuitionism as a philosophy of mathematics. This philosophy, poorly understood at first, stated that in order for a mathematical statement to be true to a mathematician, that person must be able to intuit the statement, to not only believe its truth but understand the reason for its truth. A consequence of this definition of truth was the rejection of the law of the excluded middle, for there are statements that, according to Brouwer, could not be claimed to be true while their negations also could not be claimed true. Brouwer's philosophy was influential, and the cause of bitter disputes among prominent mathematicians. Later, Kleene and Kreisel would study formalized versions of intuitionistic logic (Brouwer rejected formalization, and presented his work in unformalized natural language). With the advent of the BHK interpretation and Kripke models, intuitionism became easier to reconcile with classical mathematics.

[edit] See also

[edit] Notes

  1. ^ Undergraduate texts include Boolos, Burgess, and Jeffrey (2002), Enderton (2002), and Mendelson (1997). A classic graduate text by Shoenfield (2001) first appeared in 1967.
  2. ^ A detailed study of this terminology is given by Soare (1996).
  3. ^ Ferreirós (2001) surveys the rise of first-order logic over other formal logics in the early 20th century.

[edit] References

[edit] Undergraduate texts

[edit] Graduate texts

[edit] Research papers, monographs, texts, and surveys

[edit] Classical papers, texts, and collections

  • Burali-Forti, Cesare (1897), A question on transfinite numbers , reprinted in van Heijenoort 1976, pp. 104–111.
  • Dedekind, Richard (1872), Stetigkeit und irrationale Zahlen . English translation of title: "Consistency and irrational numbers".
  • Dedekind, Richard (1888), Was sind und was sollen die Zahlen?  Two English translations:
    • 1963 (1901). Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.
    • 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed., Oxford University Press: 787–832.
  • Fraenkel, Abraham A. (1922), "Der Begriff 'definit' und die Unabhängigkeit des Auswahlsaxioms", Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse, pp. 253–257  (German), reprinted in English translation as "The notion of 'definite' and the independence of the axiom of choice", van Heijenoort 1976, pp. 284–289.
  • Gentzen, Gerhard (1936), "Die Widerspruchsfreiheit der reinen Zahlentheorie", Mathematische Annalen 112: 132–213, doi:10.1007/BF01565428 , reprinted in English translation in Gentzen's Collected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969.[specify]
  • Gödel, Kurt (1929), "Über die Vollständigkeit des Logikkalküls", doctoral dissertation, University Of Vienna . English translation of title: "Completeness of the logical calculus".
  • Gödel, Kurt (1930), "Die Vollständigkeit der Axiome des logischen Funktionen-kalküls", Monatshefte für Mathematik und Physik 37: 349–360, doi:10.1007/BF01696781 . English translation of title: "The completeness of the axioms of the calculus of logical functions".
  • Gödel, Kurt (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatshefte für Mathematik und Physik 38 (1): 173–198, doi:10.1007/BF01700692 , see On Formally Undecidable Propositions of Principia Mathematica and Related Systems for details on English translations.
  • Gödel, Kurt (1958), "Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes", Dialectica. International Journal of Philosophy 12: 280–287, doi:10.1111/j.1746-8361.1958.tb01464.x , reprinted in English translation in Gödel's Collected Works, vol II, Soloman Feferman et al., eds. Oxford University Press, 1990.[specify]
  • van Heijenoort, Jean, ed. (1967, 1976 3rd printing with corrections), From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Mass: Harvard University Press, ISBN 0-674-32449-8 (pbk.) 
  • Hilbert, David (1889), The Foundations of Geometry , republished 1980, Open Court, Chicago.
  • David, Hilbert (1929), "Probleme der Grundlegung der Mathematik", Mathematische Annalen 102: 1–9, doi:10.1007/BF01782335 . Lecture given at the International Congress of Mathematicians, 3 September 1928. Published in English translation as "The Grounding of Elementary Number Theory", in Mancosu 1998, pp. 266–273.
  • Kleene, Stephen Cole (1943), "Recursive Predicates and Quantifiers", American Mathematical Society Transactions 54 (1): 41–73, doi:10.2307/1990131 .
  • Lobachevsky, Nikolai (1840), Geometrishe Untersuchungen zur Theorie der Parellellinien  (German), reprinted in English translation as "Geometric Investigations on the Theory of Parallel Lines" in Non-Euclidean Geometry, Robert Bonola (ed.), Dover, 1955. ISBN 0486600270
  • Leopold Löwenheim (1918)[citation needed]
  • Mancosu, Paolo, ed. (1998), From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s, Oxford: Oxford University Press .
  • Peano, Giuseppe (1888), Arithmetices principia, nova methodo exposita  (Italian), excerpt reprinted in English stranslation as "The principles of arithmetic, presented by a new method", van Heijenoort 1976, pp. 83 97.
  • Richard, Jules (1905), "Les principes des mathématiques et le problème des ensembles", Revue générale des sciences pures et appliquées 16: 541  (French), reprinted in English translation as "The principles of mathematics and the problems of sets", van Heijenoort 1976, pp. 142–144.
  • Thoralf Skolem (1919)[citation needed]
  • Tarski, Alfred (1948), A decision method for elementary algebra and geometry, Santa Monica, California: RAND Corporation 
  • Turing, Alan M. (1939), "Systems of Logic Based on Ordinals", Proceedings of the London Mathematical Society 45 (2): 161–228, doi:10.1112/plms/s2-45.1.161 
  • Zermelo, Ernst (1904), "Beweis, daß jede Menge wohlgeordnet werden kann", Mathematische Annalen 59: 514–516, doi:10.1007/BF01445300  (German), reprinted in English translation as "Proof that every set can be well-ordered", van Heijenoort 1976, pp. 139–141.
  • Zermelo, Ernst (1908), "Neuer Beweis für die Möglichkeit einer Wohlordnung", Mathematische Annalen 65: 107–128, doi:10.1007/BF01450054  (German), reprinted in English translation as "A new proof of the possibility of a well-ordering", van Heijenoort 1976, pp. 183–198.

[edit] External links

[show]

v  d  e

Major fields of mathematics

 
[show]

v  d  e

Logic

Portal ·Category ·WikiProject ·Logic stubs ·Mathlogic stubs ·Cleanup ·Talk ·changes
 
[show]

 

History and core topics

 
History
 
Core topics
 
[show]

 

Key concepts and logics

 
Reasoning
 
Informal
 
Philosophy
of logic
 
Mathematical
 
Propositional
 
Predicate
 
Modal
 
Other non
classical
 
[show]

 

Controversies

 
 
[show]

 

Key figures

 
Alfarabi · Algazel · Alkindus · Al-Razi · Aristotle · Averroes · Avicenna · Boole · Cantor · Carnap · Church · Dharmakirti · Dignāga · Frege · Gentzen · Kanada · Gödel · Gotama · Hilbert · Ibn al-Nafis · Ibn Hazm · Ibn Taymiyyah · Kripke · Leibniz · Mozi · Nagarjuna · Pāṇini · Peano · Peirce · Putnam · Quine · Russell · Skolem · Suhrawardi · Tarski · Turing · Whitehead · Zadeh
 
[show]

 

Lists

 
Topics
Outline of logic · General · Basic · Mathematical logic · Boolean algebra · Set theory
 
Other
 

Read Full Post »

Older Posts »