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.
collections
- retrospective theses [1604]