Here’s an example where choice of
encoding does matter. Say we want to encode the
set CG of graphs which have countably-many nodes but where each node can only have finitely many neighbors.
One straightforward
encoding of this
set CG is as follows.
Fix some size-
ω linear order over the nodes of
CG, and also
fix a size-
ω linear order over the edges of
CG. Now encode
CG as a
turing machine which enumerate over all nodes and edges of
CG, alternating between emitting a node and emitting an edge, and following the fixed
linear orders. By following orders of size
ω we guarantee that all nodes and edges are eventually reached, and so a consumer of this
encoding will discover all facts about the graph in
finite time.
Another
encoding of this
set CG is as follows.
Fix some size-
ω linear order over the nodes of
CG. Encode
CG as a pair of
turing machines. The first
turing machine enumerates over the nodes in
CG, following the specified
order. The second
turing machine is a
function which accepts a node in
CG and enumerates all of its (finitely-many) neighbors.
Both of these seem like potentially-reasonable
encodings for
CG, but unfortunately do not agree on computability properties. Say we want to write a
turing machine which, given an
encoding of
CG and two nodes of
CG, will output
1 if they are adjacent and
0 if they are not. Using the second
encoding for
CG, this is possible; one can call the provided nieghbor
function. Using the first
encoding, however, this is not possible. Say we are trying to find if nodes
n,m are adjacent. To do so, we iterate through the node/edge enumeration; if we eventually find an edge containing
n and
m, then we know they are adjacent. If they are not adjacent, we will never find an edge. However, at no point in our iteration will we know that we will never find an edge: it will always be a possibility that the next item iterated is an edge between
n and
m. Hence, it’s impossible to conclude with a negative result.