M3

High-level description of a Turing Machine that decides whether a graph G is connected

M2 = “On input string <G>, the encoding of G:

1. Select the first node of G and mark it.
2. Repeat the following stage until no new nodes are marked:
3.     For each node in G, mark it if it is attached by an edge to a node that is already marked.
4. Scan all the nodes of G to determine whether they are all marked. If yes, accept; otherwise, reject.