On the complexity of the correctness problem for non-zeroness test instruction sequences

摘要

This paper concerns the question to what extent it can be efficiently determined whether an arbitrary program correctly solves a given problem. This question is investigated with programs of a very simple form, namely instruction sequences, and a very simple problem, namely the non-zeroness test on natural numbers. The instruction sequences concerned are of a kind by which, for each n > 0, each function from {0, 1}(n) to {0, 1} can be computed. The established results include the time complexities of the problem of determining whether an arbitrary instruction sequence correctly implements the restriction to {0, 1}(n) of the function from {0, 1}* to {0, 1} that models the non-zeroness test function, for n > 0, under several restrictions on the arbitrary instruction sequence. (C) 2019 Elsevier B.V. All rights reserved.