[FOM] Comment on Church's Thesis

[Harvey Friedman]

We will make use of digraphs. These are directed graphs with no multiple
edges. Loops are allowed.

Digraphs are pairs (V,E), where V is the set of vertices and E is the set of
edges, which are taken to be ordered pairs from V.

We will be using pairs of digraphs

[(V,E), (V',E')]

where we care about the intersection of V and V', which at one extreme may
be empty, and at the other extreme may be V.

We say that two pairs of digraphs

[(V,E), (V',E')]

and 

[(V*,E*), (V*',E*')]

are isomorphic if and only if there is a mapping from V union V' one-one
onto V* union V*' which is a graph isomorphism from (V,E) onto (V*,E*) and a
graph isomorphism from (V',E') onto (V*',E*').

Let k >= 1. We say that these two pairs of digraphs are k-equivalent if and
only if 

i) for all A containedin V union V' of cardinality at most k, there exists B
containedin V* union V*' such that

[(V,E)|A, (V',E')|A]

and  

[(V*,E*)|B, (V*',E*')|B]

are isomorphic;

ii) for all B containedin V* union V*' of cardinality at most k, there
exists A containedin V union V' such that

[(V,E)|A, (V',E')|A]

and 

[(V*,E*)|B, (V*',E*')|B]

are isomorphic.

A digraph transition system is a pair (R,H), where

1) R is a class of pairs of finite digraphs such that for some k >= 0, the
elements of R respect k-equivalence;
2) H is a finite digraph.

A finite graph G is said to be accepted by the digraph transition system
(R,H) if and only if there is a finite sequence of digraphs

G = G0,G1,...,Gn = H

such that n >= 0, and for all 0 <= i < n, R(Gi,Gi+1).

THEOREM. The classes of finite digraphs that are the acceptance set under
some digraph transition system are exactly the recursively enumerable
classes of finite digraphs (in the obvious sense of r.e. sets of isomorphism
types of finite digraphs).

Harvey Friedman