Computer software is so called to distinguish it from computer hardware, which encompasses the physical interconnections and devices required to store and execute (or run) the software. At the lowest level, software consists of a machine language specific to an individual processor. A machine language consists of groups of binary values signifying processor instructions that change the state of the computer from its preceding state. Software is an ordered sequence of instructions for changing the state of the computer hardware in a particular sequence. It is usually written in high-level programming languages that are easier and more efficient for humans to use (closer to natural language) than machine language. High-level languages are compiled or interpreted into machine language object code. Software may also be written in an assembly language, essentially, a mnemonic representation of a machine language using a natural language alphabet. Assembly language must be assembled into object code via an assembler.
The term “software” was first used in this sense by John W. Tukey in 1958. In computer science and software engineering, computer software is all computer programs. The theory that is the basis for most modern software was first proposed by Alan Turing in his 1935 essay Computable numbers with an application to the Entscheidungsproblem (German for ‘decision problem). is a challenge posed by David Hilbert in 1928. The Entscheidungsproblem asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either “True” or “False” according to whether the statement is true or false. The algorithm need not justify its answer, nor provide a proof, so long as it is always correct. Such an algorithm would be able to decide, for example, whether statements such as Goldbach’s conjecture or the Riemann hypothesis are true, even though no proof or disproof of these statements is known. The Entscheidungsproblem has often been identified in particular with the decision problem for first-order logic (that is, the problem of algorithmically determining whether a first-order statement is universally valid).
read more here: http://en.wikipedia.org/wiki/Entscheidungsproblem