Mathematical Programming and Turing-completeness

Mathematical Programming (MP) is a formal language that formally describes solutions of optimization problems whose objective function and constraints are explicit algebraic/transcendental functions of a set of given parameters (the problem input) and decision variables (encoding the solution to the problem). The solution process is carried out by a solver. As for any programming language, one may ask whether MP is Turing-complete, i.e. whether it can simulate a Universal Turing Machine. We exhibit a simulation mechanism that lends itself practical uses, and illustrate some interesting applications to algorithmic analysis.

By: Leo Liberti, Fabrizio Marinelli

Published in: Journal of Combinatorial Optimization, volume 28, (no 1), pages 82-104; SI 10.1007/s10878-014-9715-3 in 2014

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .