C?PUTATIONAL CONPIXIT? AND NONDETE?IN?SM
IN FLOWCHART PROGRAMS*
Theodore Paul Baker
TR 73--H185
September 1973
A Thesis
Presented to the Faculty of the Graduate School
of Cornell University for the D?gree of
Doctor of Philosophy
Department of Computer Science
Cornell University
Ithaca, N.Y. 14850
*This resea?ch was partially supported by a Ford Foundation 6-Year Ph.D. Program
fellowship and by National Science Foundation Grant GJ-3317x
Acknowledgements
ti would like to express my deepest gratitude to
professor J. Hartmanis, chairman of my special committee,
for the shared insights, guidance, and encouragement that
made this thesis possible. I would also like to thank
professors R. Constable, J. Williams, and A. Nerode for
serving on my special committee.
I want to thank J. Simon for his thoughtful
comments and his help in proofreading, particularly for
suggesting Corollary 4.3 and tying up several `1loose
ends" mentioned in Chapter 7. I also am indebted to
K. ?ehlhorn for Theorem 4.5 and M. Siegel for help in
proofreading.
This work was partially supported by a Ford
Foundation 6-Year Ph.D. program fellowship and by
National Science Foundation Grant GJ-33l7X.
0
CONTENTS
INTRODUCTION
1.1			Motivation			1
1.2			Outline of Thesis			5
1.3			Basic Notation and Definitions			7
1.4			How the Blum Axioms are Weak			24
1.5			Nondeterminism--HComment5 on Definitions			28
ENUMERABILITY OF COMPLEXITY CLASSES
2.1			General			34
2.2			Constant Bounds			3?
2.3			Ultimately Increasing Bounds			39
TRANSLATIONS
3.1			Between Flowchart Interpretations			45
3.2			To Flowchart Interpretations			53
-?3.3			Between G?del Numberings			56
NONDETEp?INISM
4.1			Discussion			61
4.2			NDP and DP for Flowchart Measures			64
4.3			Nondeterminism at Other Complexity Levels			80
RELATIONS TO NATURAL MEASURES
5.1			Turing Machine Time			85
5.2			Turing Machine Tape			91
2
3
4
5
6
7
OTHER PROPERTIES OF THE FLOWCHART MEASURES
6.1 ??o "Natural11 Properties
6.2 Some "Unnatural" Failings
6.3 Further Dimensions of Flexibility
CONCLUSION
?7.l Summary of Results
7.2 Possibilities for Further Research
7.3 Step Measures
96
97
104
114
115
118
0
120
REFERENCES
It is clear that a viable theory of computation
must deal realistically with the quantitative as??ects
of computing and must develop a general theory which
studies the properties of possible measures of the
difficulty of computing functions. Such a theory r'L?St
go beyond the classification of functions as comput-
able and noncomputable, or elementary and primitive
recursive, etc. It must concern itself with comput-
ational complexity measures which are defined for all
possible computations and which assign a complexity
to each computation which terminates. Furthermore,
this theory must eventually reflect some aspects of
real computing to justify its existence by contribut-
ing to the general development of computer science.
J. Hartmanis and J.E. Hopcroft
"An Overview of the Theory of Coimputational ???p???i?yt1
0
1 Introduction
11.1 ?otivation
This thesis is an effort to contribute to the
Theory of Computation by investigation of a special cla?s
of complexity measures, the step-counting functions asso-
ciated with flowchart programs. It would perhaps bs fit-
ting to begin by describing the worthy contributior r'
all the others who have brought the theory to its pT?sent
state, yet the field has grown to a point where such a
review would far overshadow any new material we might
present. In the discussion which follows we therefore
attempt merely to outline the immediate context in which
this work was done. Apologies are offered to those whose
work nay be relevant but whose work is not menticn'?? because
it did not directly influence the thesis.
The work which did directly influence the thesis
falls roughly into three areas: Program Schecata; the LBA
Problem, NP=?P, and nondeterminism in general; Computational
Complexity. Although bordering on the first two areas, our
interest lies primarily in Computational Complexity.
An undesirable gap has been growing in Complexity
Theory between the concrete an the abstract. Early work,
beginning with 9.artnanis and Stearns [14], dealt with corn-
plexity measures defired in terms of very specific comput-
ing devices, mostly Turing machines. With the introduction
in 1967, by M. Blun (1] of an axiomatic characterization
of "step-counting functions", the theory took a turn t?ard
the abstract. slum's axioms have been shown to have many
deep consequences and have served as the roots of a rapidly-
growing fruitful theory. Nevertheless, they are not wholly
satisfactory in that they admit too many measures, some of
which are intuitively unacceptable (see ?l.5). Since the
answers to a large number of questions one may ask about
a complexity measure are independent of the Slum axioms,
work ha continued in the specific models of computation
where such questions are answerable. The problem is that we
fre??ently want to talk about measures that lie between these
two extremes: on the one side the specific measures with their
peculiar local properties, and on the other side the Slum
measures, so general as to render many questions meaningless.
The theory needs a notion of "natural" complexity measure to
fill this void, as Hartmanis points out in [10]
We can find a case in point, and one motivation for
the present work, in nondeterminism. ?uch attention has
been drawn of late to questions which amount, in essence, to
whether there is any conputational power to be gained by al-
lowing nondeterminism in certain specific models of resource-
bounded computation [6,13,17]. Such questions are beyond the
scope of general Slum complexity theory, which does not recog-
nize a distinction between deterninistic and nondeterministic
measures. Nonetheless, this distinction seems to be am
important abstract concept, transcending individual models.
3
Our first approach to more abatract n?ndetermini?r.'
(which resulted in theorems 4.1 and 4.2) made use of Turing
machines with recursive oracles. Although the measures
defined by these machines are quite variad in tneir behav-
iour, owing to the oracles, they still have many of the
idiosyncracies of the Turing machine step measure and there-
fore are not exactly what we are looking for.
What we seek is either a narrower abstract definition
of complexity measure, or, failing that, a class of specific
measures which reflect a natural conception of conputation
and in which we can discuss notions like nondeterminism, but
which are sufficiently general to allow us to overlook the
peculiarities of the individual measures. Hartmanis [101
gives several good reasons why we are unlikely to succeed
by piling on more and more exclusionary additicns to t.?a
Blum axioms, sggesting that a bottom-up constructive app-
roach is more promising. With this in mind, we have decided
to put?off attempts to improve upon the Blum axioms until we
know more. In the mean time we hope to learn more by exam-
ining a class of specific natural Blum measures.
Research on reducibilityand equivalence in program
schemata by Ianov, Paterson, and others [16,21,24) has shown
a way to view the structure of algorithms separate from the
obscuring details of computational systems. We apply this
same technique to complexity measures. A flowchart is a
program schema, defining a program for each interpretation
given to its operations. Likewise, a flowchart language
4
is a complexity measure schema, defining a complexity measure
for each (universal) interpretation given to its operations.
Whereas the research in program schemata has been primarily
motivated by an interest in the problems of formal simplific-
ation and, more recently, in questions about the computation-
al generality of various program structures (as exemplified
by (31), we are presently interested in how the complexity
classes defined by the step-counting functions are affected
by changes of interpretation1 which we consider superficial
relative to the unchanging schematic framework.
5
?l.2 OutlineofThesis
In this chapter we intend to lay a basis in motiv-
ations and definitions for the results which we doscribe
later. The chapters following this one each cover a group
of properties of the flowchart step measures. T?gether,
they represent an attempt to place the class of flowchart
measures as a bridge between the specific natural measures
with which we are familiar and the full generality of the
Blum measures.
Chapter 2 deals with the problem of recursively
enumerating complexity classes. It exhibits two large
groups of bounds for which the flowchart complexity
classes sre provably r.e.
Chapter 3 approaches the flowchart measures and
their associated G?del numberings as ob?ects of translations.
The flowchart G.N.s are shown to be especially good targets
for translation from other G5del numberings. We show that
a "simple translation between flowchart interpretations
exists and that under some circumatances it produces
efficient programs.
Chapter 4 is concerned with how nondeterminism relates
to determinism in flowchart programs. Two examples of flow-
chart interpretations are given, for one of which NP#P, and
for the other of which NP=P. These are presented so as to
apply not only to the polymomial time bounds, but to any class
of time bounds which share certain properties with them.
It is thus shown that the answer to Cook's Np=?p (6) and
the answers to similar questions about nondeterminism and
othor classes of time bounds must be strongly dependent on
the precise model of computation. Further results are
given which indicate that if there is a "rule" it is for
nondeterminism to allow greater computational speed than
determinism.
Chapter 5 gives two examples of the manner in
which well-known natural measures (Turing machine tape
and multitape T.m. time) can be "simulated" by flowchart
measures so as to make classes like the polynomially-
bounded computable functions the same.
Chapter 6 offers two additional properties which
we have observed in the flowchart and other natural
measures that perhaps whould be consi&ered requisite for
"naturalness'.. Examples are then given of "natural"
properties proposed by others which do not hold for all
flowchart measures. FiAally, some ancillary properties
are presented which demonstrate how flexibly the flowchart
interpretation may be used to tailor the measure, so as to
uniformly speed up the flowchart "machine", to selectively
reorder the complexities of certain functions, or to limit
the computational advantage gained by having more than one
register.
6A
Chapter 7 concludes the thesis. The first section
summarizes the nain results. The second section catalogues
some natural questions which we would like to an?wer but
hawe not answered as yet. The last section proposes a
tentative framework for an abstract axionatization of step
measures which would explicitly relate the `step" as a
unit of cost to the step as part of a conputatlon.
7
11.3
Defin?tioms
Basic ?otatiom an
We are forced to assume that the reader has prior
knowledge of the most fundamental terms and concepts of
Recursive Function Theory (251, complexity Theory [121,
and Graph Theory (8]. However, some elementary defin-
itions are included below, because our versions are not
standard or because we wish to fix notation.
A. General
N denotes the set of non-negative integers1
(0,1,2,3, ... ). A number means an element of N.
N is the same as (`1' o+o.*)*, a regular subset of the
binary (bit-) strings, (O,l)*. Bit-strings are differ-
entiated from decimal numerals and from variables by
enclosure with "5. Thus, if n --H 5, `lnOlin.0.
represents the bit-string `ll1ll0ll0l0?, which is 2010
in decimal notation. Zero is written  (the null string)
when treated as a bit-string. Multiplication (x?y) is
distinguished from concatenation of bit-strings (xy).
Unless stated otherwise, a (partial) function
means a (partial) computable function from (a subset of)
N to N. R denotes the set of all total recursive functions.
fis denotes the restriction of the (partial) function f
to the domain S. Two (partial) functions f and g are
equivalent (f g) if for all x (such that f(x) or g(x)
is defined) f(x) --H g(x). If for all x (such that f(x)
8
or g(x) is defined) f(x) < g(x) then we write f <
Zf a relation holds everywhere but on a finite set we say
that it holds almosteverywnere (a.e.); if it holds on
an infinite set we say it holds infinitelyoften (i.o.)
?or example, f > g i.o. means that there are infiritely
sany x such that f(x) > g(x). If f > k a.e. for every k
in N then r is ultimatelyincreasing. A function g is
said to be 0(f) for some function f if there is a constant
c such that g < c?f.
A predicate is a function from N to (0,1). If P
is a predicate then P denotes the cemolement of P, the
function which is 0 when P is 1 and v.v.
To define functions we will frequently use an informal
LIsp-like [221 notation, based on A. Church's (41 lambda
calculus (e.g., ?x,y((x>y)? (x-y); (y-x)) for the
integer norm It follows standard conventions close-
ly enough that the reader should have no difficulty in
understanding.
9
G generally denotes an acceptable ?d?l numbering
of the partial recursive functions (e.g. a lexi-
cographic enumeratiom of the programs for a universal
binary single-tape Turing machine). G denotes a Blum
complexity measure on G (e.g., the T.M. step count).
G denotes the ?th partial recursive function in this G.N.
and Gi denotes its complexity or step-counting function.
For any recursive function t, ?G (abbreviated Rt) is the
t
class of total recursive functions of complexity t or
less almost everywhere, i.e.,
G
at --H tf:??? I fGi? ?Gi?<t a.e., fER )
Similarly L?Gt denotes the class of sets
(s: Gi accepts S? Gi?<t a.e., feR )
A function T is a translation from G5del numbering G to
G.N. H if for every iEN
Gj ?HT(i)
10
B. Flowcharts
We define here a specific type of program schema,
called a flovchart. Similar definitions of sche?ata are
found in (3,16,21,241.
A functionnaI,e is a sequence of one or more "?"s
followed by one or more "`"5. A predicatename is a
sequence of one or more "P"s followed by one or more "`"5.
denotes "Fwith i "?"s and ?"5, and
should be interpreted similarly.
A flowchart language L is a pair (Ip?i?) of sets of
numbers defining a set
= ??(n
mi			iCip
of ?ni-arYpredicatenames and a set
= fFm(?i) iEI 1
i . p
of ni-aryfunctionnames. Unless the contrary is stated,
? and F are assuned to be recursively enumerable and of
unary names. With few exceptions, the following definitions
and proofs apply to the general n-ary case, but the notation
required to carry this through will eventually be dropped,
since it becomes nearly unreadable.
An L-predicate-tern is a predicate name pm(n.i) fol-
lowed by n. positive integers, called regi?t?rindic??. An
L-function-terin is a positive integer, also called a reg-
ister index, followed by a function name ?Fm(?.i) and n? reg-
ister indices.
`[Note: ((mi,ni))i=1 is an enumeration of NxN. 1
Ii
A nondeterministicL-flowchart is a labelled directed
graph with nodes labelled with L-predicate-terms and L-
function-terms and edges labelled with 0 and 1, the nodes
being indexed by an initial segment of the positive integers.
The node indexed with 1 is called the startingnode. A
deterministic L-flowchart in addition satrsfies the require-
ment that here be at most one edge from each function-term
node and at most one edge labelled 0 and at most one edge
labelled 1 from each predicate-term node. Ordinarily, a
flowchart is taken to mean a non-deterministic L-flowchart
for some flowchart language (FCL) L. All flowcharts are
assurned to be finite, although it does make sense to speak
of infinite flowcharts.
In a flowchart, a terminal node is a node which has no
edges from it, or which is a predicate-term node and has no
0-edges or no 1-edges from it.
`f a fl
?wn- ie u			?wcnart:
Here we have substituted shorter auxiliary names for
the functions and predicates in order to enhance readability.
This practice will be continued in subsequent proofs and
examples. The canonical "FP'" notation is necessary only to
insure the existence of an enumeration of all flowcharts.
If A. is a flowchart, Aj<j> denotes the node Of Aj
with index ?, if such exists. Otherwise, Aj<j> is defined
to be the null set, ?. A path in A. is a sequence
Ai<j1>S Aic?2>, o+. of nodes such that there is an edge
from each node to the next one, repetitions being permitted.
A cycle is a path which begins and ends with the sarne node.
A flowchart which is a tree is called a tree-flowchart.
??en we talk about the complexity of computations
on flowcharts, we will need a simple canonical way of
encoding the flowcharts as integers. For this reason only,
the following detailed description is given.
iJ
flowchart ::--H
node
term
term
index
o-name
name
indexlist
f-narne
0-ed es
node
$ term 0-edges i-edges
index f-name indexlist
p-name indexlist
(1 0 )
`00
`01'
# $ name
`10'
`Il
o+l'+ `0'+
$ (? index)
$ name
*
$ (* edge)
0 index
index
$(# ed e)
edge			_ _____
edge			_____
1-edges			_ _
Condensed slightly, the flowchartdescriptions are:
* * **
($(index+ ?)$ name $(# index) $(? edge) $(jed e) )
Note: In the dascription above the notation of regular
expressions is used. x* denotes all strings of the form x
concatenated with each other in all possible ways, that is,
all sequences of strings of the form x, including the null +
string. tThen we wish to exclude the null string we write x
X+Y denotes all strings of the form X or Y.
14
As this clearly demonstrates, the valid flowchart
descriptions are a regular subset of)) which
we have identified with N. The way in which they may be
interpreted as describing flowcharts is suggested in part
by the names of the nonterminals in the preceding grammar,
and may be f?rther explained as follows:
A node describes a node. The index of the node it des-
cribes is the order of the node in the ?.c. description.
An index is an encoded integer, possibly the index of a
register.
An edee is an encoded integer, possibly preceded by a
`00'. It represents the index of the node it is in less
the index of the node to which it goes. A negative sign
is represented by the initial `00. when it appears If
the edge is to am index beyond the range of the flowchart
description it is interpreted as null (going nowhere).
An -name is the name of a function and a p-name is the
name of a predicate. For n-ary operations there is a
final string of n `0's in the name. The n argument
register indices are taken to be the first n indices
encoded following the name. If there are too many, the
excess are ignored. If there are too few, the unspecified
register indices are assumed to be 1. If the result
register index of a function is missing, then it is also
asswned to be 1.
[Local note on underlining: Here an index is not an index,
but the nonterminal in the preceding grammar, or a string
generated from that nonterminal. Similarly for other words.i
15
All invalid flowchart descriptions are defined to
represent the null flowchart (0 or ), so that every
element of N can be thought of as denoting a uni?ue flow-
o+chartr A Zf we wish to enumerate some subset of the
n
flowcharts, say the deterninistic flowcharts, D, we define
D = A if A c D and D - A (the null flowchart) if A ?
n n n n 0 n
16
c. Programs
An interoretation J is a pair (P,r) of a set
--H (n )
(P i			ici? )
mi			P
of predicates and a set
P -			??			F
i			icz? )
of functions. Together these predicates and functions are
called the onerations of J. Unless stated otherwise, P and r
are always r.e. sets and the predicates and functions are
JJ
always recursive. tj denotes the language ?`p"F?
J-flowchart is an abbreviation for t?-fl0wchart.
A and n ?enote the canonical lexicographic enurnerations of
the (N1N) flowcharts (i.e., all the flowcharts) as described
above. These nay be also interpreted as enuncrat?ons of
the J-flowcharts by letting all flowcharts using nanes of
operations not in J represent the null flowchart.
A flowchartnrogram A?. is a flowchart A. together with
1			I
an interpretation J			such that A. is an Lj-
flowchart. A?. is called a J-oroqran.
D. Computation
Each program A. may be interpreted for each m as
defining a unique partial n-ary function A?(x1,..
We define this by first describing a more general actiom
of A. on sets of sequences of numbers, which might be
called "instantaneous descriptions" (i.d.s). Let m be the
maximun register index appearing in Ai. The finite
sequences of one or more elements of N are denoted by
and 2 denotes the finite sets of these. For each set
+
S in N2 define A. [s)
( (5.,Xj. .. xm): (s,x1, Xn) is in S, n>m, Ai<s>$%e
and
(1)			?f A.			is labelled P			:1..zk then
(a)			there is an edge labelled pJ(x			..x ) from A.
j :?` 2k 1<5>
to Ai<s?> and Xj			Xi ?or i = I to m, or
(b)			there is no edge so labelled1 a			0, and Xi' --H Xj
for i			1 to m.
(2)
Otherwise, A.			is labelled Z0Fj(k)			.zk? and
:1
(a) there is an edge from Ai<s> to Ai<s2> and
--H F?.(x ,...x2), Xi --H Xi for i --H 1 to 1, i # :0,
? ?l k
or
(b)
there is no such edge, 5' --H 0, and x
o+ = J
F.(x ,...x ),?x'.
X:o ? :1 Zk I = Xi for i --H 1 tom, i # 5o"?
J
Ai!S]o =
for m > 0.
in i 1 n--Hl
18
i>)c ==> y?=c1J?
This is called the nthstage of the computation of
J
The haltinapoint is the first nO for
which the first, or node-, component of one clement of
the ?th???g? of the computation is 0. If n is the halting
J
point of A?(y1 .. y?) and
(x1: (O,x1,...xm) is in
has a single element we say that this element is
J
A?(y1?.. y?) and that the computation cenverges in n steps.
In this case n is called the running-time, comple?ity, cr
stepcount of AJ?(y1????y?) and written as AJ?(y1, ...y<)
J			J
Otherwise, A?(y1 .y?) and A??(y1?. ..??) are undefined.
J
Ai computes the (partial) function
J
stronglvcomputes a partial			(n) iff
Ai __________________			function
A?(x ...x ) = f(x ,			x
i			1'			m			1			a
for every Xl?? .x? and x1,...x , where m is the maximum
n
register index of A., as before. (This means that the
function computed by A?i is independent of the initial value
of any but the input registers--H that is, it does not
flatter whether the other registers are zero or not.)
It follows directly from the definitions that
defines a (partial) recursive function if A. is finite
and J recursive. Unless it is stated to the contrary, we
19
will speak only of th?s type of program, with finite flow-
chart and recursive interpretation.
For any flowchart interpretation J, under the stan-
dard conventions we nave stated, the J-progru?s are r.e.
This follows directly from the J-flowcharts' being r.e.
We denote the canonical enunerations of the nondetermin-
Jo+ J			J
istic and deter'ninistic J-prograns by A1, A2, A3,
J J			J
and D1, D2, D3respectively.
A program accepts a set S if it computes a total
function f such that
s --H fx: f(x),'O)
We extend this definition to include partial functions,
saying that f (partial) accepts s iff
S = (x: f(x) defined & f(x),'O).
zero is thus interpreted as a "reject value? wheras all
other values are interpreted as "accept values".
20
Z. L1niversalitv
A flowchart interpretation J is universal iff, for
any C5del nur?ering of the partial recursive functions, G,
there is a recursive map, h, such that for each i
i h(i)
J J
Thus, equivalently, J is universal iff D1, D2, ... is a G.N.,
and J is universal iff for every partial recursive G. there
is a D?. such that C. D?.. Say that J is nondeterninisti?-
I			?
J J
allyuniversal (N-universal) iff D1, D2, ... is a G.N.			we
conjecture that N-universality does not inply universality.*
A flowchart interpretation J is stronglyuniversal
iff for every p.r. G. there is a j such that			strongly
computes Gi. We can easily see that this kind of universality
is stronger than the first kind by looking at a universal
interpretation J, modified so that each of its functions and
predicates requires an additional argunent which nust be
zero unless the function is to return the value one. Unless
we are certain to always have a zero-valued register, this
interpretation cannot conpute anything consistently by the
one-function, so it is not strongly universal; it is still
universal, however.
*1 As J. Simon has pointed out, there is a sinple proof of
this when we restrict ourselves to single-register prograns.]
21
J J
If D is a G?del numbering then D is a Blum com-
plexity measure on it, and similarly for the nondetermin-
istic progr??s. When _ is a Blum measure, it is a sub-
measure of A?. If I c J then D1 is a submeasure of _
I			J
and similarly with respect to A and A
If t ts a recursive function, we denote by Rt
the complexity class of tunctions
(f:?N! f 5 A?i? A?i?< t a.e., f E
By R?t we mean the sane thing, but for deterministic pro-
grams only. We say that a set s of functions is r.e. iff
there is an r.e. set of numbers W such that
s = ff:N?NI f 5 Gi, i ?
where G is a G?del numbering.
Lt and Lt are the corresponding complexity classes
of languages.
This notation is all extended to sets T of complex-
ity bounds in the obvious way, e.g.,
- u ?.
tcT
The superscript J is sometimes omitted when the meamimg
is clear fron the context.
J
A t-bounded J-program is a program Ai such that
< t a.e.
--Hi --H
Ab
22
tt
orev1?Ionsano?vmoo1s
a.e.
G.N.
F.c.
iff
i.o.
lng(n)
inin(s)
p.r.
r.e.
recursive
so+to+
vo+vo+
w.r.t.
w.l.o.g.
v
a
4-
-C
u
n
Is
fis
Lxi
fxl
A?irs?
almost everywhere
G?del numbering
flowchart
if and only if
infinitely often
length of n as bit-string
least element of the set 5
partial recursive
recursively enumerable
total recursive
such that
Turing machine
vice versa
with respect to
without loss of generality
for all
there exists
if and only if
implies
proper set inclusion
set inclusion
is an element of
set union
set intersection
Cartesian product
eardinality of the set 5
function f restricted to set 5
multiplication
greatest integer < x
least integer > x
the null string
the set of instantaneous des-
criptiens reachable in one step
from the set of instantaneous J
descriptions S, by the program A.
23
i.d.
i.d. function
o+0
o+1
N2
the jtn node of Aj
instantaneous description
the identity function, ?x.x
the bit (character) zero,
as opposed to the integer
zero, 0
the bit one
all the non-null sequences of
non-negative integers
all the finite sets of non-
negative integers
end of proof
(quod erat dernonstrandun)
11.4 1(0w the Blum A:'
24			¶
Wea?
we have claimed that the 13lu,. axioms are too liberal.
Since the vigorous theory which has grown from th':m attests
to their strength (121, we would like to illustrate here how
they are weak.
The definition that Blum proposed in 1967 (I) was
essentially as follows: if G1, G2, G3, ... 15 an acceptable
Gadel numbering of the partial recursive functions and
?G1, G2, G3, ... is a sequence of partial recursive functions
such that:
(I) Gj(x) is defined iff G?i(x) is defined.
(2) The function
M(i,x,m) -
0 otherwise
is total recursive,
then the G. are stec-countingfunctions (a complexity
ineasure) for G. tThat this means is, first, that the amount
of resource used by am algorithm is known precisely when the
algorithm defines a convergent computation and, second, that
it is always possible to determine whether an algorithm
exceeds any particular bound on its resource. One can see
how it would go contrary to the intuition to admit anything
as a complexity measure that failed either of these simple
requirements.
Nevertheless, because the axioms do not mention any-
thing about how the complexity of an algorithm is related to
25
the value computed, they allow us to construct some very
strange "complexity measures". Starting with an intuitively
acceptable measure C. the step-count for single-tape T.X.s,
one may distort the measure in countless ways
Example_1.1 Let Ci C.1 Cbe a subenumeration of the
1 12 13
C?del numbering C which includes only total functions. Such
a set of functions might include all the constant functions
or all the polynonially time-bounded functions. Le?
= (iE(i1,i2,...))? 0; Ci(x))
In this measure, an infinite number of nontrivial functions
are computable "for free".
Examole1.2 Let Cc be an arbitrary T.M. Let
= ?x((i#c and Ci's control structure is
isonorphic to Cc'S as a finite
autonaton)? Ci(x)S; Ci(X))
mere, definitionally-equivalent algorithms may have exponen-
tially different "step counts".
Example1.3 Let f be a function such that f is not the
identity and
fOf ? Rt
for some nontrivial time bound t. Suppose computes f.
Define
Cj = ?x((i=j)? 0; ?Ci(X))
Thus f is "free" but we cannot apply it nore than one tine
to get f.f for less than cost t.
To see that such an f c1ocs indeed exists and is total,
define one: Start with the assumption that f is going to be
:onotonically increasing. Choose a total recursive t.
Suppose that f(x) is already defined for x 1,2, Ni
l,et r be a recursive function such that r = k i.o. for every
k in N. If
Cr(i) (Ni) < t(f(Ni))+t(Ni)
let			f(f(N.)) = min(y: y>f(N?), y#G			(N )?
I			1			r(i) i
let			Ni+l = f(f(Ni))+l?
and let f(x) --H x+l for all x s.t. x#f(N?) and
Otherwise, let f(Ni+l) = Ni+2 and Ni+l = Ni+2
These examples demonstrate that, although functions
satisfying the Blun axioms nust at least bear a remote
resemblance to what we would accept as step-counting
functions, they need not satisfy some of our basic ideas
about consistency and "fairness" in measuring computational
cost. One believes that changing the name of an algorithn
should not change the amount of computational resource it
uses. One also believes that one should be able to compose
the results of various computations without great additional
cost. We have seen how well the Blum axioms reflect such
beliefs. Doubtless, it is difficult to say exactly what
relations should hold between "cost" and value computed, but
it must be considered a weakness of the Blum axioms that
they do not in any way explicitly relate the two.
27
A fur?er exanpie, which we borrow from r121, shows
that there are Blum measures where the functions of complex-
ity zero are not r.e. This is widely held to be undesirable.
?xample1.4			Let			be an enumeration of the
constant functions such that
Define
Thus
- ?x.t
?Gj --H
x; 0); x+l)
R0 --H			t) is not defined)
If R0 were r.e. then, since G : 2
the set
(2 ? (2) is not defined)
would be r.e. This set is well known not to be r.e., a
contradiction.
28
11.5 ?.ondete=?nism--HComments on ?efinitions
From ?l.3, it should be evident tnat our definition of
acceptance, particularly nondeterministic acceptance, is
not standard. This is not by caprice, but is part of a
deliberate attempt to correct disparities in the traditional
definitions tnat prevent ccrtain notions we feel are related
from fitting into a unified definitional framework.
We are concerned that definitions dealing with the
notions of set recognition, function computation, determin-
ism, nondeterminism, and computational complexity should
satisfy the following principles:
(1) The class of nondeterministic algorithms (acceptors)
includes the deterministic algorithms (acceptors).
Consequently:
(a) All terms meaningful in the deterministic case
should have meaningful generalizations to the non-
deterministic case (e.g., re?ecting should be
distinguishable from not halting).
(b) Definitions should consistently treat the deter-
sinistic algorithms as a restricted case of the
nondeterministic algorithms, i.e., the set accepted
(or function computed) and the running time of a
deterministic algorithm should be independent of
whether it is viewed as a nondeterministic
algorithm or as a determimistic algorithm.
29'
(2) Recognizing a set amounts to computing a (partial)
function (of at least two values, by (la) above).
Consequently:
(a) Complexity measures for acceptors should satisfy
the Blum axioms, when the acceptor is viewed as
computing a (partial) function to
(accept, reject].*
(b) The complexity of accepting a set should not be
greater than that of computing its characteristic
function.
(c) Recursive sets?should be recognizable by algorithms
with total complexity functions.
In the interest of brevity, we omit the extensive philosoph-
ical justifications, based on intuition" and specific
examples of "real" computation, that could be given for
these principles, trusting that the reader will join us
in accepting them as self-evident.
Every one of these principles is violated by what,
up to now, has passed for the "standard" definition of non--H
deterministic acceptance [15, 17]. According to custom,
a nondeterninistic algorithm accepts" an input iff one of
the computations it defines accepts (by whatever definition
of acceptance is used in the deterministic case). The
"running time" is the running time of the shortest accept-
In the nondeterministic case it might be desirable to
weaken the first Bl?¶ axiom to say that G. (x) is defined
only if G. (x) is defined. This may be ju?tified infor:',-
ally by ?s?ying that the computing device may "jam", due
to an inconsistency in the output.]
30
ing computation.* This fails (la) because there is no way to
reject an input. It fails (ib) and (2a) because a determin-
istic algorithm may halt and reject, having finite running
time, wheras the "running time" of the same algorithm, viewed
as a nondeterministic algorithm, is undefined. (2b) and (2c)
are failed for the same reason.
We incorporate principle (2) into our definitions
very simply, saying that an algorithn acceots a set s if it
computes the (0-1) characteristic function of S, or by
extension, if it computes a (partial) function f such that
S (x: f(x) defined and #0).
Any Bl?m measure on the complexity of computing functions
is thus also a measure on the complexity of accepting sets.
It should be clear that this is close to the usual defin-
ition of acceptance for deterministic natural models of
computation, such as Turing machines, in the sense that an
accepting algorithm according to the usual definition may
be transformed recursively into an accepting algorithm
according to our definition without more than a constant
increase in the complexity. It remains for us to define
how a nondeterministic algorithm computes a function in
such a way that nondeterministic acceptance also has a
meaning close to the usual one.
*[ This definition L? adequate for "real time" or other
fixed-bound computations, where the running time is always
defined and rejecting means halting without accepting.]
31
Define a comoutation to be an initial value and a
sequence (possibly infinite) of functions, called ooerations.
Thus each computation defines a unique sequence of (intermed-
iate) values, starting from the initial value and applying the
successive operations of the conputation. An algorithn is
a (partial) function which gives a set (possibly empty) of
operations for each value1 thus defining a computation or
set of conputations for each initial value. The algorith.¶ is
deterministic it there is at most one permissible operation
for each value. A (nondeterministic) algorithm defines a
tree of computations for each initial value. If the algor--H
ithn is deterministic then the tree is a simple sequence.
Let there be a (partial) function from the values to the
outputs, which gives the result of a computation from its
final value. Let there be another (1-1) function from the
inouts to the values, giving an initial value for each
input. The function comouted b? a deterninistic algorithm
A on input x is the result of the computation defined by A
on the initial value for x if the computation is finite.
So far, we have merely fixed a terminology for
notions about which there is widespread agreement.
Wnen we come to extend this notion of computing a function
to all (nondeterministic) algorithns, we run into uncertainty.
Clearly, a single nondeterministic algorithn and initial
value may define an infinite number of terminating comp--H
utations?. How do we define an output from the results of
all these computations? We start by making a choice:
First, we may allow all terminating computations to con-
tribute to the output. We reject this because it implies
that the "output" and "running time" may be infinite (not
inherently a bad idea, but out of keeping with our desire
that the output be a (partial) recursive function of the
input). The alternative is to (explicitly or implicitly)
define a "cut-off time" by which a computation must have
terminated if it is to contribute to the output. Intuitively,
suppose we view the nondeterministic computing dev?ce as an
infinitely-expandable network of independent computing
devices, each one adding a copy of itsslf to the network
whenever it is faced with a choice and passing on its result
to a central output device when it terminates a computation.
Having a cut-off means that the output device listens
to all the results it gets up to a certain poi?Lt, whereupon
it decides to put out something. Naturally, all results of
computations terminating after that point cannot contribute
to the output, and we might just as well assume that all
computations are cut off at the time of output.
No matter how good a cut-off criterion we choose,
we must still occasionally face the problem of defining an
output when several computations terminate simultaneously
and produce inconsistent results. We call this problem
a".?iguity. The simplest action we can take is to give up,
saying that the output is undefined unless all computations
terminating by the cut-off time produce the same result.
33
uecause this is simplest, we believe it is preferable to
any ad hoc rule for resolving ambiguity,* assuning that an
unambiguous output is required*.
Having chosen to leave the output undefined when the
computations terminating by cutoff time are ambiguous, and
faced with a multiplicity of possible cut-off rules, two
extromes bockon to us. On the one hand, we could strengthen
the policy of exclusivity we have followed in ignoring
ambiguous results, letting the "cut-off" criterion be that
there be no unterminated computations rema?ining to cut off,
thereby minimizing the number of algorithm/input combinations
producing output. On the other hand, we could try to rrax-
imize this number, cutting off all computations when first
some computation terminates. We choose the latter policy
because the definition of nondeterministic acceptance it
gives us is closest to the traditional one, even though we
believe the stronger policy surpasses it in elegance.
*( For example, choosing the least of the results defined
by the terminating computations.]
t[ Of course, it would be most natural to allow for ambig-
uous outp?2t, interpreting the alcorithms as defining set-
valued rather than integer-valued functions. However, the
prospect of saying the detorministic algorithms define
(partial) functions from N to t?n]: nEN) is not appealing.
The partial recursive functions are traditionally from N
to N, and identifying n with fn) is inconsistent.]
t[ In certain cases, especially when the algorithms are
specified to have built-in "clocks", intermediate cut-off
policies may be preferable.]
34
we have thus madt three decisions which, tegether with
the two principles we stated earlier, completely shape our
definitions:
(1) There will be a cut-off time for each algorithrn/input
coT.?ination that produces output.
(2) If any algorithm/input combination produces anoiguous
results no output will he defined.*
(3) An algorithm will be cut off for a particular initial
value when first one of its conputations terminates.
Although some compromise has been made in (2) and (3)
between elegance and compatibil?ty with previous work, we
feel that any framework in which we can simultaneously
discuss accepting sets and computing functions, deterministic-
ally and nondeterministically, along with the associated
complexities must be better than the jumble of disparate
notions we started with.
*[ This means the running time must also be undefined, by
Blum's first axiom, if we wish to satisfy the Blum axioms
fully.]
f Com?lexitv Cl?
2 tnumerab?iitv0
?2.l Ceneral
We have shown, in Example 1.4, that certain ?lum meas-
ures have non-r.e. con?plexity classes. This property may be
deemed undesirable, since all complexity classes are r.e. in
the natural measures we traditionally use as examples. It
has long been known that non-r.e. complexity classes must be
low in the hierarchy of classes when they do exist. All
classes larger than the first class to include all finite
variants of some function must be r.e., as the following
lemma indicates.
34A
35
Le=r?2.1 In any ?lum measure G on G?del numoering G, if
there are total recursive functions f and t such that for
every total recursive function g
g			f a.e. ==> g E Rt
then R is r.e. for.every recursive function r s.t.
r
r > t a.e.
Proof For each (i,j,k) in Nx?xN let
f(x) if there is a y such that
y < j and G?i(y) > k
G (x)			-
or ? < y < x and G?(y) >
Gi(x) otherwise.
If Gi  R.r then there exist ? and k such that
G			Gi
Unless Gg(?,j,?) f a.e.,
Gi(y) < k for y < j and Gi(y) < r(y) for y > j
and so
Otherwise
Thus if
C Rr
 Rt s Rr
((it?it?kt))t=l
enunierates NxNxN then is enumerated by
(Gg(i&?jL?k&) ?t??
Q.E.D.
36.
Example2.2 For any measure G on G there is a t such that
the identity function and its finite variants are all in Rt
To see this, start with an encoding of the finite subsets
of NxN as integers,
K --H ?s((s=?)? o+ll?;
o+ll'c(min(s))?(S--H(min(S))))
c --H ?x((x=?)? ;
(x--Hy?O')? c(y)'lO';
(x--Hy'l?)? c(y)'Ol ),
--H ?x,y(x'lO?')
and use it to define an enumeration of the finite variants
of the identity function,
Gy(i) --H ?x((i--H?(S) & <x,y>(S)--H--H--H? y; X)1
in terms of which we define
x
t --H ?x( ? G?Y(i)(X) )
i-i
37
12.2 ConstantBounds
Theorem2.3 or any (finite) clowohart interpretation J the
J
A
constant comple:<ity cLasses ?x.k are r.e.
Proof Tf f is a function in Rtx.k then there is a finite
tree-program A?. which computes f. Any change we may make in
J
A. which is more than k nodes away fron the root cannot change
w?ether the function computed by the program is in RtA.k#
lenyth ?r?atar
since it does not change whether any paths of
than k are followed infinitely often. Thus, startLog 4ith
a k-height tree-program, we may add on whatever suprograna
we wish to any of the nodes that arereached for only finitely
many inputs, and still have a program computing a f-unction in
R?x.k Conversely, any function in RAx.k may be "otten by
adding finite tree-programs to a k-height tree-program in
the sane nanner. Therefore, the only problem "e face In
enuTerating ?A?Jx.k is knowing for each k-height J-program
which nodes may be reached only finitely often. We solve this
by observing that whether a node may be reached for ininitely
many inputs depends only on the sequence of function and
predicate steps on the path leading to it from the root.
There is only a finite number of these sequences; let the
(finite, although not necessarily r.e. w.r.t. k)
set of k-operation sequences that are followed for only
finitely many inputs be called Ek Enumerating RAx.k
reduces to enumerating the permissible combinations of
38
a k-height tree-progran,
a finite set of paths with operation
sequences in Ek and
and a finite set of tree-programs,
which is clearly recursive.			O.E.D.
Corollary2.4 Por any F.C. interpretation J the (constant-
bounded) complexity classes R?t are r?e., for t recursive
and bounded in macjnituda by some constant k.
Proof As in Theoren 2.3, start with the set of tree-
programs that are bounded by t everywhere and add on other
tree-programs for paths in ?k
39
?xamole2.5
Zf k --H 3, J --H ((2),(?, m)), z =
?= ?x(x+l),
and			m = ?x( x$O---? x-l; 0)
then the set of k-operation sequences which can be followed
for only finitely many inputs, Ek is
Pm2, mpz, mmz, m?, , zno, zzn,
mzm, zpm, zrnm, zzrn,
mzz, zp:, zmz, zzz,
zmz
This means that the 3-height tree program
I:			2 1
2: I p?l			3: 1 m I			4: I m I
0			+0
5:			2 1			6:			2 1			7: 1 m 1
may have any finite tree-program added by a 0-edge from
node 5 or a 1-edge from node 6 without changing the
complexity class, but any other addition at level 4 will
change it.
?2.3 Ul
imatel Increasin Bounds
We have just shown that the flowchart complexity classes
are r.e. for constant-bounded complexity bounds. It is also
possible to prove that they are r.e. for ultimately increas-
ing bounds.
40
Theorem2.6 If J is a universal flowchart interpretation
and t is an ultimately increasing recursive function, then
J
the complexity class RA? is r.e.
t
Proof			Since t is ultimately increasing, we know that Rt
includes all the functions computed by finite tree-programs.
We modify each J-program to conpute a function computed by
a finite tree-program if the time bound t is exceeded often
enough.
Take ((ji'ki)) to be an enumeration of NXN; define
i=l
if ?J(y) <			or			< t(y)
--H ki A??(?)
Mi(x) --H			for every y < x;
(x)			otherwise, where
n --H max( A?(z): A. (y) < k. or A. (y) < t(y) if y < :
--H?			?i			--H 1
and AT(?,n) is the finite tree-program containing a1l?paths
in A. of length n or less (see Example 2.7). Mi computes
if
> k.			A?.(x) < t(x)
and conputes a function of finite complexity otherwise.
If f is in Rt then there is a ? such that A. computes f
and for some k
x > k A?.(x) < t(x).
Mi computes f when ?i is j and
ki --H max(A?.(x): x<k).
41
Thus			??i?i?? enunerates			If J is uni?ersal this
enuneration may be translated recursively into a
J
subsequence of A
xam le 2.7
If A. is
then AT(j,S) is
iri
2:
jro3: ?l ?4: IHI
O.S.D.
1: IFi
In
2: l?l			3:
4: l?l			5: l?l			6:
ltl			6: l?l			9: ?l			10:
7:
12: lPTm3:l?l 14:			1			15:			1			16: lAl 17:
?lC
Pi 11: iAl'
18:
The following theoren is a weaker version of Theorem
2.6, given because it uses Lemma 2.1 and beca?se the
technique is illustrative of the kind of manipulation
possible on flowcharts.
42
Theorem2.8 If J is a universal flowchart interpretation
which includes the identity function1 t = ?x.x1 then the
complexity classes Rt are r.e. for all ultimately increasing
recursive t.
Proof 8y Lemma 2.1 we need only show that the identity
function and every finite variant of it are in Rrx.kl each
one for sone constant k. Clearly the identity function is
in Rtx.O It will be enough to show that every function f
which is equivalent to the identity except at a single point
is in sone R?x.kl since any finite variant of the identity
function is expressible as a finite conposition of these.
We will describe two transfornations on flowcharts1
e and Tkl which are recursive.
8 alters flowcharts so as to guarantee that, as
programs, they do not destroy the contents of the input
register until the final operation; yet still compute the
sane function. A flowchart A. is transformed by first
changing the result register index of every node with result
register index 1 to the index n, where n-l is the highest
register?index appearing in A.. The edges leading from
these altared nodes are then connected to the correspond
ing next nodes in another copy of A. in which all occur-
rences of 1 as a register index have been replaced by m.
To each terminal node of the copy of A. a link
is added to a new node 1 1 ? n. The final flon?hart, Ae(i)a
is functionally equivalent to A., but never alters the
43
value of register I until the last step. All computation-
al paths are at most one step longer than in A..
(See Example 2.9.)
Tk transforms a flowchart into a tree of height k,
so that for all paths of length k or less the operations
are the same, and no paths of length greater than k
exist. (See Example 2.9.)
If Ai computes a p.r. function equivalent to the
identity except at one point, y, then A. A. for
3			1
i = TA. (y)+l(e(i)), and furthermore, A.(x) <A. (y)+l
--H?			--H1
for all x.			Q.E.D.
Example2.9
AT5e (i) --H
F 1			Ae(i)--H
1 G I
?2?M
1: 2 F 1
2: ??2?3: 3
4:			2 ?O2			9: 2
5:			?`2			10:
7:			2 ?0l			6: 2
8:
10
11: 1'			3
Gl
?`2?ll: l?? 3
`4
Theoren 2.6 and Corollary 2.4 leave an obvious gap in
the classes of time bounds for which the flowchart complex-
ity classes are known to be r.e. So far as we know, it is
also an open question for Turing machine time whether the
complexity classes bounded by non-constant-bounded non-
ultimately-increasing functions are r.e. This is because
the T.M. is generally assumed to read its input, which
would require at least linear tine. However, there is no
solid reason for this, since certain regular sets, such as
1t( ? + 1 ) , are acceptable in tine < lng(x) for many inputs
3 T?5n5j5t10n5
?3.l BetweenFlowchartInterpretations
Diverse as the flowchart interpretations may be, it
is always fairly simple to translate programs from one
interpretation to another.
Theore?n3.1 For any two flowchart interpretations I and J,
if J is universal and I finite, then there is a lng(lng(x))--H
tape-bounded Turing machine which translates the I-programs
1-1 into equivalent J-programs in time O(lng(x).lng(lng(x))),
where x is the encoded I-program and lng is the bit-string
length function.
?ote: A Turing machine as used in tape-bounded computation
has finite control, two-way read-only binary input tape,
and read-write work tape with finite alphabet. In the
present context we allow it to serve as a transducer by
optionally putting a 0. or a `1' out onto an output-tape
for each control-state transition.
Proof Intuitively, each node of am I-program is replaced
by a J-subprogram. Since J is universal, there is a J-
program for every function of I. similarly, J must have a
nontrivial predicate 0 such that Q(a)=O and Q(b)=l for some
J
a and b. For each predicate P of I there is a program Ai
which computes A?i(x)= a if P(x)--HO and A?i(x)- b otherwise.
The J-prograin represented by
45
46
(oAr
-k?: 0 l?I
created by adding the predicate-node k: 0 1 to the
flowchart Aj in terminal position, is operationally equi-
valent to the Z-predicate P in the sense that the 0-edge
will be followed iff P is 0 on the contents of register I.
By substituting register indices not used anywhere in the
rest of the program for all the register indices local to
Ai this program segment, or subprogram, may be modified
so as to have the sane effect as P would when applied to
register j. We thus have a J-progran which is operationally
equivalent for each function or predicate of I. These may
be inserted in a J-program, with certain modifications of
register index and the addition of entering and leaving
edges, so as to have the same effect as if the corresponding
I-operations were inserted.
We would like to?say, without loss of generality,
that these J-program counterparts to the operations of I
(called translation patterns) are well behaved in certain
ways:
(1) They do not alter the contents of the input register
(which we shall still assume is 1) and they use some other
register as output register. (If the programs we have are not
already of this form, then they can be made so, without
changing their complexity, by a transformation similar to
47,
the 8 described in the proof of Theoren 2.8, omitting the
final transfer of the output back to register 1.)
(2) All register indices are of the form iOn., for
various n.
(3) The patterns all have the same number of nodes, this
being 2m for some fixed m. (Add inaccessible and useless
nodes if necessary.)
With the flowcharts of the I-programs encoded as
binary strings (see Chapter 1 for encoding), a Turing
machine nay translate them into flowcharts of equivalent
J-programs node by node, A well-formed?flowchart descrip-
tion is a se?uence of node descriptions. Each node
description consists of a function or predicate term, with
register indices, followed by lists of the 0 and 1-edges
from the node, gi%en as displacenents in the flowchart
description. Because the well-formed descriptions are a
regular set, a finite automaton may recognize the malformed
descriptions, which may be translated trivially as them-
selves, since each malformed description represents the
null flowchart. The transducer replaces each node of a
well--Hformed flowchart description by a sequence of nodes
generated from the appropriate pattern (which is stored in
its finite control). ?odifying the indices of the input
register in the source node by suffixing a 1', it substi-
tutes them for the indices of the input registers of the
pattern, wherever they occur. In the case of the function
48
nodes, it substitutes the similarly modified index of the
result regist?r of the source node for the output register
index of the pattern. The other registers local to the
pattern are ?iven unique indices, obtained by suffixing the
register indices of the pattern to the index of the source
node being translated (i.e., o+10n, becomes k.10n. in the
translation of the kth source node). Tha edges of the
pattern nodes are suffixed with o+0m1 to allow for the
expansion which has taken place.
In doing all this the Turing machine would be per-
forming notning nore than a finite-state transduction, were
it not for the problem of local registers (which disappears
if J is strongly universal--H see following corollary).
Xeeping local register indices unique makes us count the
number of nodes translated. This requires at most lmg(lng(x))
tape for input x. To put this out, when we need to, as
part of a register index takes about lng(lng(x)) steps.
Although this happens ?t most a constant number of times
per node, there may be about lng(x) modes in the input, so
the running time is pushed up from O(lng(x)) to
O(lng(x).lng(lng(x))) for input x.
As to the translation being 1-1, that should be clear;
if it is not, then it is s?npler to make it clear by
encoding the original program in the form of an extra node
than by going over the translation process again in
detail.
49
Corollary2.2 If I and J are two flowchart interpretations
such that J is universal and
A1			A?
(1) I is finite and, for every recursive t, R?t c , and
(2) each constant function ?x.k is included in A for
some other constant function ?,
then there is a translation a, computable by a lng(lng(x))-
tape-bounded T.M. in time O(lng(x).lng(lng(x))) (where x
is the input), and a constant c such that for every j
A1			and			A?			<			c.A1.
a(j)			j			a(j)			--H			--H?
Proof From (1) we know that we can get translation
patterns for the functions of I which are of complexity
1 a.e. The predicates, however, do not compute functions
in themselves. Thus, in order to apply (1) to show that
the translation patterns for the predicates of I are also
of some bounded complexity, we use (2) to convert them into
prpgrans which compute functions. For each I-predicate p
and some constants a and b, there is an I-program
l:
P l?i>( a
to
A)
(where A and a compute the constant functions which are a
and b respectively, computing a when P is 0 on the input and
computing b otherwise. By (2), this progran is bounded in
complexity by a constant dependent only on a and b. This
function must be computable by a J-program of lesser o+r
equal complexity a.e. Since there are a finite number of
so
these programs for the var?ous predicates of I and they are
all bounded in complexity by a constant a.e., we cam remove
the a.o. condition and make the constant independent of the
predicate as well. The same thing can be done for the
function patterns.
Following the translation procedure of Theoren 3.1
we see that the complexity of the translated J-program is
bounded by a constant times the complexity of the original
I-program.
If J were strongly universal we could require that
the pattern programs compute the same functions regardless
of the contents of the non-input registers which they use.
Thus the need for unique local register indices vanishes1
and with it the need for any nontrivial storage capacity.
The following stronger version of Corollary 3.2. them holds.
Corollary3.3 For any flowchart interpretations I and J,
if J is strongly universal and conditions (1) and (2) of
Corollary 3.2 hold, then there is a translation a, conput--H
able by two-way (read-only) finite-state transducer, and
a constant c such that for every j
Al.			and			A?			<			c.A?.
0(j)			?(j)			--H			--H?
Notes:
(1) A finite state transducer here is a finite automaton
that can optionally put out a .0' or a `1' with each state-
transition. By two-way it is meant that the automaton may
51
back up on its input (and thus is not operating in "real
time").
(2) Having a zero-function implies that a flowchart in-
terpretation is also strongly universal.
Theorem3.4 If I an? J are two infinite flowchart inter-
pretations it is possible that there is no recursive trans-
lation taking I-programs to J-programs of lesser or equal
complexity, even if an equivalent J-program of the same
complexity exists for every I-program and I and J are
universal.
Proof we construct I and J to force such a translation
to solve the halting problem. Let I and J have the same
functions and predicates, but let certain ones of them have
different names. Let both include the zero-function under
one name. Let I also include, for each i, a function
--H ?X((Gi(l) > x)? 0; 1)
Let J also include these functions, but named differently,
as
--H ?x((i > x)? 0; 1)
It follows that if we can translate every program
I: I ?i 1
into a I-step J-program (i.e., one of the or the zero-
function) then we can decide the halting problem fro all
Gi ( on input I ), which is well known to be undecidable.
52
Rerrark: If I and J are further restricted, allowing them to
have only successor, predecessor, and zero--Htest (or some
other well-behaved" finite universsl set of f?nctions and
predicates) in addition to the zero-function and the ?i? or
then one can say even more about the difficulty of
translations from I to J. If there were a translation which
were both recursive and took I-programs into equivalent J-
programs ofcomplexities linearly related to the complexities
of the original I-programs then, the programs
1: 1 f. 1
would all be taken into J programs of some fixed-constant--H
bounded cor?lexity. It would then be possible to transform
them into finite tree-programs of constant height.
With a simple enough interpretation J, one should be
able to decide whether such a program ever computes a non-
zero value by examining the finite number of possible
sequences of k operations allowed by the program. This is
possible for the interpretation we have given and many others.
It follows that for such interpretations there is no trans-
lation computable which does not slow down some algorithms
by more than a linear amount.
53
13.2 ToFlowchartInterpretations
Theorem3.5 ?or any G?del numbering G and universal flow-
chart interpretation J there is a 1-1 translation fror..
to D? computable by a lng(lng(x))-tape-bounded T.?. in time
O(lng(x) .lng(lng(x))).
Proof Intuitively, an algorithm G. is translated into a
sequence of operations which encode i, followed by a uni-
versal program. Since J is universal there are J-programs
D?i0f D?i2v and D?i to compute the functions
3
?x((x#?)?			x'OO';			?)
Ax((x#)?			x'lO';			) , and
?x((x?)?			x'll';			c)
J
There is also a "universal" program Du to compute the
partial function
?x((?<i,j>)?
where			<i,j> --H i'll'e(j)
and			a --H			?x((x=E)? c;
(x=y'l')? o(y)?lO'
(x?y'O')--? 5(y) `00
J
If j--Hj1j2...			(as a bit--Hstring) let DT(?) be the composition
D? (D?			(... D?.			(D) ...)),
i3 i5(j1)			10??k?
which computes G. by encoding <i,3> from input i and applying
D?u Producing DT(j) from j involves simply writing down a
copy of D. followed by a copy of D. or D. for each bit of
13			1			1
2			0
I			54
j and, finally, a copy of Du, making sure that the registers
of each subprogram have unique names. We may assume without
loss of generality:
(1) all the suhprograns use the same register(s) for input
and output;
(2) each subprogran has a single terminal mode with 0--H and
1-edges to a (hypothetical) node following the last node
of the subprogram, which is treated as a null edge in the
absence of such a node;
(3) the sets of register indices of the suoprograms
and D are dis3oint, except for the input-
13			1			1			u
2			0
output register(s);
(4) the register indices of D. and D are of the form
12			10
o+10n for various n and the register indices of D. and Du
13
are of the form x'l for various x.
If the flowcharts do not satisfy these conditions we can
change then so that they do, without changing the function
conputed.
Translating j to T(j) would be even sinpler than the
translation process of Theorem 3.1 (since we do not have to
back up to copy out register indices), were it not that the
various copies of n. and D might interfere with each other
10			i2
(by leaving non-zero values) if they had any but input-output
registers in cornrnon. Keeping these unique, by counting bits
of j and substituting tx for every register index x of
requires lng(lng(j)) tape and boosts the time by a
55
factor of lng(lng(?)) over lng(j), the length of the input.
Because of the direct way in which j is encoded, it
is obvious that the translation is. 1-1. Q.E.D.
Corollary3.6 For any C?del nurr?ering G and strongly
universal flowohart interpretation J there is a 1--H1 trans-
lation from G to D? conputable by (one-way) finite-state
transducer.
Proof Knowing that J is strongly universal allows us to
require that the D13			12			10 and Du be insensitive to
changes in the initial values of any but their input
registers. The assigrinent of unique register indices is
no longer necessary and the translation technique of
Theoren 3.5 gives the stronger result. O.E.D.
56'
?3.3 BetweenG?delNumberings
Loosely speaking, the preceding two results say that
the flowcharts make a good universal target language for
translations (supporting our assertion that they are a
natural class of G?del numberings on which to base complex-
ity measures, and indeed worthy of study)'. The next theorem
shows that many G?del nuTberings are worse-behaved as
targets than the flowchart G.N.s and that we cannot say
much good about any G?del n?¶bering as a universal trans-
lation source. It is a'weaker version of a theor?? which
we prove in [11] about "optimal" G.N.s.
Theorem3.7 For any G?del nur?ering G1 complexity measure
G, and recursive function t, there is another C;?del nu?ber--H
ing ? such that any translation from G to H must be of
complexity greater than t.
Proof The desired H is defined as a recursive permutation
of 0 by an inductive diagonalization over the possible
translations 0k Let (o. ?i=l be an r.e. sequence of con-
stant functions such that for every ?
0 = ?x(i) and
n
We know that such an enumeration exists by the 5n theorem.
0
Let (0 )			-			be a recursive enumeration of k--H., where
k. i=l			t
1			0
> t and R?t includes all finite-variants of the zero-
0
function (see Lerr?a 2.1 that Rt is r.e.). By the jth
stage ?l'? HN are assumed to have been defined. We define
57
RNi+li????\i+l as follows: L?:p?te o+(?t? for
until one of the cllowing cases holds:
[lJ (Gki(iL) > `??): Let n = (n: n>2, in>Gki(i?))?
i+l --H
1! =
Gk (??)			?n
1(?n = GGki??L?'			and
for Nj< ? --H< Ni+l, ? # Gk. ??t? and j $ ins
-(;
fi			--H G = ?x.n ?			=
???1i?			in
?21			(L > 2.Ni):			Let Nj+1 =
and If. = a1 for N < i <
j --H1
Then for sone I and n < t5 and such that n ,`
???1n?			Gki(in)
HGki(in) = HGki?1n?'
and so if Ifa C (as G.N.s) we have
ki
?x.m 5 G11 = ?Gk.(im) 5 If = ?x.n
1			Gki(in)
Clearly this halts, at the latest when & reaches 2?Ni+l
and it always produces a contradiction from H G O.E.D.
Gk.
59
Lemma?.S For any measure G on G?del nurnbering G there is
a recursive f such that for any recursive g and t,
____			--H1
g c Rt			g			RfOt
where g?1 denotes
?x(minfy: g(y)
Proof We proceed by a series of "claims" which are
"obviously" true, but some ?ustification is sketched for
each.
claim1 There is a recursive a such that includes the
identity function and all its finite variants. (This is
shown in Example 2.2.)
claim2 There is a recursive v such that for every total
0.
?0y(i,?)?2'=l =R0
(Let f(mi?ni))i?1 enumerate NXN s.t. (m?,m?)=(k.i) i.o.
for every (k,t) in N?N. Define
Oy(i,j) --H ?x((?(y)<a(y) or ?(y)?<G?(y) for every y
3 3
such that m1< y < x)
0 (x);
Thus 0
y(i,j) computes a finite variant of the i.d. function
unless 0. is not total (in which case 0y(i,j) is a.e.
undefined), unless
< 0?(i) a.e., where
59
GS(i) --H Ax(max((a(x),G?(x))))
claim3 There is a recursive ? such that
--H1
for every j.
(Define --H Ax(min(y: Gj(Y) x)) .)
We can now define
x
--H Ax(nax( ?(Y(i,?))(X) ))
i--HI
so that
Gj ERGj ?			(j)  RfGj
Q.E.D.
60'
Corollary`.9 For any complexity measure G on Gb'del
numbering G and any recursive t there is a G.N. N such
that all isomorphisms from ? to G must be of complexity
greater than t.
Proof Suppcse no such H exists, i.e., for every H
there is a t-bounded isomorphism from H to G. Applying
the preceding lemna we see that			there is a translation
from G to H of complexity f(t).			This contradicts
Theorem 3.7.			Q.E.D.
This is in contrast to:
Corollarv3.10 For?any two universal F.c. interpretations
I and J there is an isomorphism from A1 to A? computable
n
by a T.M. in atmost 0(2 ) steps on input n.
Proof This follows immediately from a coarse analysis
of the time required to compute an isomorphism by the usual
"back and forth" method from the two 1-1 translations
guaranteed by Theorem 3.1.			O.E.D.
Remark The time analysis here is verv coarse. We
conjecture that the actual bound should be polynomial.
i Nondetermin?s?
14.1 Discussi?n
Questions about the precis? complexity relations between
nondeterministic and deterministic models of computation have
bedeviled computer theorists for a long time. This family
of as-yet-unsolved problams traces its origin back to the
question whether nondeterministic and deterministic linearly-
bounded a'?tonata accept the sane family of langua?es--Ha sub-
ject of conjecture since 1964, when Kuroda (18] showed that
the family of languages accepted by the nondetermin?st?c
limearly-bounded autonata is exactly the fa:r.ily of context-
sensitive languages. Hartmanis and Hunt [13] explain the
importance of this question and other problems related to it,
leading up to the more recent question whether tr?u ramilies
of lan?us?es accepted by the nondeterministic and deter??tn-
istic T.H.s in time polynonially bounded w.r.t. the len?th
of the input (frequently denoted by NP and PI are the sane.
As cook [6] and, later, Karp [171 have shown quite
well, there is a large class of problems of practical inter-
est which are solvable by nondeterministic Turing Machine
in polynomially-bounded time. These problems include
satisfiability for Boolean formulae in conjunctive normal
form and several problems dealing with graphs, such as finding
the chromatic number and detecting a Hamiltonian circuit.
The surprising thing is that these problems are all inter-
reducible by deterministic Turing machine in polynomial
61
62
time and can be shown to have deterministic polynomially
time-bounded solutions only if NP=P.
Questions such as these and others relating to nondet-
erminism have taken on a new interest with recent efforts
toward parallelism in computing hardware. Nondeterninism
in computation formally expresses a notion that can be viewed
intuitively as infinite parallelism. Although it is not
always true that what holds for the infinite must also hold
for the finite, there is at least a conceivable real model
for sucI? parallelism in an indefinitely-expanding network of
tape-equipped minicomputers. Even if there is not a precise
real-world counterpart to nondaterninistic computation, it
might be wise to ask whether anything can be gained by non-
determinism before we ask the same about finite parallelism,
since theory often is more effective in dealing with the
infinite than with the finite.
The flowchart measures lend themselves well to dis-
cussion of nondeterminism, the distinction between deter--H
ministic and nondeterministic programs being a simple
difference in the structure of the flowcharts, and thus
independent of the interpretation. In this context we
may generalize Cook's (6] question, ?P=?P, to \DP=?DP,
where hDP and DP are the families of languages acceptable
nondeterministically and deterministically by computations
bounded polynomially with respect to the length of the input.
63
As the followin(J theorems show, there is a large class of
sets T of time-bound functions (including tne set JI of
polynomials applied to the input length) where whether
A?			D?
T
is provably dependent on the flowchart interpretation J.
That is, there are some flowchart interpretations where
NDP$DP and there are others where NDP=DP. Interestingly
enough, the latter interpretations are not recursively
emumerable as a olass of sets of functions and pre?ioetes.
In fact, it is a consequence of Mehlhorn?s work 23] that
the set of predicates (P: an interpretation possessing as
much computational speed as a single-tape T.M. may include
P and still have aDP=DP) is meagre in the space of
recursive functions.
Based on the observation that whether NDP=D? for
flowcharts is dependent on the interpretation, we remark
that an answer to this question for a specific natural
measure, such as Turing machine time, will have to rely
heavily on the peculiar local properties of the measure.
The fact that the class of interpretations where NDP=DP
is mon-r.e. and "meagre", together with the work of Cook
[6] and Karp [14], leads us to conjecture that for inter-
pretations of practical interest NDP?DP.
14.2 NDPandDPfor..Flewchart`.¶easures
The following theorems and corollaries deal with the
relations between nondeterministic and deterministic
complexity classes for flowchart measures. Theorens 4.1
and 4.2 begin by showing that, for large enough time-bound
classes T, it is dependent on the flowchart interpretation
whether nondeterminism permits anything to be computed that
is not also computable deterministically.
With regard to Coo'??s !6) NP=?P question, it should
be noted that the classes NP and P were defined in terms
of th? traditional notions of acceptance, and in the
context of Turing machine and random access machine measures.
On the other hand, ?DP and DP, our corresponding generalized
classes of nondeterministic and deterministic polynomially--H
acceptable languages, are defined in terms of our own
version of acceptance. seemingly as if to obfuscate
relationships further for those interested in the ?P=?P
question, some of the theorems are stated in terms of
complexity classes of functions. ?T The latter really
should present no difficulty, since the recognition
problem is a special casa of computing a (characteristic)
function. However, the formar confusion is more subtle
andmight be misleading did not the ability of the Turing
machine and like models to adapt from one definition of
acceptance to another without more than polynonial change
in complexity permit us to treat NDP and DP as consistent
generalizations of N.P and P.
65
Theoren4.1 For any flowchart interpretation J and any
r.e.			class T= (t.:			of recursive conpiexity bounds
containing a tj S.t.
[Hli for each ??1T' 2ti(X)>t.(x) a.e.,
[H21 there is a jEIT 5.t t (x)>5?t.(x) a.e., and
[H3j tj is a.e. increasing,
there is a flowchart interpretation J', gotten from J by
adding a finite number of unary predicates and functions,
for which
?
T T
Proof We will exhibit a set x that is accepted by a
nondeterninistic T-bounded ? -program, but not by any
deterninistic T-bounded J'-prograrn. Intuitively, x is a
diagonal set over the sets accepted by deterministic
T-bounded J?-prograns. We want to be able to accep? x
with a nonde;terministic T-bounded J'-program. Assuming
J' allows the necessary arithmetic operations, we know
that if we ha4e a predicate e in J' we can use e on all
numbers less than or equal to 2ti(x) in approximately
ti(x) steps nondeterninistically. We will define e so
that it tells us whether a given point is in X, but only
by examining e on all points in the interval
Sm (2ti(X?l)+l,...2ti(X)) will we be able to get this
information, since e "hides" the point in this interval
66
where e i 1 so well that no T-bounded deterministic J'-
program can find it.
More formally, define x to be the set
fn: SnflE=%? n>l)
where E is the set accepted by the predicate e, which we
shall define later. (The letter "E is used for this
predicate-set since it might be thought of as am
exponential j)xansion of x.)
To be certain that we can write a nondeterministic
T-bounded J'-program to accept X, we let J' contain the
following functions and predicates, as well as any others
included in J:
zero			=
adl			=
sufO			=			?x(2 x)
codl			--H			?x((t.(x?l)+2)ilOXi);
cod2 --H ?x((x=y'l05, &
0);
dec --H ?x((x-y'l02 & y#0)?((y--Hl)?lO51); 0);
=			?x(x=?l0Z & zN);
-			a predicate to be defined later.
The following J -program accepts x in 4. (ti(X)+l)
steps or less, and thus is T-bounded, by ;`2.
1:			1 codi			1
+1
2:			2 zero			2
+1
3:			2 adi			2
+1
+0			+1
6:			2 sufO 2			9: 1 dec 1
7:			2 adi 2			10:			z 1			13: 2 adl 2
+0			+1
11: 2 sufO 2			1 zero 1
+1
__			e2
1 adl
____			14:			____
___ 2			?:?l5:
16:			___ I
In the program above a number with between, tj(n-1)+2
and tj(fl)+2 binary digits is nondeterministically generated
in register 2 (where n is the initial c?ntent of register 1)
Such a number is between 2t?(n-l)+2 and 2ti(fl)+2?1. One
is added to the content of register 2 and the predicate e
is applied to the result. This accepts X.
We now define the predicate e by induction. Let
o+((Dix?tjk))ktl be an enuneration of all pairs of a deter-
ninistic J1-flowchart and a function in T, each pair appear-
ing infinitely often. It is clear that such an onuneration
exists. Let e(x)=O for X<2t?(c)+2 where c is chosen such
that ti(x)>ti(X?l) for x>c. For n>c assurne the first n-l-c
pairs have been looked at and e(x) is defined for all
(n-1)+2 Let Zn?l be the finite set of numbers
greater than 2t1(n-l)+2 for which e has already been defined
to be zero. Naturally, Zc is ?. Now for the nth pair,
E8
the following procPdurc is performed:
(11 If t(n)>2ti(n) let e(x)=0 for all XtS? and let
Zn?Zn?l?Sn?l
(21 Otherwise conpute (n) for up to t(n) steps, recording
all ergtL?ents x>2 ?(n-l)+2 for which uses the
predicate e(x). For all these x, e(x)?0. Let
Zn=(Zn??U(x: D?' (n) used ?e(x)))?Sn?1
(a) If D (n)>t(n) then let s(x)=O for all x(Sm.
[bi
Otherwise
(ij If D (n)60 then let e(x)=0 for all XESn
(iii Otherwise let e(x)=0 for all X(Sn except
the least element not in e is 1 for
this elenent.
From Nl we know that t(n)<2ti(n) a.e. Since the
enuneration of pairs is infinitely repetitive, the pair
(D,t) cones up for infinitely many n such that t(n)<2ti(fl) I
and (21 is followed.
In (2bii] we know that the nw:?er of elements in
is less then or equal to
n			n			n
?l DJik(k)< k?l tik(k)<k?l 2ti(k)< k?l 2k
which is less than 2t?(n)+l At any stage we have left in
5 -z			at least
n n
2t?(n)+2?2t?(n?l)+2?2t?(n)+l --H 2ti(n--Hl) (2ti(n)?ti(n?l)?1)
elements, which is more than one, by H3.
69
is thus well-dcfined, and by construction the se? X in
not acceptable by any T-bounded deterninistic J.'program, as
was clained.
70
Theorern4.2 Por any flowchart interpretation J and any r.e.
class T=(t.: j  `T? of recursive complexity bounds such that
[H41 for each j ? IT there is an i  1T such that
tj(X) > 2?t?(x) a.e.,
there is a flowchart interpretation J', gotten from J by
adding a finite number of unary functions' and predicates1
for wilich
A?' D?1
PT			?
Proof Intuitively, we, add a "universal operation" which
"operates" on instantaneous descriptions of nondeterrninistic
programs in a manner similar to the way the cperations of J'
operate on the registers of a deterministic J'-program.
Let h be a recursive 1-1 function from the finite sets
+
of fini?e secuences of non-negative integers (written N2)
to the non-negative integers (N) whose range is a recursive
set. It is clear that such an encoding exists. Let J?
contain all the functions and predicates of J plus all of
the following: cod3, sufO, sufl, steo, out, halt. Let
A1, A2, A3, . . - be an enumeration of the J'-flowcharts.
Such an enuneration clearly exists. Define the new functions
and predicate as follows:
cod3			--H
sufO
sufl			--H
71
+
step --H Ax(((x""lok'lo?l?)&(xcN2)&(k=h(x))&(k?h(AJ.'!x1),)
? ,10k10?1			0));
out --H ?x(((x=?loklo?l)&(k=h(x))&(x 2))
min(t 1 o+(O,t 1 2,.. .Lm? cx); 0)
halt --H ?x((x-?lOklCili)&(k=h(x))&(xc 2)&
(X includes a sequence starting with 0)).
explanations: cod3, sufO, sufl?will be used to encode
o+lO?lO?l?. step is the "universal operation we mentioned,
performing one step of the program A. on the partial
results encoded in k. halt is a convergence test. out
deoodes the output from the encoded partial results.
We will now exhibit a program Da(i) which determin-
istically computes the same function as A. for each i.
Furthermore, this program will use
(x)+i+4
steps for input x, thus being T-bounded whenever Aj is.
by R4.
D			__
c(i)
1:			1			cod3 1
+1
2:			1			sufO 1
+1
i+l:			____			1
i+2:			____			1
i+3:			____			1
j+4:			____
i+S:			____
1 sufO
1 sufl
I sufl
+1
1 steo 1
+1
halt 1 ?? i+6: I out 1
72
It should be pointed out that1 although ste? is defined
recursively, it is always convergent. The case in doubt
would be when computing ?x] involves computing ste?(y)
for some y. In this case, y must be smaller than the x
which encodes x. For successive recursions each argument of
step must be smaller. Since the initial argument is finite,
step always converges. The program D0(1) does what we
clai?od and so we are done. Q.E.D.
Jan05 Simon ?26] observed that the constructions of
Theorems 4.1 and 4.2 allow us to prove the following
corollary.
Corollary4.3 It is recursively undecidable whether
A?			D?
ST--H			ST-
for arbitrary flowchart interpretations J, where T is
a class of complexity bounds satisfying Hl-N4 of the
preceding two theorems.
Proof We combine the previous two constructions, so
that one is effective if a given Turing machine halts
and the other is effective if the Turing machine does not
halt.
Let J be a flowchart interpretation. Let J include
p
the functions and predicates of J plus the functions
zero, adi, sufo, codl, cod2, dec, cod3, sufl, stec, out
and predicates z, e, halt as in the proofs of theorems
4.1 and 4.2, except that e and step are to be defined
slightly differently.
73
step is defined as before, but over the language of
Jp and with the modification that s?eo computes A. [xl,
where J' denotes the interpretation identical to Jp except
that e is zero everywhere. step thus fulfills its role
as universal operation" for J only if e is identically
p
zero in J
p
e is defined as before for arguments x such that
G (O)<x. For other arguments, e(x)=O. Thus e serves its
role as expansion of a diagonal set only if Gp(0) converges.
When Gp(0) does converge, e gives us a set in )%AJP but
J
not in RD P. Otherwise, eC and step "works", making
T
J			J
Ap			Dp
R? =?
Clearly a decision procedure for whether ?Jp D?0
=RT-
would solve the halting problen, which is widely known to
be undecidable.			Q.z.D.
Since the non-halting Turing machines are not r.e.,
we also get a stronger conseguence.
Corollary4.4 The flowchart interpretations where
A D
RT-= ?
are not r.e.
74
The preceding results remain valid when the complex-
ity classes LA and tD of languages are interchanged with the
T			T
complexity classes RAT and D of functions. In fact,
RT
LAT 6 LTD			RA--H,' D
RT
and contrapositively. Except for minor changes in encodings
and in the hypothe?es Hl-H4, the proofs?are also independent
of the precise model of flowchart computation. That is, it
does not matter: whether cross-register assignments
(i F ?, i#?) are allowed; whether a nondeterministic algo--H
rithm converges when the first computation terminates or
when the last one does; whether only one register, some
fixed number of registers, or arbitrarily many registers
are allowed.
Furthermore, although the flowchart programs defined
compute functions on N (the bit strings without leading
zeros), "acceptance" for general character strings may be
defined in terms of a simple isomorphic representation of
the character strings in N (e.g., w? `l?w). It follows
that the statements made above about complexity classes of
functions and sets of integers might as well have been made
about complexity classes of functions and sets over the
character strings, specifically, the classes of languages
NDP and DP.
75
K. Mehihorn (23] has recently proposed tnterpreta-
tions in the domain of conputable functions for some of the
elementary notions of general topology. ?ased on our ear-
lier formulation of Theorem 4.1 (in terms of T.M.s with
o+oracles?) he observed that the construction gives a set of
oracle functions which, by his definition, arc "co-meagre".
In terms of flowchart interpretations, this means that, for
sufficiently powerful interpretat?ons J, the set of pred-
icates which J may include without causing ?
? 15
"meagre". It implies that in sorne sense "most" flowchart
A? D?
interpretations J satisfy R--H11 ? Rrt . Since the construc-
tion is essentially the same as that for Theoren 4.1, we
give it here in brief form, along with the needed defini-
tions.
The following are Mehlhorn's definitions:
Let T be the set of (finite) functions from an initial
segment of N to N. For 5 to extend t means domain(t)
is a subsetof domain(s) and s(x)=t(x) for all xtdomain(t).
Length(t)= max(domain(t)) for t?T. The basicooenneigh-
borhoods are the sets Ut (f tT, f?R, f extends t). A
set 5 of recursive functions is (effectively) nowh':????u??
if there is a recursive veri?yingrunction v:v?r s.t.
(1) for all tET, v(t) extends t, and
(2) there is an n?N s.t. for all tcT,
length(t)>n			Uv(t)flS=?
76
A set t'JL of recursive functions is (effectively)
neagre iff there is a sequence
f(Mi.vi))i??
of nowhere dense sets with verifying functions vi such
that
M- U M
i=l
and
v --H ?i,t(v?(t)) is total recursive.
77
Theorem4.5 If J is a flowchart interpretation such that
G
then the set Q of recursive predicates which J nay not in-
dude unless			J			J
pA? IL			D
is meagre in R.
[As stated before, G denotes the Turing machine step-count-
ing reasure for single-tape machines; It denotes the class of
functions ?i= ?x(??(ln?(x))) where ranges over all the
polynomials with integer coefficients and lng is the length
function; R is the class of total recursive functjons.i
Proof ?ecause of the great similarity to the proof of
Theorem A.l, some details of the argument have been omitted,
but the construction is given in full.
The interval 2lng(n)-l+1, 2lng(n) is denoted by
If e is a predicate the set x is defined:
Xe= (m: ?X(XESm ?
Let ((DmisPni))i?l be an enurneration of all pairs of a
deterministic "J+e"-program and an element of It.
--H (el x is accepted by (deterministic "J+e"-program)
and			?"J+e" < ?			(everywhere))
I			1			I
where "J+e" denotes J if J includes the predicate e and
denotes J augmented to include e otherwise.
B			UB
i--H--Hl
7e
To satisfy the definition of meagre we must exhibit
a computable verifying function v:NXT?T such that ?i is
nowhere dense with veritying function v = ?t(v(i,t)) for
`each i.
Vi(t) is defined in a fashion similar to e of
Theorem 4.1: Let
m = minfx: Pni(x) < 2lng(x)-2 & ? > length(t))
The dornain of Vi(t) is
fx: 1 < x < 2lng(x)--Hl?
Cases: (A) (x<m) : let Vi(t) (x)= t(x).
(B) (x>n)
(1)
(?(m) >pn(m) or (D??(m)?<p?(m) & Dm(m)?O)):
1 1			1			1 1
let Vi(t) (x)= 0.
(2) (?(n)?<pn.(m) and Dm(m)=o):
1			1 1
let Vi(t) (x)= 0 unless
x = ninfy: YSm and Dm(m) does not use
e(y) in its computation) ;
otherwise, let Vi(t) (x)= I.
Clearly Vi(t) extends t. To show that a' is nowhere dense
with verifying function v. Ve need only show that for all
tcT
length(t)>n ? Uv(t) fl B =
Suppose the contrary, that there is an a in B. which extends
Vi(t) for some t such that length(t)>n. This means that the
o+J+e"-progran			D
accepts Xe in ?n? steps1 i.e.,
79
Dm.?< ?n. Since D?(m) < ?n.??? wo ?ave either
I			I			1 I
Dm(.n)?o and e?(x)v?(t) (x)=C for all x insn or else we have
Dm(,m)=o and e(x)=v?(t) (x)=l for sone x in 5m In both cas?s
we have a contrad?ction.
It follows that ? is neagre. Since Rw.			R? we
know Xe is acceptable in linear `time with respect to the
length of the input by a nondeterninistic "J+e"-program,
sinply by "guessing" a number in 5n and applying the
predicate e. If e is in 0 we must have
?"J+?e"			?"J+eJ'
which ineans e is in B. for some i.			Thus Q=B and we are
done.			O.E.D.
80
?4.3 Nondeterninismatutner??mnexityLeve?s
It is natural to ask whether nondeterminism may gain
anything in simpler interpretations and for tighter time
bounds. It may.
Theorom4.6 For any monotone non-decreasing recursive
function and any fiowchart interpretation J which includes
the function `+1 = ?x(x+l), there is a recursive
predicate P su?h that if J includes P then
A?			D?
Rt YE
Proqf Although the statement may appear similar to
Theorem 4.1, the method of proof is quite different. The
critical observation here is that a nondeterministic
program may loop without executing a test operation. The
predicate P is defined so as to allow a mondeterministic
program to make use of this advantage to diagonalize over
the deterministic programs of similar complexity.
J
Let (Di)
i=l be an enumeration of the J-programs
with infinite repetition; that is, for every i and ? there
is a k>i such that DJ = Dk? Suppose J includes a predicate
named P and that it is the same as the P defined as follow?:
Staqe0: N0= 0. P(C)= 0.
J
Stagei: Assume P(y) is defined for y<N?. Compute Di(Ni+l)
for up to t(Ni+l) steps. whenever a value for P(y) which is
not yet defined is needed in the computation of D1?.(Ni+l)i
assume that it is zero and add y to the set U. (which starts
81
empty for each i). For each new argument added to U. (aft?r
the first one) a new function step must have baen performed.
Adding the function steps needed to generate the arguments
together with the predicate steps needed to apply P, we get
) 2??UiI?l
J
If Di(Ni+l) doesn?t converge within t(Nj+l) steps
then we give it up and go on to step i+l, letting
Ni+1 = max(U.u(N.+l))			and
I			1
P(y) = t? : if ;1CU?t and Ni<Y?<Ni+l
If, on the other hand, D?i(Ni+l) does converge within th?
time bound t, then let
Nj+1 --H max(u.ufD?.(N.+l)))+l and
1			I I
J
0 if Y?Ui or Y=Di(Ni+l) & Y>Ni
P(y) -			J
1 if Y/UiU(Di(Ni+l)? & Ni<Y<Ni+l
The nondeterministic program
L?1:ij1oi
computes the function
f --H ?x(min((y: y>x &
in 2+f(x)-x steps or less. If f(x)>x we know that X#Ni for
every i, since otherwise f(x)-x. Thus there is an i such
that Ni+l < ? < Ni+1 if f(x) > x.
82
Zn this case we also know
x E
J
or			x --H Dj(Nj+l)
and			luil < (tjNi+l)+l)/2
For every y between f(x) and x, P(y) --H 0 (includinq x but
not f(x)), so
f(x)-x < IU. 1+1 < t(Nj+l)/2+l
and 2+f(x)--Hx < t(Nj+l)/2+3 < t(x)/2+4
if t is nondecreasing. That is,
f  RXx(t(x)/2+4)
Since f was defined so that
f 
Rt
we have			R?t			#			Rt
5 Relation-toOtherNatur?'I?a.2.qu'.a?
The flowchart measures are a natural cL'- of complex-
ity measures in the sense that t?,? ?o count recoqoizable
steps" in a specific model of computa??on. They do not
properly include all of t?e co?m?nly ac?pt?d Nat?r?i*meas-
ures, which have come to mean the single and multitape
Turing machine time and tape measures and t?e va-?ou? ran-
dom-access machine step maasures. There is, howev?r, a lim-
ited sense in which these can be "mimicked" by flowchart
measures. ?f we consider a large enough class, suc.? as the
polyncmially-tirr.e-bounded functions, it is the sa:t for .`oe
flowchart measures as it is for certain Natural measures.
Althcuch we show this only for Turing machine time and tape,
Xarp [17) has claimed that the classes NP and p are the sare
for all Natural time (as opposed to storage) measures. whic'?
would mean that the flowchart measures extend all th Nat-
ural time measures, at least in so far as the polynomially-
time-bounded computations are concerned. Of course Karp
gives no proof of this, but our experience with the two
examples given leads us to believe it is true.
*[ Note distinction between "Natural" and "natural".]
S4
8%
?5.l TuringMachineTime
Theoren5.1 There is no flowchart interpretation J s.t.
G
= Rt
for every recursive t, where RG is the class of t-bounded
t
functions with respect to the T.M. step measure.
proof We show that the tape of the T.M. forces it to
compute things differently from the way a F.C. program
does.
Consider a function which forces the T.M. to move
its head along the entire length of the tape. Assuming
a T.M. starts with its head on the leftmost bit of an
input string, such a function would be:
f --H ?x(;;=x1.. Xn)? Xl???Xn.lXn? 0),
where we denote by X? a bit that is different from Xn
f is in RG but no function equivalent i.o. to f
?x(lng(x))
is in RG?t for any t < ?x(lng(x)) i.o. Suppose there is
a flowchart program A. which computes this function in
?x(lng(x)) steps; we can show there is another program which
uses fewer steps and still computes the sane function
infinitely often.
J
Ai may be altered to skip the first predicate step
(if there is any). This is done by making a tree-program
of all the paths from the starting node of A. which consist
86
of only function nodes up to the final node, which is a
predicate or terminal node. A copy of A17. is then made.
For each predicate-node of the tree-program, consider the
predicate either it is 1 i.o. or it is 0 i.o. First
suppose it is 1. If the 1-edge from the correspond?ng
predicate-node in A?. is null, we simply delete the node
If the edge is not null, we delete the predicate-node and
replace all edges leading to it by edges lead?ng to the
7
node (in the copy of A.) corresponding to the node
(in A.) to which the 1--Hlink of the predicate-node goes.
If the predicate is not 1 i.o. then we perform a similar
procedure for the 0-edge. The resulting program is called
Since A. computes a total function, every path
containing a loop must include a predicate-node. Thus,
7
unless A. is bounded by a constant, the modified program
we have described1 A7., will use one fewer step , while
still performing the same sequence of function operations,
for an infinite number of inputs. It thus computes a
7			G
function in R?7 but not in R--H7 .
A.			A.
--H3			--H3
87
Theorem5.2 If T is an r.e. class of recursive complexity
bounds s.t.
(::5] there is a t in T s.t. t > log2 a.e. and
[H61 for every t and t? in T and every polynomial P(x,y)
with coefficients in N there is a t" in T such that
t" > P(t,t')
a.e., then there is a flowchart interpretation J such that
G
Pr-			Pr-'
where G is the step-counting measure for (nondeterministic)
multitape Turing machines with binary alphabet.
Proof The model of T.M. which we use has a binary alphabet
for input and computation, with an additional "blank"
character which can be read but not written. The portion
of the tape which is not occupied by input and which has
not yet been read is filled with this character, which is
found nowhere else. ?or consistency with our input-output
conventions for flowchart programs the input is assumed to
be only on the first tape and the output is the nonblank
portion of the input tape to the right of the head at
the time the machine halts. The operations for an L-tape
T.M. consist of an t-tuple of operations fron the set:
print-O; print-l; print-O-nove-right; print-I-move-right;
print-O-mo're-left; print-l-move-left--H one operation per
tape.
o+9? p? s? o; ?uTp?0??? `?; e?os Aq peptrnoq ST ??T?"
+ ;. `z.?3 >
T=T			T--HT
x + ? u.t? (T.?+u).?? ?
?? ?T `: ???`1?T 30 ?ndQT uo
? o+?ITflt::TS ? ?S? ??? `pe?0TT? e??? e? Su0T????d0 a?
30 ??TL??U Aq `u0T;??ad0 ?ed s?Tq 0?? ;Sou! ?s Aq ???ST??? ?
30 ?zTS e?? ess???uT u?? e?? ??uTs 0 ?UP?SU00
?os 103 ` (u.?) .?o Aq u ??bu?T 30 1e;ST??1 ? uo uz??6oid
-r ?? ?? uoT??1ed0 u? 103 sd?s o+W?L 30 IaqLuflU e?? pun0?
sn?? ugo ?i o+Ie?ST5?I pe?STntJ'TS paTdOO ??? 30 ???U?T ???
?oedse1 t(?T? lPeuTT u??6s ?T S??? ?nq `??nS?I e?? ?uTAdo3 30
e?? 103 ?I0? ?Su0???pp? e?? ST e1et(? ?U??fl?I? e?
peu??u00 ?0T?? ?S'? US?? Ie??0 1e?ST5?I 5 UT p?I0?S ?T u0T?5
?edo us ??ns 30 ?TflS?1 e?; 31 o+U0 pe?s?edo ST ??T?? 1??ST
o+??1 P???Th?T? e?? 30 ??BueT e?? S?u!T? ? ?T u! pUS ?U5?Suo0
5 ST ?0 uTsBS S1SU? ` u.?o Aq pspunoq Su?T? UT o+W?L ?u?
Aq pa?nd?o0 ?q TT? uso r 30 S?S?? PUS Su0T?S?Sd0 eU? ?SU?
uses ?T ?I o+pspOous eq 0? ?nduT eU? 30 U?0ueT ?U?
? ?T ? Pu? ouS?SU00 S ?T T0 SISUM `sda?s u!.TO ?noqs e?s?
TtT? u0T????X? TsT?Tu?. ?U1 (??US?SUO0 ST ?T ??UT'S `?U?A5
?e1IT ST ? 1sqUnu STOSId aU?) o+S1e?ISU1 55 ?Sn o? o+si??05
-15U0			51?X5 a?cS SASU TTT? o+W?? ?U? ??U? 0S (s			TT.
OT. .0. `?b?e) dpoO ?TU-? 5 UT ?ndUT 5U?
9?O3U? 0; ?T de;s ;s1?? s?? o+A;Tn?T.;?Tp ??ou2 e?;;??
u:?:?o:d-r ?a;sTbe1?? u? ?;vTnuzT.s u?? o+w?? ed?;-? uv
(?T uoT??sOd UT
p??? p'i? x s;u?;uo? ??T,? ed?; ? ?Ut.PO?U9 X?OTT? ?;Tn 1edg;
? 0; spuodse?io3 ATT??n;?U ??;sT?e? ??L) eel; ?T.? ?O
???e lO? sepou uoT;?ledo ? ;so? ;? pu? I o; dn ?;dep ?o
ee?; ;se; ? `???? e?; ?o e;?;s ???e 103 `buT.pnI?uT Aq ATdurt.s
`sde;s (x);.I.?+? BuTsn 3Tes;t. `x ;nduT uo sde;s (x); sesn
??T't? o+W?L ed??-? u? e;?tnu!T.s U?3 ? `At1?eT?
o+suo?,;?iedo o+??? e?; 30 u0T;?Un3 e?; ?Tu!TUZ o;
?ATl?TT,u!T9 peuT3?p ei? 1-?-d pu? `T-o-d ?? `?0-
(x .,.ouA...TAo T.
T+t.
? (.UA.. TA0 T.?))
.,.UA.. .T+TT--HI...TA to
1+1
? (.UA.. .TAo'.T.=x)))x? --H Trw'-
(x `A ?(A0To+z? .Tzo1T.?-x) )x? ep0?ep
= epo?
? (T=To+A) , (!UA? .TAo1T.=x))x? = euo
, (0=TA) ? (.UA???TAoT,Tsrx))x? olez
su0T,?21?O
edg??e?5uTo+s o+w.? e?; o; A?? sno?Aq0 u? ur pu3dserio?
uee? eq TI'." su0T;?un3 le;;?i euJ, 7=7 pu? `T-o.d
o+l-T-a `1-0-a `? `0-0 `apo3ap `ep0? Su0T;Dun3 pu? euo pue
o1ez se;???pe1d sr? r uoT.;?;e.?dIe;uT. ;1????oT3 eu?
68
?o X?PUT ?? ST 5			o+W'L			et(; ?o uoT,?dT,??s?p e?eTatuo?
I			s?po?ue			`?`?T? seu:? ??A?t(?T?? `9aT?Ao o+W?L ?t(? 10
`s?TI? o+w?? ?`t? `lell ,(1Q? peqTl3sep e?? ??o seAou: psa?
T
e?? ?e???e TT?un ?xn1 pu? <A'b'x'd's''?> o+p?T u!o1?
T
?T op PT?O?			;? o+???			T e?? ????
(<A'b'x'd's' `?>)ae?s uOT??Ufl? de?s bTq T?s?eAT.un (?)
o+SuoT?T.sQd p?e? ?uT?1??s PUl e???s ?UT,????S tIT A ?ndUT Uo
T
e?? ?o o+P?T e?? ST <A'o'c'o'o' ?> e?e?? `A ?ndUT
T
u:oI? <A'o'o'o'o'??? epo?Ue o? SUoT??Un? bUTPo?Ue (T)
:epnT?uT o? r ?UT?ea
o+UoT???nd?o? o+w'? e?? ???Tfl?TS e? `pa???e1 ST
p?? TIUTu11.e? ? TT?Un ae?s ?UT??1??T A? o+?Ueurn??e S?de?S
1::O1? p??1??S o+W?L ? Aq pesn e? PTflOM ed?? ??o? ?o ?15flbS
I ??Ttt? ?O? o+P?T ;xeu e?? s??nd?o? d??s o+(??P?T)
SeUT??? 5UT1n? ;o sUoT?dTI?SaP Sno?U??U??S?T papo?u? uo
S?1O? ??TW? Q??? UoT??un? de?s ?Tq ? SePnT?UT r ?oo?a
o+exns?eu: ed?? eUTt(o?uz 5UT?flL ??? ST .? ?:(?t[M
r
??`n t;?nS r UoT???e?d?e?UT ?1????OT? 5 ST CI?t(?
--H< `? o+?`S ? tIT .? ? ?T e?e?? ? tIT ? AiaAe 1O? (8H]
pul 91 X < (x)?			?1U? U??S ? tIT ?			5 ?T			e?e??			[L?]
4 5			PtI??oq
A?TxeTdu:Q? eATS1n?e1 ?o			? sss?? o+e?? Ati?			2O?			??S
=UT.tI??w bU??L1			??s?
T6
.9?s s?; ATT?T.?uesI? ?T 3oo:d o+?
o+S?W?L ?T.?9TuT.u::e??p puv su!v??o?d ??????OT? ?T.?sT.ut.uLXe??p ?o
sd::?? UT p?4??9e? ?T OST? ?n?? ST u:e?o??i ?uTp??e?d e?L
o+s??ns??ut t(?oq UT ewvs e'?? ?1? L A?Tx?t
du:o? o+?o suo???un; e?? sp?zTS???odAq ?g ?T ? ?T `Sn'(?
O6
92
the current state as it appears in x is the work tape,
with head position p. y is the input tape, with head posi-
tion q. If T.M. G! halts or expands its work area,
5teD(<?i,s,p,x,q,y>) is the T.?. 5 i.d. at the point where
it first expands its work area or halts. If G' cycles, with-
out expanding its work area, then steD(<??,s,p,x,q,y>) is
(3) decoding function decode(<???s?P?x?q?Y>) =
where x = X1...x? (leading zeros assumed dropped).
(4) halting-state--Htest predicate halt(<C?,s,p,x,q,y>) = 1
iff x is a halting state of Gj
With these functions and this predicate we can write
a J-program
encode<?i,o,o,o,c,y>
1+0
z;i1: r1 s??o r1
i+l: halt r??-+j1+2: r1 decode r1
which computes G in G!?2 + c. steps, if the encoding of
1			--H1			1
is done in ci steps. In that case,
RT--?RT-
by H7 and liS.
is encoded so as to make the initial
encoding easy. The usual encoded form is
93
where --H ?x((x=y'l?)? ?(y)'ll';
(x=y?O?)? ?(y)?lO?; o)
o+ = o+00., $ = Ol x = X1???Xp?1 and x" - Xp o+XnI and
y and y" are defined similarly for the input tape, y. The
exceotion to this is when y has head position 1, as in
starting. Then the form is
This allows us to encode <?. ,O,O,O,O,y> in a constant mum--H
ber of steps independent of y, using the encoding functions
?rel = ?x(?l'x) and
shift = ?x((x=?l?y)? `iC'y; 0)
It renains to be shown that
c RT
i.e., that a T.?. can compute any function computed by aT-
bounded deterninistic J-program without using more tape
squares than can be bounded by some function also in T. In
simulating a J-program, a T.M. will require many steps for
each operation of the J-program. We must merely assure our-
selves that each operation of the J-program which the T.M.
simulates will require at most a constant increase in the
size of the T.M. .5 work area. Initially let the T.M. copy
the input onto its work tape in an expanded form, so as to
get the effect of a very large character set. Conceptually,
we view this as a five-track work tape,
94
e.g..			1			register contents: r1, r2, r3,
2			working copy of register contents
3			delimiters of registers
4			working markers for comparisons moves, etc.
5			countina space to detect cycling
This initial encoding will require a linear increase in
work area over the size of the input, but it is only done one
tire. The T.M. makes use of a few markers to help it sinulate
the various steps of the J-progran on the encoded reaisters,
which are recorded in sequence on the first track of the tape.
?flien the program terminates, the T.M. decodes the output into
single-track form and halts with its work head at the beginning
This			again only happens once and in fact need not in-
crease the work area at all.
Zf the operations of J can be simulated in this envir-
onment, each costing at most a constant increase in work
space, we can conclude that
J
D
nT-sRT
by H7 and ?8. Considering these operations by groups, we
see that the encoding functions, decoding functions, and
predicate can easily be computed within the constant-tape-
increase constraint. The only apparent difficulty is the
function ste?. Since we have encoded everything in a rather
simple fashion, there should be no difficulty in following
the steps of the T.M. computation simulated by sten. The
counting space in the fifth track enables us to halt the
simulation at a point where we can be certain it has begun
95
to cycle. This is done by counting each step of the siinu-
lation until the space is full. This takes steps for a
fifth-track alphabet of size Q and track length t. The
lengths of the tapes plus the nunber of states of the T.M.
G. sirulated by stan nust be less than the length of the
tapes of the T.M. sinulating step, since the argunent to
s?p encodes the entire description ?? along with the tapes
of Gj			With read and write tapes of lengths n and m, and
m
states, G! can go at most 2 o+q. n?n steps without cycling.
1			1
This is less than 0??+n+n, which is less than Q for 0
greater than 2. Since sten was the only operation of J
that could not obviously be done without more than a oonst-
ant amount of additional tape, we are done. Q.E.D.
o+s?o; ?uoI?s IT??? UT ?s?eT ??
`se?ns??? ??????OT? ?t(? ?O? PTO? ATT?Pss?3eU ?oU op
ese? 30 ?e3 ???? ?0?S eM o+!oT? s??fls??U T??n??U
?03 pesodo?d U??? eA?? seT???do?d eTqe?Ts?p Au?w
s??n??p? ???n??uun ?uios ??9?
o+se?ns?em `?T? TT? ?0? PTO? ?ou op saT???do?d
?P? ?0?S 0? `??t? UT `u?AT? ua?q eA?? s?Tdu1Pxs
o+? ?uTs???3UT
ATe??u:T?Tn ?o; o+??? e?? s?ssP?? A?'.x?idu1o? ?.T???Mo?3
???? eAo?d o? pasfl s?? A???do?d ST? o+)( ?U??SU0?
eu:o!3 ?03 PUP sIC.? sITD ?P?? ??flS P
96
?o uT?u!op e? UT s ?es ,??TuT? ??AS ?O? ?T U:op
-ee?? e?TuT? s?? ? uo o+?n9??c! nm?g v inop?e?? e?TuT?.
???? e? (?ndUT ?T.etp ?O TT? p?e? ?ou peeu S?UTM?P1:t
??tI? ?UTuznss?) se?ns?eu: ???n??? e?? ?o OST? pU? sein
-s?em ?i???MoT? e?? ;o eni? ?T ??T?" A?iedoid ie?ouv
uiopa?i? a?TUT.?
o+A21a?oIa uoT?Tsod?o? eu? ?T ????
o+ed?? pu? euzT,? euTtt??u! BuTin? s? ??ns o+pessn?s?p e??q eA
seins?e? T?ifl??N e?? s? TT?? S? se?ns?eu: ?i?t(??OT? ?o eni?
ATi??T? ?T A?i?doid ST'&? o+b0? e?ndu?o? o? ?+6.? u?? eiou:
?so? ?oU PTflO?S ?T ue?? `e?ndmo? o? s;so? ? uoT??UnJ e??
pu? ??nduzo? o? ? ? UoT?oUfl? e?? ?T `ATeAT?Tn?UI
UoT?T.sooL'o?
:seins?eui ?i????oT3
e?? UT pe2TUBo??i eq A?ui seT?iedoid TP?n?Pu ?2ou! O?L
o+peAg?eq TT?? ATi?Tn?T.?i?d ei? seins?eui ?iP???oT? a'?;
??TU.M UT sAP? OM? e??i?snTTT ? pu? ? sie?d??? o+s?set;1
ST'?? ?ioddns ??T?? seT???do?d eLos UeAT6 Ap?eiTg ?A?%(
si??dPt(? snoT.Ae?d o+sa?flS??? T?ifl?PU ?o s?To+;s?ie???i???
e?? ?noq? A?T?PieU?b ?u!os UT ???ds o? sn ?OTT? o? es?eA?p
AT?u?T?T??ns ??? e??s e?? ?? eTT?? `seins?eu:
??T? Au?? up?? p?Ap??q i???eq e?? se?nspeu1 ??????o?? e??
?Pt(? `sa?d??x? ?????fl3 Aq `?o?s o? ?d?a??? TTT? a?
s?T???Qo?d TU?t?rN o?? T?9?
???n%:??? 2?P???o?? ?u? ?o s?T??aao.?d iau?o 9
os `? ?nduT. uo ATe??Tpeun:!T
y
?T e?:o? 0ST? PTfl0? o+e'? sd??s UT
PTfl0? `(QT?? e??3Tp??d A1e?? ,( ? t(?flS ?oa o+r UT ? A?e?e ?o?
T -			_ = (`t)a 4-			o+??? ?			a puv
T =			= (?)a ?			o+e?? 0			a
` ?u:os ?oJ ;?? os `r UT se???Tp?d ?o ??qumu e?TuT? P
eia? o+?nduT etp UO T ?T d ??tt? ew?? A???e ?so'nT? ???6oid
3(T
s???uT.m?e? t(?T'&? ?P0U ????Tpe?d ? ti?TM u??eq ?snu:
= 4- T = (x)d
r
e?u?s o+e?? v ?uiT? UT ?OT se?nduio? v
r r
Tv
95oddn9 :sMo?s ?u?uosPeI ?uT?oTTo? e?? ?? r ? UT ?0U ?T
(x `0 ?(?=x))x? =
uo??oun; eq? ???? ??flS ? ?T ????? `e?dui-?xe ?o? o+s?usT??A
e?TuT? ??T ?0 tT? ;0'Z ;nq `uoT??un? A?T?u?pT a?? s?pnT?uT
v
r ? `es?0M ?T ??? o+s?nduT ?o s?es a??u?, uo suoT?
s0?v o? buTpuodse??o? sw??5o?d-e??? e?TuT.? ??? Aq
r
pe?nd?o? suoT??un3 ?`&? TT? ??? buou? `suoT4?ufl? AuP? ATa?T
v
uT?uT S?PflTDL1T ?? r
?? ,?o? o+??T????3-??o ? 6uT?ndwo?
pu? ? ?T a 3T. AT???Tpo??'. ?uT?Tst? `a ????Tpfl?d ??? t(?Tt?
66
?nduT e? s?s?? t(DT?? ?pou ? Aq
v buTpe?e1d Aq u.?;ob
??Boid etp eq ?e? o+; i?nduio? ?T'(? 3rTv ??boid I
?T e?e? T?9??ATun ?T r e?uTs I ???L o+sd??s ?
SS?T UT o+o?T eTq??ndmo? ?Ot' ?T T?9 ?um'a? ?o ? e?? ?OO1d
o+?uI?I?AuT ATe?TuT?
?ou sT'rv o+o?T T PUl o+o?T 0 ?T ;It!? d e???TPe?d I
r UoT?S?e?d1e?UT ??S?D?OT? TISleATUn Aul ?oa ?`9 ?uLia?
o+6?I T			--H
o+? < ? ?ATI?eT? `ue?? o+e?I ? > o+D ?1
T T=T
((0 .(x)o+? ?((x)? ; (x)T?)) ?			--H
x
(TITATI;)			?oo?i
o+o?T ? < o+?			o+o?T 3
??tt? ?ons ? eATs?n?e? ? ?T e?e?? ? UoT??un3
eAs?n?e? Aul pu? ? Uo einss?m UrflT? Au? ?oa T?9 ?UflL1e?
o+s?um!eT ?uTAoTTo3 e? 1!T ue?o?d 91 `A??edoid
?U???T1 sT'(? e?s?s TT? ?OU Op Se?flS1eU1 ??1tt??OT3 etp
?nq `e;1Un??O3Un ST ?1 o+?U1T?1AUT ATa?TUT3 ATI1eT? ?T
elnsleuI ed?? ?UTU??U bUT?n? 1U? o+A?TxeTdu!O? S?T UT eBus??
TT1'?S 1 ?SflP? ATUo pTnOUS uOT??Un3 I UT e?us?? TTILS I ?IU?
SA-QS sTU? `AT?AT?Tn?UI o+? eATS?n?e? A?eAa ?O3 `OSTI
T
UT ??I ?T 30 S?U?T?IA e?TUT3 TTI U1U? ? UT ?T ? 3T o+???T
`			c			T			C
? ?o)(? ? o+e.I .? 5
`D PU? o+? ?ATS?n??I TTI ?O3 3?T ?U1T?IAUT
Ate?TUTJ ?T ? bU???qwnU Tapgo uO ? e?nssaui ?TS Y
o?u???':AUT 0??U?1
86
loo
Procerness
A Bl?wt measure on G.N. G is proper iff for every i
G. E
--H1
2i
This means intuitively that the running t?me of an algorithm
should be at least as easy to compute as it is to run the
algorithm. Although this seems a good idea, it ?ay be a
little too strongly stated. We shall see that many flow-
chart measures come close to satisfying it without satis-
tying it precisely.
Lemma6.3 If flowchart interpretation J includes the
function ?x(x+l) them for every i
J
A?i E R?x(2?AJi(x))
?roof (trivial) Alter the program A. by putting an
addition operation between every two step?, doing the
final addition into the output register at termination.
The program counts the steps of A.. O.E.D.
This idea can be taken a step further, expanding the
program to make all cycles of lengths divisible by k and
no cycle beginning closer than k nodes to the initial node.
The steps are counted by adding one for the first k steps,
adding k every k steps thereafter, and adding 1 up to
k times at termination. This yields a stonger version
of the ler??a.
Lemna6.4 If J includes the functions ?x(x+1) and
?x?j(x+y) then for every i and k
J
A.  RAJl2.k
--H1			x(Aix?+k?+
(proof has been sketched above.)
This neans that for reasonably powerful interpretations
there is a t arbitrarily close to each A. such that A?i Rt
Now we look at a specific one of these interpretations to
see that we can do no better than this.
Let J			(fp,z)?(plus, plusl, ninusl)) where
ninusl =
piusl			=
olus			=			?x,y(x+y),
z =
p =			??((??y???ki)? 0?
(x?Ni?lokI)? 1;
(x?Ni?lOki?)? 0;
(x=Ni'lO (C(Ni)?3)/2 )? 0; 1),
--H			?x(x'lO9lO9l')f
kj --H			min(k: (A?r(i) (Ni) does not use p(NiIlok?)
in the first ?(Ni) steps1
A?			(N.)p'3+2.k, and
r(i) 1
k<(C(Ni)?3)/2 or k=(?(Ni)?3)/2 )i
N1			1
Ni+l			--H			N. .2?(Ni)+21 and
r			recursive s.t. r(i)=k i.o. for every k in N.
102
Let f(x) be the running time on input x of the following
program:
1: 1 ?s 1
2: 1 olusi I
+0
plusO ?
which is 3 for all inputs but Wi and which is 3+2?kj for
Ni Suppose A. is a program which computes f in f steps
a.e. Then ?=r(i) and
3 . J J
1 i A?(Ni) > Aj(Nj) 1.0.
To compute n values of Wi?lOk? and apply p to.a?c:? of them
requires at least n+(n-l) steps. Thus, since A?.(W.) must
Jo+ 1
USC P(NjI10k1) for every k < (?(Ni)?3)/2 such ??at
J
Ai(Ni) # 3+2'k
at least ?(Ni)?6 steps are needed for this purpose. We
know that			A?(N.)
--H? 1 --H< c(Ni)
so there are only 6 steps left for the rest of A			o+s
? (Wi)
computatiol. if ?(Ni) = N.'1O91O91' is computed, then for
infinitely many i it must be conputable by some 6-step
process from N. or from N.IlOk for some k. it is not.
1 1
We have proved the following lemma.
103
Leffina6.5 There is a flowchart interpretatioii J such that
J
A is not proper but such that for every i and k there is
a recursive t such that
t - A? <			+ 2.k
--H k
and
 R--H
--H?			t
We comment that the intent of the' notion of properness,
that it should be no harder to conpute the running tine of
an algorithm than it is to run the algorithm, is honored by
ineasures such as those' described in Lemmas 6.3 and 6.4.
Lei?rna 6.5 really only shows that "properness" should not
be stated in quite so strong a form. Perhaps
E R
--H1
(where L is linear or "close" in sone sense to the identity)
is good enough.
104
?6.3 FurtriorLimensionsofFlexibility
The results in chapters 4 and five show to some extent
the generality of the flowchart neasures, demonstrating how
they may easily be tailored to possess certain properties
or not. The results which follow explore other dimensions of
flexibility exhibited by these measures.
Theorem6.6 For any flowchart interpretation J there is
another interpretation J' such that, for every recursive t,
- R?0g2?
Proof			J' will include encoding functions, a "universal"
function, a halting test, and a decoding function. cod?,
sufO, and sufl are defined as in the proof of Theorem 4.2.
lump = ?x(((x='lokloilol?) & (k=h(x)) & (X(N+2) &
(k'=h(A?. (2?+6+3?l)
o+10k10i10j?			0)
out --H ?x(((x??loklo?lol?) & (k=h(X)) & (XE 2))
min(?1: (O,t1,?2,t3,...?m)EX); 0)
+
halt --H ?x((x='lOklO?lOl?) & (k=h(x)) & (x?N2) &
(x includes a sequence starting with 0))
J n			J
where A. [xl denotes the result of iterating Ai
n times on the set x of i.d.s, and h is the encoding fumc-
tion of Theorem 4.2.
JI
For each program A. we have a program AT(i) which is
equivalent toit, but faster by a logarithm.
105
1:			1			cod3 I
4.
2:			1			sufO 1
+0
i+l:			1 ____
i+2:			1 ____
1 ______
i+4:			2
sufO 1
+0
sufi 1
sufO 1
+0
halt 2
` i+6: 1 out 2
This program computes
??2h(f(i?inPut)))+l+1?2i+1+1)2i
for successive ?, starting with 1, applying jump and halt to
each, until would have halted in i+6+3.j steps, at which
point out decodes the output and the program halts. The
program uses i+2+3?j+l steps to compute A?.(x) if
< 2i+6+3.j
--H1
Thus, if
J > 2i+6+3(j--Hl)
Ai(x)
then
log			> i+6+3j--H3 --H			i+3.j+3
--HI
and so			J
(			RA?0g A?i			O.Z.D.
This says we can always make all conputations easier by
making the interpretations more powerful, an obvious truth.
The log function used here is for convenience of proof only.
Other speed increases are provable. In effect, we can always
speed up the flowchart ?machine".
106
Every complexity measure defines an "order" relation
on the computable functions: f may be said to be nomore
complexthan g iff for each algorithm which computes g
there is an alqorithm for f which is of equal or lower
complexity, i.e.
V t c R, g Rt ? f c Rt
This relation is clearly reflexive and transitive. It
lacks the property of antisymmetry of being a partial
order, but
f "g ( V t c R, g c Rt f E Rt
is an equivalence relation. Looking at the functions,
modulo this relation, we have an alternative concept of
"complexity class", these equivalence classes being
partially ordered. It is natural to ask whether t.?ese
orderings have any properties in common and to what extent
the ordering may vary with the complexity measure. In
the case of the flowchart measures we make a start by
showing that the relation between two functions may be
quite dependent on the interpretation.
107
Theorem6.7 For any total recursive function t there exist
flowchart interpretations I and a and total recursive
functions f and g such that
A1			A1			I
R??x.l			and			g / R?Ax.l			(g c RA?t
a
but			g ? s?x.l			and			f ? R?At
Proof I and a have a set of common functions and predicates,
which nay be chosen to make then universal. In addition,
each has one other function; I has f and a has g. f and g
are defined by a double diagonalization so that g is not
conputable by any t-bounded I-program and so that f is not
comp??table by any t-bounded J-progran. (The details are
similar to previous diagonal constructions we have done.)
Theorem6.8 For any universal flowchart interpretation a
and any recursivo functions r and t there exists an exten-
sion a' gotten by adding a recursive function g to a,
such that, for some recursive function f and some recur--H
sive function 5 > r, if t > 5 ( > r ) then
A1			A1			A1
r			? R?t			g ?
f			t
g ? ?r , f  Rt
Proof f is gotten by diagonalizing over all r-bounded I--H
programs. 5 is any function greater than or equal to the
time needed to compute f by an I-program. g is gotten by
diagonalizing over all t-bounded I-programs. (Again the
details are similar to previous proofs.)
108
Theorem6.9 ror any flowohart interpretation I there is
another flowchart interpretation J such that every I-prog-
ram has an equivalent J-program which uses a single reg-
ister and has complexity lincarly related to the I-progr?m.
rurthermore, for every J-program there is another J-prog-
ram for which the same is true.
Proof It is shown that arbitrarily many registers may
be encoded into a single register and the functions of I
modified to work on the encoded registers without more
than linear loss of time.
The functions and predicates of I are carried over
into J, but modified so as to treat their arguments as
encoding several "registers" plus information about which
"register" is to be treated as argument and, in the case
of functions, which "register" is to receive the result.
To make the "furthermore" clause of the theorem true, J
must also include functions and predicates which bear the
same relation to the modified functions and predicates of
I just described as those do to the unmodified functions
and predicates of I. Since the number of these may be
infinite and we wish to keep J finite, we so this by means
of a universal fumctiom,r0, and a universal predicate, p01.
The encoding and interpretation J are formally defined
as follows: Let F1, ... r be the functions of I and
n
be the predicates. Let <i,j,k,r?,. . .r1> denote
`l'?0(i)?0(j)?0(k)#aCrt)...#r(r2)...$r1
-			109
where
--H			?x( x=y'O1?			?(y)'lO';
x--Hy1l1?			c(y)'111; 0 ),
*			--H			`00., and
$			--H			`01'.
This encodes the indices of the result and argument "reg-
isters", the operation code for the universal operations,
and the "registers",
F' (<i,j			--H <0,0 0 r'			r'>,
p			k,rt,...r1>)			1
for in I, where rn?O for
m-max((i,i)), rn'=rn for n<?,#i,
and r'=F (r.).
1p?
rn1=O for n>&,iLi
p' (<i,?
?			k?r?? ..r1>) --H
for Pp in I and t>j.
P' (<i,j
? k1r? ...r1>) --H Pp(O)
for Pp in I and t<j.
Fm'+1(x) --H sufl(x) --H 2flog2xi+l+?,			(encoding)
--H shift(x) --H sufl(x) - 2?log2xi			(encoding)
F1 (<i
m+3			,j1k,rt,...r1>) = r1.			(decoding)
Fn'+4(<i ?,k,rt1...r1>) --H c(r?)...#?(r2)$r1. (clean-up)
Fo'(<i,j,k,rt,...r1>) --H
for k<m+4, where rn=O for n>?,
m=max(tt,i)), rn=rn for n<t,#i,
for n>&,#i, and rI=Fk'(rj)
110
P0(<i,j,k,rt ...r1>) --H P?'(rj)
for k<n and 1>j.
P01(<i,?,k,rt,...r1>).= ???0?
for k<n and t<j.
For all cases not yet defined, the functions are defined
to yield the identity and the predicates to yield 1.
Thus in the last case given for'P0 the value will always
be 1, since 0 is not decodable into <i,j,k,rt .
A simple inductive argument shows that F a
? na %
are total, even though they are defined recursively:
If k#O there is no problem. For k=O, the only -question
is whether F0,(r?) and P0'(r?) are defined. If r? is not
decodable as <i???'?k'?r?'??..rj> then Fo(rj)trj and
P0,(r?)--Hl (by convention above) If r? can be decoded
then the question is reduced to one about F0(r;..) and
P01(r;..). By nature of the encoding, r;.< r?. Since
smaller than o+l?#*#$ are clearly undecodable, the initial
step of the induction must hold, and we are done.
Given an I-program A1 we can translate it to an
equivalent J-program as follows. For each node i F ?
k
in A we substitute a sequence of nodes which compute
p
<i,j,o,rt,.. .r1> from every string of the form
<x,y,:,r?, ..r1>, followed by a node 1 Fk 1. (The sequence
which computes<i,j,O,r ,...r1> uses Fm+l. Fm+2 and Fm+4
and is dependent only?on i and ?.) For each node
j in Ap we similarly substitute a sequence which
Ill
computes <O,?,O,r?,...r1> in register 1, followed by P0' I.
Znitially, we add a sequence of nodes to compute <O,O,O,r1>
from r1 and. finally, we add a node 1 Pm+3 1 following
each of the provious terminal nodes.
For a J-program what we do is analogous. Each node
i Fk' j is expanded to a computation of <i,j,k,r?,. . .r1>
ollowed by a node 1 F0 1 and similarly for predicates.
The complexity of the resulting program bears a
simple relationship to the complexity of the original
program. A constant number of steps are added at the
beginning and at the end. Additionally, each step of the
original program is expanded into an encodinq sequence
and a "computational" step. The length of the encoding
sequence is bounded by a constant for each program, since
the program and interpretation are finite. The complexity
of the resulting single-register program can thus be
bounded by c1 plus c2 times the complexity of the original
prograrn, where c1=lO and c2 is dependent on the size of
the interpretation and the number of registers used in the
program.			Q.E.D.
Although the previous theorem is stated in terms of
I-argument interpretations, by the convention we made in
?l.3, it could also be proved for the n-ary interpretations
by more complex encoding.
112
Others have defined notions of program which deal with
what are supposedly more general domains. The idea is that
for full generality one would like to be able to think?of
the programs as operating or? ob3ects which might be any one
of the numerous data structure conceivable--H arrays, stacks1
queues1 lists, ... The "power" of a class of uninterpreted
flowcharts as functionals may depend on the domain. In terms
of interpreted flowcharts, however, there is no reason why
the domain cannot be restricted to the integers. It is well
known that all partial recursive functions can be computed
by programs with a single variable over the integers and a
proper finite interpetation. In effect1 the one variable
becomes the entire data space of the computation. By suit-
able encodings the operations of the program may work on
various portions of it in any way that is desired.
1l?
Remark The preceding theorem is particularly significant
in view of Ianov's work ?l6I on schenata. Despite the fact
that schematic equivalence (whether two schemata define the
same program under all interpretations) is undecidable for
schemata with more than one free variable [21], Tanov has
shown that equivalence is decidable for schenata with a sin--H
gle free variable, and that for such schenata each may be
reduced to a simple canonical forn. Since we cannot in-
crease the complexity of a program by more than a constant
factor in going to an interpretation where only a single
variable is necessary, we can translate any program (in
linear time if we have a zero-function) to a single-varia-
ble program, perform any sort of optinization we wish, using
Zanov?s equivalence procedure, and translate it back to the
original interpretation, again without any more than a lin-
ear increase in complexity. Thus, if there is anything of
higher than linear order to be gained by optinization on
the schema level we can achieve it regardless of how many
free variable5 we allow.
A further consequence of this theoren is that all
previous proofs of theorems about classes of complexity
bounds which are closed under multiplication by a constant
also hold for the same theorems if we restrict ourselves
to single-register programs.
Conclusion
?7.l
o??nTarvofr?esults
We have shown that the flowchart complexity measures
form a diverse class, useful in demonstrating that certain
properties proposed as requirements for "natural" measures
need not be true for all natural measures. Finite invariance
and properness are examples of such properties. We believe
that there are others.
We have shown that nondeterminism is meaningful in a
very general framework, but that its effect on the complex-
ity of functions is dependent on the specific model of
computation.
Im general, we have taken a step toward isolating some
of the nonessential properties of natural measures from the
sore essential ones. Two properties which seem essential,
at least so far, we have called "composition" and "finite
freedom"
We have shown that the flowchart measures are well-
behaved in two senses. .`4any of the complexity classes are
provably r.e. This is because we may perform certain
transformations on the flowcharts, knowing the effect they
will have on the programs without knowing exactly what the
programs do. These schematic manipulations also allow us
to do simple translations, which in some cases produce
translated programs that are reasonably efficient.
114
115
?7.2 PossibilitiesforFurtherResearch
A. Loose Ends
?n the course of this research several questions
arose which were not answered. we have broken these into
two groups. Th? `?loose ends are simple questions which
represent gaps in our results. Those marked by * we believe
we see how to answer, although time has prevented us from
including the finished proofs here.
(1) Are the flowchart complexity classes r.e. for non-
ultimately-increasing and nonconstant time bounds?
(2) Can better bounds on translation cost for "worst case"
programs be found for translations:
(a) from one flowchart interpretation to another?
(b) from a G?del numbering to a flowchart G?del
numbering?
(c) yielding an isomorphism between flo:'chart
interpretations?
(3) Can the complexity of the resulting program be
simply bounded for translations between flowchart
interpretations with equivalent complexity measures
under weaker conditions than those of Corollary 3.2?
(4) Are the interpretations where DP=NDP r.e.?
(5) Are there a t' and a t such that
D?			A?			A?			?J
R?tI - R?t - Rt $ R?t			?
That is, are there "gaps" in the nondeterministic classes
where there are none in the deterministic classes?
116
(6)* We know we can always make a function "easy" by adding
to the interpretation. Can we aiwava change the interpreta-
tion to make a specific function harder to compute?
(7) Can some well-known "Natural" measure be sinulated
more precisely by a flowchart measure than we have done?
That is, so that the complexity classes are the sane for
all bounds?
(?)t Can we give examples of universal flowchart interpreta-
tions which give finitely-invariant or pr?per measures?
(9)t Are there any other "natural properties (10] which either
hold for all flowchart measures or are interpreation-
dependent (e.g., conformity, parallelism, downward diagon-
alization, denseness)?
(lO)* Can recursive oracles be found for which the deter-
minism-nondeterminism question for linearly-bounded
automata with oracles, hDL?--DL, may be answered "yes"?
(We know there are oracles for which the answer is "no".)
(11) May a flowchart interpretation be N-universal
without being universal? (See p. 20.)
ll?
B. Open Areas
The remaining questions are much broader in scope,
and cannot be asked quite so simply.
(1) [General Nondeterminismi. What kinds of functions can
be computed nondeterministically if we say that a nondeter--H
ministic algoritnn computes a set-valued function,
converging only when all computations have terminated? How
much more powerful is this model than the one where all
computations are halted with the first to terminate? Are
there other interesting notions of nondeterministic algo-
ritnm or of parallel computation with which to compare these?
(2) (Conplexity of Flowcharts] How does the complexity of a
flowchart as a graph relate to its complexity as an algorithm?
For example, are planar graphs less powerful as flowcharts
than nonplanar graphs? This area might border on work which
has been done in program schemata.
(3) [General Step Measures] We regard the flowchart
measures as "true" step measures because there is a recog-
nizable computational operation for each "step" counted in
the measure. Is there a nice abstract characterization of
measures which have this "property"? Can we go to an
abstract notion of "true" step measure without losing all of
the nice "natural" properties that we have not lost already
by accepting the flowchart measures as natural?
*[ We have some conjectures and preliminary results in this
area, hinted at in 1.5, which do not properly fall within
the range of this thesis.]
lie
i7.3 Step?easures
Y. Weihrauch [27] has shown that an" fllum measure
:aay be realized as a submeasure of a flowchart measure.
This means, as Hartmanis [101 has e?plained, that we cannot
accept as an Irnprovement" on the Blum axiomatization any
set of properties which are transitive with respect to
submeasures. The example he gives of a property which may
hold for a measurewithoutholding for all of its suomeasures
is finite invariance, which we have shown to be excessively
restrictive.
Although we have stated two properties which are
characteristic of flowchart measures, and natural at least
in that sense, we do not believe that they are sufficient
to define a "natural madsure. The naturalness of a
`neasure seems unavoidably connected to the existence of a
corresponding model of computation, with recognizable steps
and intgrmediate results related in some way to the results
of shorter computations. We believe that the existence of
a partial result (produced by a recognizable operation
from a previous result) for each "step" counted should
be a basic requireTent for all step measures. The flowcharts
do this, but have a good deal more structure than is needed.
It should be possible to define a structure more abstract
than the flowcharts which still has the properties we admire
in them.
119
A possible start would be to hypothesize a single
data space (ropresented by an ante?er variable, in the
manner of Ianov [16]), with a set of unit-cost operations
(a recursiva, or finite, set of recursive functions), a
pair of input-output encoding-decoding functions, and
a set of algorithms (next-operation choice functions
dependent only on the result of the previous step). The
operations would determine a natural congruence relation
and a metric on the space of possible partial results
(the orbit of the range of the input encoding under the
action of the free group generated by the operat?ons).
The space of partial results would admit a natural parti-
tion under the obvious equivalence relation defined by
the algorithms. The equivalence classes so defined could
naturally be called "states". One might even go so far
as to require that the partial results decompose into.a
Cartesian product of the "states" and another ("data")
space, although this seems unnecessary. The axioms would
basically be closures on the set of algorithms, to assure
the possibility of "programming" in some natural manner.
Xt is hoped that a few such closures would be sufficient
to get son?e interesting properties about the step measures
(operation counts)
[1]
[2]
References
slum, M. "A .?achin'" Independent Theory of the
Complexity of Recursive Functions", JACM, Vol.
No. 2, 1967, pp. 322-336.
15,
Borodin, A., R.L. Constable and J.F. iiopcroft.
"Dense and Non-Dense Families of Complexity Classes",
TEES Conference Record of 1969 Symposiun ?n
Switching and Automata Theory, 1969, pp. 7-19.
[3] ChaAdra, Ashok K. "On the Properties and
Applications of Program Schemas?', Stanford Computer
Science Department Technica# Report 73-336, 1973.
[41 Church, A., TheCalculiofLa?bdaConversion,
Princeton University Press, 1941.
[51
[61
[7]
Constable, R.L. "Type Two Computational Complexity",
Procedings of Fifth Annual ACM Symposium on Theory
of Computing, 1973, pp. 108-121.
Cook, S.A. "The Complexity of Theorem-Proving
Procedures", Third Annual ACM Symposium on
Theory of Computing, 1971, pp. 151-158
Cook, S.A. "Linear Time Simulation of Deterministic
Two-Way Pushdown Automata", InforinetiunPrv????ing71,
Nortn-Molland, 1972.
[8] Harary, F., urathTheorv, Addison-Wesley, .1969
[91
Hartmanis, J. "Computational Complexity of Random
Access Stored Proqram Machines", Mathematical Systems
Theory, Vol. 5, No. 3, 1971, pp. 232-245.
120
?2l
rioi
[11)
[12)
[13]
Hartmanis, J. "On the Problem of Finding Natural
Computational Complexity Measures", Technical
Report 73-175, Department of Computer Science,
Cornell University, 1973.
IIartmanis, J. and T.P. Baker "On Simple G?del
Numberings and Translations", Technical Report
73-179, Department of Computer Science, Cornell
University, 1973.
Hartmanis, J. and J.E. Hopcroft' "An Overview of
the Theory of Computational Complexity", JACM,
Vol. 18, No. 3, 1971, pp. 444-475.
Hartmanis, J. and H.B. Hunt III "The LBA Problem
and its Importance in the Theory of Computing",
Technical Report 73-171, Department of Computer
Science, Cornell University, 1973.
[14] Hartmanis, J. and R.E. Stearns "On the Conputational
Complexity of Algorithms", TransactionsoftheAMS,
Vol. 117, 1965, pp. 285--H306.
[15) Hopcroft, J.E. and J.D. Ullman, FormalLanguages
andtheirRe1atj??Automata, Addison-?esley,
1969, p. 96.
[16] Ianov, Iu. I., "The Logical Schemes of Algorithms",
ProblemsofCybernetics (USSR) Vol. 1, 1960,
pp. 82-140
[17) xarp, R.M. "Reducibilities Among Comoinatorial
Problems", in R. Miller and J. Thatcher (eds.),
Complexityot?onouter?emoutations, Plenum, 1972,
pp. 85--H104.
Kuroda, S.v. "Classes of Languages and Linearly-
Rounded Automata", InformationandControl, Vol. 2,
1964, pp. 207--H223.
[19]
122
tl9]
(201
Landweber, L.H. and E.L. Robertson "Rscurrive
Properties of Abstract Complexity Classes",
?, Vol.19, No. 2, 1972, pp. 29?--H3oS.
Le?is, F.D. "The Enumerability and Invariance of
Complexity Classes", SJCS, Vol. 5, No. 3, 1971,
pp. 286--H303.
[21] Luckham, D.C., D.M.R Park and M.S. Paterson
"On Forrnalised Computer Programs", JCSS, Vol.4,
1970, pp. 220--H249.
[22] ncCarthy, J. et al, TheLISP1.5Proorarnrner?s
M?nual, NIT Press, 1968.
[23]
(24]
Mehihorn, K. `On the Size of Sets of Computable
Functions", Technical Report 73-164, Departni-.?t
of Computer Science, Cornell University, l97J.
Paterson, "Equivalence Problems in a Nodel of
Computation", Doctoral Dissertation, Canbridge
University, 1957.
[25] Rogers, ?., Jr., Theurvof??cUt?iveFunctiun?
andEffect?veCom"utabilitv, McGraw-Hill, l9E7.
[261 Simon, J.: Personal cotmnumication.
[27] Weihrauch, K.: personal co?",unication.