FORMULATION OF LINEAR-PROBLEMS AND SOLUTION BY A UNIVERSAL MACHINE

Using the predicate language for ordered fields a class of problems re ferred to as linear problems is defined. This class contains, for exam ple, all systems of linear equations and inequalities, all linear prog ramming problems, all integer programming problems with bounded variab les, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfia bility problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quad ratic programming problems with bounded variables. A single, one, algo rithm, to which we refer as the Universal Linear Machine, is described . It solves any instance of any linear problem. The Universal Linear M achine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates a linear algorithm fo r the problem. Then, given an instance of the linear problem, in the s econd phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loople ss and executes only the five ordered field operations - additions, mu ltiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which t he linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametri c instances of the linear problem.