Mathematical programming is Turing complete, and can be used as a general-purpose declarative language. We present a new constructive proof of this fact, and showcase its usefulness by discussing an application to finding the hardest input of any given program running on a Minsky Register Machine. We also discuss an application of mathematical programming to software verification obtained by relaxing one of the properties of Turing complete languages.
Mathematical programming: Turing completeness and applications to software analysis / Leo, Liberti; Marinelli, Fabrizio. - In: JOURNAL OF COMBINATORIAL OPTIMIZATION. - ISSN 1382-6905. - STAMPA. - 28:1(2014), pp. 82-104. [10.1007/s10878-014-9715-3]
Mathematical programming: Turing completeness and applications to software analysis
MARINELLI, Fabrizio
2014-01-01
Abstract
Mathematical programming is Turing complete, and can be used as a general-purpose declarative language. We present a new constructive proof of this fact, and showcase its usefulness by discussing an application to finding the hardest input of any given program running on a Minsky Register Machine. We also discuss an application of mathematical programming to software verification obtained by relaxing one of the properties of Turing complete languages.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
