Computation using s-programs
Abstract
The concepts of S and Sn programs are given by Davis,
Weyuker, 1983. Several parts of the complexity theory are
carried out directly for S and Sn programs. The concepts of
non-deterministic and deterministic computation from
S-programs are defined, and deterministic simulation of
non-deterministic computation is proved. A universal
5-program for general (non-deterministic) computation is
shown to require only one duplicate line label. Complexity
results are given for these and other simulations, e.g.
Turing Machine by 5-programs and the reverse. Cook's Theorem
for Sn programs is proved in full.