A user-friendly Introduction to Computability via Turing Machines (and “Church’s Thesis”) Part II

We have stopped short our exposition—in Part I of these notes—due to a “publication deadline”.^{†}

This is Part II. Section numbering resumes from where we stopped in Part I. In Section 6 we had hoped to include material on semi-decidable relations. We did not manage to include more than the definition and a remark. We reproduce both below—adding the notation “P_{∗}”—and take it from there.

7. Semi-decidable relations (or sets)

7.1 Definition. (Semi-recursive or semi-decidable sets)

A relation Q(x⃗_{n}) is semi-decidable or semi-recursive iff there is a TM, M, which on input x⃗_{n} has a (halting!) computation iff x⃗_{n} ∈ Q. The output of M is unimportant!

A less civilized, but more mathematically precise way to say the above is: A relation Q(x⃗_{n}) is semi-decidable or semi-recursive iff there is an f ∈ P

such that

Q(x⃗_{n}) ≡ f(x⃗_{n}) ↓  (1)

Sipser [2] calls these relations recognizable. Some others call them recursively enumerable.^{‡}

The set of all semi-decidable relations we will denote by P_{∗}.^{§} □ 7.2 Remark. Yet another way to say (1) is:

†I had set myself a deadline, the weekend of Nov. 11–12, to upload a substantial amount of notes.

‡To see why, visit Section 8.

§This is not a standard symbol in the literature. Most of the time the set of all semirecursive relations has no symbolic name! We are using this symbol in analogy to R_{∗}—the latter being fairly “standard”.

Intro to Computability via TMs—Part II \begin{matrix}c \\ ◯ \end{matrix} by George Tourlakis

A relation Q(x⃗_{n}) is semi-decidable or semi-recursive iff there is an e ∈ ℕ such that

Q(x⃗_{n}) ≡ ϕ_{e}^{(n)}(x⃗_{n}) ↓  (2)

The following figure shows the two modes of handling a query, “x⃗_{n} ∈ A”, by a TM.

Here is an important semi-decidable set.

7.3 Example. H is semi-decidable (recognizable, as our text ([2]) prefers to say). To work within the formal definition (7.1) we note that the function λx.ϕ_{x}(x) is in P.

Indeed, to compute it for any input value x do:

(a) Go and fetch machine M_{x}

(b) Run M_{x} on input x

(c) Output whatever output (if any!) is generated in step (b) above.

CT then validates our claim.

But

x ∈ H iff ϕ_{x}(x) ↓

By Definition 7.1 (statement labeled (1)) we are done.

Alternatively, we argue intuitively, using the figure for a recognizer, above: Our recognizer (for x ∈ H) does the following: Well, exactly (a)–(c) above!

If it halts, we take it to mean that x ∈ H is true (and we are right too!). If it never halts (something we will never know), then this corresponds correctly to the “answer” x ∉ H. □

7.4 Example. Any recursive relation A is also semi-recursive.

Indeed, intuitively, all we need to do to convert a decider for x⃗_{n} ∈ A into a recognizer is to “intercept” the “print 1”-step and convert it into an “infinite loop”,

while(1)

{ }

By CT we can certainly do that via a TM implementation.

A more elegant way (which still invokes CT) is to say, OK: Since A ∈ R_{∗}, it follows that c_{A}, its characteristic function, is in R.

Define a new function f as follows:

f(x⃗_{n}) = \begin{cases}0 & if c_{A}(x⃗_{n}) = 0 \\ ↑ & if c_{A}(x⃗_{n}) = 1 \end{cases}

This is intuitively computable (the “↑” is implemented by the same while as above).

Hence, by CT, f ∈ P. But

x⃗_{n} ∈ A ≡ f(x⃗_{n}) ↓

because of the way f was defined. Definition 7.1 rests the case.

Clearly, the “elegant” way is just a wordy way to repeat the “informal” way. In what follows we will prefer the informal way of doing things, most of the time. □

An important observation following from the above examples deserves theorem status:

7.5 Theorem. R_{∗} ⊂ P_{∗}

Proof. The ⊆ part of “⊂” is Example 7.4 above.

The ≠ part is due to H ∈ P_{∗} (7.3) and the fact that the halting problem is unsolvable (H ∉ R_{∗}).

So, there are sets in P_{∗} (e.g., H) that are not in R_{∗}. □

What about \overline{H}, that is, the complement

\overline{H} = ℕ − H = \{x : ϕ_{x}(x) ↑\}

of H?

The following general result helps us handle this question.

7.6 Theorem. A relation Q(x⃗_{n}) is recursive if both Q(x⃗_{n}) and ¬Q(x⃗_{n}) are semi-recursive.

Before we proceed with the proof, a remark on notation is in order.

In “set notation” we write the complement of a set, A, of n-tuples as \overline{A}. This means, of course, ℕ^{n} − A, where

ℕ^{n} = \underbrace{ℕ × ⋯ × ℕ}_{n copies of ℕ}

In “relational notation” we write the same thing (complement) as

¬A(x⃗_{n})

Similarly, “set notation”: A ∪ B, A ∩ B “relational notation”: A(x⃗_{n}) ∨ B(x⃗_{n}), A(x⃗_{n}) ∧ B(x⃗_{n})

Back to the proof. Proof. We want to prove that some TM, N, decides

x⃗_{n} ∈ Q

We take two recognizers, M for “x⃗_{n} ∈ Q” and M′ for “x⃗_{n} ∈ \overline{Q}”,^{†} and run them—on input x⃗_{n}—as “co-routines” (i.e., we crank them simultaneously).

If M halts, then we stop everything and print “0” (i.e., “yes”).

If M′ halts, then we stop everything and print “1” (i.e., “no”).

CT tells us that we can put the above—if we want to—into a single TM, N. □

7.7 Remark. The above is really an “iff”-result, because R_{∗} is closed under

complement.

If we believe the latter claim for a moment,^{‡} we then see how the converse of Theorem 7.6 goes:

If Q is in R_{∗}, then so is \overline{Q}, by closure. By Theorem 7.5, both of Q and \overline{Q} are in P_{∗}.

Now to see why R_{∗} is closed under complement, let Q be in R_{∗}. Let M be a decider for Q. A decider M′ for \overline{Q} is a trivial modification of M:

Simulate M on input x⃗_{n}. If M wants to print “0” and halt, print “1” instead and halt. If M wants to print “1” and halt, print “0” instead and halt. “Mathematically”, this is just the observation that

c\overline{Q}(x⃗_{n}) = \begin{cases}0 & if c_{Q}(x⃗_{n}) = 1 \\ 1 & if c_{Q}(x⃗_{n}) = 0 \end{cases}

†We can do that, i.e., M and M′ exist, since both Q and \overline{Q} are recognizable.

‡We have a closer look at closure properties in Section 9.

Intro to Computability via TMs—Part II \begin{matrix}c \\ ◯ \end{matrix} by George Tourlakis

CT performs its obvious duty.

7.8 Example. \overline{H} ∉ P_{∗}.

So, here is a horrendously unsolvable problem! This problem is so hard it is not even semi-decidable!

Why? Well, if instead it were \overline{H} ∈ P_{∗}, then combining this with Example 7.3 and Theorem 7.6 we would get H ∈ R_{∗}, which we know is not true. □

Recall the concept of reducibility of one set to another:

7.9 Definition. (Strong reducibility) For any two subsets of ℕ, A and B, we write

A ≤_{m} B

or more simply

A ≤ B  (1)

pronounced A is strongly reducible to B, meaning that there is a recursive function f such that

x ∈ A ≡ f(x) ∈ B  (2)

We say that “the reduction is effected by f”. □

“Small print”: A ≤_{m} B is also pronounced A is many-one reducible to B, hence the “m”.^{†} “Many-one” is a name due to the fact that (usually) many x values (in A) are mapped into the same value f(x) (in B)—see (2) above. If f is a “1-1 function”, that is, whenever f(a) = f(b) then a = b, then we say that the reducibility is 1-1. This is so important that we have a symbol for it ([1]): A ≤_{1} B.

We have seen in the previous section that, intuitively, “B is more ‘difficult’ than A (to decide)”, in the special cases where A = H.

Indeed, when (1) holds, then “B is more difficult than A to either decide or recognize” in the following very precise sense:

7.10 Theorem. If A ≤ B in the sense of 7.9, then

(i) if B ∈ R_{∗}, then also A ∈ R_{∗}

(ii) if B ∈ P_{∗}, then also A ∈ P_{∗}

Proof.

†[2] attributes the “m” to the term “mapping-reducibility”. We follow [1] in our choice of terminology.

Intro to Computability via TMs—Part II \begin{matrix}c \\ ◯ \end{matrix} by George Tourlakis

(i) Let B ∈ R_{∗}, and let f ∈ R effect the reduction.

Let M be a decider for “x ∈ B”.

Here is how to decide “x ∈ A”:

(a) Compute f(x) (for the given x). This computation terminates!

(b) Use the result f(x) as input to the decider M. That is, call M with input f(x). If M prints “0”, then print “0” and halt. If M prints “1”, then print “1” and halt. By CT we can build a single TM, M′, that carries out the steps (a)–(b). Clearly, M′ behaves correctly: It halts with a “0” if f(x) ∈ B—that is, if x ∈ A (by A ≤ B—see 7.9). It halts with a “1” if f(x) ∉ B— that is, if x ∈ A is false (by A ≤ B). Thus, A ∈ R_{∗}

(ii) Let B ∈ P_{∗}, and let f ∈ R effect the reduction.

Let N be a recognizer for “x ∈ B”.

Here is how to semi-decide “x ∈ A”:

(1) Compute f(x) (for the given x). This computation terminates!

(2) Use the result f(x) as input to the recognizer N. That is, call N with input f(x). If N ever halts, then halt. By CT, there is a TM N′ that implements the algorithm (1)–(2). This N′ behaves correctly: If x ∈ A, then f(x) ∈ B, thus N′ halts (the call to N “returns”). If x ∉ A, then f(x) ∉ B, thus the call to N (input f(x)) does not return. So N′ never returns either. Thus, A ∈ P_{∗}

□

Taking the “contrapositive”, we have at once:

7.11 Corollary. If A ≤ B in the sense of 7.9, then

(i) if A ∉ R_{∗}, then also B ∉ R_{∗}

(ii) if A ∉ P_{∗}, then also B ∉ P_{∗}

We can now use \overline{H} as a “yardstick” and discover some more unrecognizable (= NOT semi-recursive) sets.

7.12 Example. The set A = {x : ran(ϕ_{x}) = ∅} is not semi-recursive.

Recall that “range” for λx.f(x), denoted by ran(f), is defined by

{x : (∃y)f(y) = x}

As with the reducibility arguments of the previous section, we will assume that we can semi-decide

x ∈ A

and then try to use this to semi-decide

a ∈ \overline{H}

by finding a recursive h such that

a ∈ \overline{H} iff h(a) ∈ A

In short, we will try to show that

\overline{H} ≤ A  (1)

If we can do that much, then Corollary 7.11 will do the rest. Well, define

f(a, x) = \begin{cases}0 & if ϕ_{a}(a) ↓ \\ ↑ & if ϕ_{a}(a) ↑ \end{cases}

Here is how to compute f:

Given a, x, ignore x. Fetch machine M_{a} from the standard listing, and call it on input a. If it ever halts, then print “0” and halt everything. If it never halts then you will never return from the call, which is the correct behaviour for f(a, x).

By CT, f = ϕ_{e}^{(2)} for some e ∈ ℕ. By the parametrization theorem, there is a recursive h such that

f(a, x) = ϕ_{e}^{(2)}(a, x) = ϕ_{h(a)}(x), for all a, x

Therefore,

ϕ_{h(a)}(x) = \begin{cases}0 & for all x if ϕ_{a}(a) ↓ \\ ↑ & for all x if ϕ_{a}(a) ↑ \end{cases}  (2)

hence,

ϕ_{h(a)} has empty range iff ϕ_{a}(a) ↑ (Otherwise the range is {0})

Another way to say the above (bring in A!) is to say

a ∈ \overline{H} iff h(a) ∈ A

which is (1) above! Done. □

7.13 Example. The set B = {x : ϕ_{x} has finite domain} is not semi-recursive.

This is really easy (once we have done the previous example)! All we have to do is “talk about” our findings, above, differently!

We use the same f,

f(a, x) = \begin{cases}0 & if ϕ_{a}(a) ↓ \\ ↑ & if ϕ_{a}(a) ↑ \end{cases}

and the same h as above.

Note that the following statement is the same as (2) of the previous example, but in different notation!

ϕ_{h(a)} = \begin{cases}λx.0 & if ϕ_{a}(a) ↓ \\ ∅ & if ϕ_{a}(a) ↑ \end{cases}  (3)

Recall that “∅” denotes both the empty set and the empty function. In the bottom case above it is the empty function. Thus,

ϕ_{h(a)} has finite domain, indeed (empty!) iff ϕ_{a}(a) ↑

Another way to say the above (remember B?) is to say

a ∈ \overline{H} iff h(a) ∈ B

thus

\overline{H} ≤ B

and 7.11 does the rest. □

7.14 Example. The set C = {x : ran(ϕ_{x}) is finite} is not semi-decidable.

Here we cannot reuse (3) above, because both cases lead to finite range. We want one case to lead to finite range, the other to infinite.

Aha! This motivates us to choose a different “f” (hence a different “h”), and retrace the steps we took above.

We want, as usual, to show that

a ∈ \overline{H} ≡ k(a) ∈ C  (i)

for some recursive function k. OK, define

g(a, x) = \begin{cases}x & if ϕ_{a}(a) ↓ \\ ↑ & if ϕ_{a}(a) ↑ \end{cases}  (ii)

Here is an algorithm for g:

Given a, x. Fetch machine M_{a} from the standard listing, and call it on input a. If it ever halts, then print “x” and halt everything. If it never halts then you will never return from the call, which is the correct behaviour for g(a, x).

By CT, g is partial recursive, thus g = ϕ_{e}^{(2)} for some e. By parametrization, there is a recursive k such that

g(a, x) = ϕ_{e}^{(2)}(a, x) = ϕ_{k(a)}(x), for all a, x

Thus, by (ii)

ϕ_{k(a)} = \begin{cases}λx.x & if ϕ_{a}(a) ↓ \\ ∅ & if ϕ_{a}(a) ↑ \end{cases}

or, more suggestively,

ϕ_{k(a)} = \begin{cases}has infinite range (all of ℕ) & if ϕ_{a}(a) ↓ \\ has finite range (empty) & if ϕ_{a}(a) ↑ \end{cases}

In short, (i) holds. By Corollary 7.11, “x ∈ C” cannot be recognizable! □

Enough “negativity”! Here is an important “positive result” that helps to prove that certain relations are semi-decidable:

7.15 Theorem. (Projection theorem) A relation Q(x⃗_{n}) is semi-recursive iff there is a recursive relation S(y, x⃗_{n}) such that

Q(x⃗_{n}) ≡ (∃y)S(y, x⃗_{n})  (1)

Q is obtained by “projecting” S along the y-co-ordinate, hence the name of the theorem.

Proof. if-part. Let S ∈ R_{∗}, and Q be given by (1) of the theorem. We show that some M semi-decides

x⃗_{n} ∈ Q  (2)

Here is how:

proc Q(x⃗_{n})

y ← 0 /* Initialize “search” */

while (c_{S}(y, x⃗_{n}) = 1) /* This call always terminates since S ∈ R_{∗} */

{

y ← y + 1

}

By CT, there is a TM N that implements the above pseudo-code. Clearly, this TM semi-decides (2).

only if-part. This is more interesting because it introduces a new prooftechnique:

So, we now know that Q ∈ P_{∗}, and want to show that there is an S ∈ R_{∗} for which (1) above holds:

Well, let M semi-decide x⃗_{n} ∈ Q.

Define S(y, x⃗_{n}) as follows:

S(y, x⃗_{n}) ≡^{by Def} \begin{cases}0 & if M on input x⃗_{n} halts in exactly y steps \\ 1 & otherwise \end{cases}

Clearly, S(y, x⃗_{n}) is decidable. Indeed, here is how to decide it:

Given an input ⟨y, x⃗_{n}⟩, the algorithm is to crank M (the machine for Q) on input x⃗_{n} and keep track of the number of steps of M as it computes. If at its y-th step M halts, then print “0” and halt everything.

If M is still cranking at the y-th step, then print “1” and halt everything. Finally, if M has halted before its y-th step, then again print “1” and halt

everything.

By CT, the above algorithm can be formalized into a TM, N, which decides S, i.e., S ∈ R_{∗}.

Now it is trivial that (1) holds, for we have the equivalences

Q(x⃗_{n}) ≡ For some y, M, on input x⃗_{n}, halts in exactly y steps

and

S(y, x⃗_{n}) ≡ M, on input x⃗_{n}, halts in exactly y steps

□

Here is an application:

7.16 Example. The set A = {⟨x, y, z⟩ : ϕ_{x}(y) = z} is semi-recursive. Indeed, let the relation Q(w, x, y, z) be defined as

Q(w, x, y, z) ≡^{by Def} M_{x} with input y produces output z in exactly w steps

Q is recursive (by CT), for here is how to decide it:

Given input ⟨w, x, y, z⟩. Fetch M_{x}. Crank it for exactly w steps with input y, and then halt the simulation. If (and only if!), at this w-th step of the simulation, M_{x} actually has halted on its own (had a terminal ID) and has produced the (numerical) output z on its tape, then halt everything and print “0”. Otherwise, halt everything and print “1”.

Clearly,

A(x, y, z) ≡ (∃w)Q(w, x, y, z)

and we are done by the Projection Theorem. □

8. Why “Recursively Enumerable”?

In this section we explore the rationale behind the alternative name “recursively enumerable”, in short “r.e.”, for semi-recursive relations. To avoid cumbersome codings (of n-tuples, by single numbers) we restrict attention to the one variable case.

We show that 8.1 Theorem. (What’s behind the name “r.e.”)

Any non empty semi-recursive relation A (A ⊆ ℕ) is the range of some (emphasis: total) recursive function of one variable.

Conversely, every set A such that A = ran(f)—where λx.f(x) is recursive— is semi-recursive (and, trivially, nonempty).

Thus, the semi-recursive relations are exactly those that we can algorithmically enumerate, by a recursive function.^{†} Hence the name “r.e.”, replacing the non technical “algorithmically” by the technical “recursively”.

Note that we had to hedge and ask that A ≠ ∅, because no recursive function (remember: these are total) can have an empty range.

Proof. (A) We prove the first sentence of the theorem. So, let A ≠ ∅ be semirecursive.

Case 1. We look at the “hard case” first, where A is an infinite set.

By the projection theorem (7.15) there is a recursive relation Q(y, x) such that

x ∈ A ≡ (∃y)Q(y, x), for all x  (1)

Let M be a TM that decides Q(y, x).

Here is an algorithm that algorithmically lists all of A:

Form two lists, List 1 and List 2:

List 1 is an algorithmic listing of all possible inputs ⟨y, x⟩ for M (the machine that we said exists, and decides Q(y, x)).

That is, in List 1 we list

All strings 1^{y+1}01^{x+1}, for y = 0, 1, 2, … and x = 0, 1, 2, … by length, and in each length group lexicographically, taking 0 < 1

For example we list (in the length-6 group) as follows

101111, 110111, 111011, 111101

For each 1^{y+1}01^{x+1} that is listed, run machine M (M always halts, being a “decider”). If M prints a “0”, then add x to List 2.

Comment. This is so because a “0” printout means Q(y, x) is true, hence, by (1), x ∈ A is true.

We can now use the algorithmic listing, List 2, to compute a total function λx.f(x), such that

A = ran(f) = {f(x) : x ∈ A}  (2)

Given x, go down the list List 2^{‡} until the x-th entry is found.

†Sipser [2] talks of “enumerators.

‡We have said, on many occasions, “go down a(n algorithmic) list until you find the x-th entry”. This means, of course, that you generate the list, algorithmically—from scratch— and stop exactly once the x-th entry has been generated. It does not mean that an entire infinite list just sits there and is being “searched”!

Intro to Computability via TMs—Part II \begin{matrix}c \\ ◯ \end{matrix} by George Tourlakis

Since the list “List 2” of all of A is generated algorithmically, and has infinite length, the x-th item exists, and will be (algorithmically) found.

Output that item and halt.

Clearly, this f satisfies (2). By CT, f is in R (since it is total, and algorithmic).

Case 2. The finite case. Say A = {a_{0}, …, a_{k}}, where I have listed its members in ascending numerical order (k ≥ 0, since A ≠ ∅). The following f is algorithmic (table look-up!) and does the job (by CT, it is (total) recursive).

f(x) = \begin{cases}a_{0} & if x = 0 \\ a_{1} & if x = 1 \\ a_{2} & if x = 2 \\ ⋮ & ⋮ \\ a_{k−1} & if x = k − 1 \\ a_{k} & if x ≥ k \end{cases}

(B) Proof of the second sentence of the theorem. So, let (2), above, hold. The relation f(y) = x is decidable. Indeed, (using CT) given the input ⟨y, x⟩, compute f(y). This will eventually produce a number z as output (f is recursive!). If x = z then print “0” and halt, else print “1” and halt.

Since x ∈ A ≡ (∃y)(f(y) = x), we are done by the Projection Theorem. □

9. Some closure properties of decidable and semi-decidable relations

9.1 Theorem. R_{∗} is closed under all Boolean operations, ¬, ∧, ∨, ⇒, ≡.

Proof. It suffices to prove closure under ¬ and ∨.

The case for ¬ has already been witnessed: Any decider can be trivially converted to a decider of the negation (or complement) by reversing the “reporting”: “1” for “0”, and “0” for “1”.

Let next Q(x⃗_{n}) and S(y⃗_{m}) be decidable. This means that

c_{Q} and c_{S} are recursive  (1)

Clearly (i) c_{Q∨S}(x⃗_{n}, y⃗_{n}) = c_{Q}(x⃗_{n}) · c_{S}(y⃗_{n}), and (ii) c_{Q∨S} is recursive. To see the latter, given the input x⃗_{n} and y⃗_{n}, we compute c_{Q∨S}(x⃗_{n}, y⃗_{n}) as

follows: Compute each of c_{Q}(x⃗_{n}) and c_{S}(y⃗_{n}). Multiply the results, return the product and halt.

The remaining Boolean operations are expressible via ¬ and ∨, so there is no more to say. □

Rephrasing in “set-jargon” we get:

9.2 Corollary. Decidable sets are closed under complement, union, intersection.

9.3 Remark. We took the point of view of Computability, in looking at TMs as number processors. As such it is not readily meaningful to ask if decidable sets are closed under string operations, such as concatenation, because the sets of our theory are sets of numbers, or tuples of numbers.

Pretend, however, for a moment that we never restricted the input format, and that we allowed our TMs to process strings rather than “numerical inputs”^{†}

Under these (hypothetical) circumstances, we ask: Are decidable sets (of strings!) closed under concatenation?

That is, if A and B are decidable, is A · B also decidable?

Easily, yes. Given input z we test “z ∈ A · B” as follows:

For each decomposition of z as z = xy^{‡} we process (using deciders for A and B) the queries x ∈ A and y ∈ B. If (and only if) some such decomposition allows both queries to print “0”, then I print a “0” and halt everything.

Otherwise (no decomposition worked), I print “1” and halt everything.

9.4 Theorem. P_{∗} is closed under ∧ and ∨. It is also closed under (∃y), or, as we say, “under projection”.

It is not closed under negation (complement), nor under (∀y).

Proof. Let Q(x⃗_{n}) be semi-decided by a TM M, and S(y⃗_{m}) be semi-decided by a TM N.

Here is how to semi-decide Q(x⃗_{n}) ∨ S(y⃗_{m}):

Given input ⟨x⃗_{n}, y⃗_{m}⟩, we call machine M with input x⃗_{n}, and machine N with input y⃗_{m} and let them crank simultaneously (“co-routines”).

If either one halts, then halt everything!

For ∧ it is almost the same, but our halting criterion is different:

Here is how to semi-decide Q(x⃗_{n}) ∧ S(y⃗_{m}):

Given input ⟨x⃗_{n}, y⃗_{m}⟩, we call machine M with input x⃗_{n}, and machine N with input y⃗_{m} and let them crank simultaneously (“co-routines”).

If both halt, then halt everything!

The (∃y) is very interesting as it introduces a new technique:

Let Q(y, x⃗_{n}) be semi-decidable, say, by machine M.

Here is how to semi-decide (∃y)Q(y, x⃗_{n}):

Idea: Given an input x⃗_{n} for (∃y)Q(y, x⃗_{n}), we want to search for a y such that the input ⟨y, x⃗_{n}⟩—supplied to M—makes M halt. Obviously we cannot try each y = 0, 1, 2, … in turn until we succeed, because it is possible that, for example, ⟨0, x⃗_{n}⟩ makes M “loop forever”, while ⟨1, x⃗_{n}⟩ makes it halt!

†True, numerical inputs are also denoted by strings, but strings of a very restricted type.

‡By “xy” I mean concatenation of x and y in that order. Note that there are exactly |z|+1 such decompositions, “|z|” denoting the length of z.

Intro to Computability via TMs—Part II \begin{matrix}c \\ ◯ \end{matrix} by George Tourlakis

Instead we would like to try “all the values 0, 1, 2, … of y in parallel”— running infinitely many copies of M, one for each input ⟨y, x⃗_{n}⟩,^{†}, and halt iff any M-copy halted.

Of course, this “infinite parallelism” is nonsense, and no amount of Church’s Thesis will save us if we attempt it.

The next best thing to do is use “the poor person’s parallelism”, known as “dovetailing” in the theory.^{‡}

proc EQ(x⃗_{n}) /* To semi-decide (∃y)Q(y, x⃗_{n}) */ T ← 1 while(1) {

1. Perform exactly T steps of the M-computation, for each of the finitely many inputs ⟨y, x⃗_{n}⟩ obtained by letting y = 0, 1, 2, 3, …, T − 1.

2. If any input ⟨y, x⃗_{n}⟩, above, causes M to halt, then halt everything! (exit)

3. T ← T + 1

} The above pseudo-code semi-decides (∃y)Q(y, x⃗_{n}) because it does search

systematically all the y’s, until it finds one that works, iff there is one (in which case the process halts).

By CT (which guarantees a formal version of our code), this makes (∃y)Q(y, x⃗_{n}) semi-decidable.

Why is P_{∗} not closed under negation (complement)? Because we know that H ∈ P_{∗}, but \overline{H} ∉ P_{∗}.

Why is P_{∗} not closed under (∀y)? This is slightly trickier: x ∈ \overline{H} is not semi-decidable—we know this. Now,

x ∈ \overline{H} ≡ ϕ_{x}(x) ↑

Let us translate to machines, computations, and “steps”:

ϕ_{x}(x) ↑≡ M_{x} with input x has no “terminating computation”

or

ϕ_{x}(x) ↑≡ for all y, M_{x} with input x has no computation that halts in y steps

Aha! But we know that

“M_{x} with input x has no computation that halts in y steps”  (1)

is decidable (We do? Where from?).

†That is, testing Q(y, x⃗_{n}), for all the y values simultaneously.

‡An Operating Systems expert, which I am not, may call it “time-slicing”.

Intro to Computability via TMs—Part II \begin{matrix}c \\ ◯ \end{matrix} by George Tourlakis

So, the NOT semi-decidable x ∈ \overline{H} is equivalent to some (∀y)Q(y, x), where Q(y, x) IS decidable hence also semi-decidable (Q(y, x) here is the statement in quotes in (1) above). We rest our case. □

9.5 Example. We look at an easy application (which would not be so easy if we did not have the theorem above!).

Suppose that f is partial recursive.

We prove that the relation y ∈ ran(f) is semi-recursive. Indeed, let f = ϕ_{e}, for some fixed e. We already know (see Example 7.16) that ϕ_{z}(x) = y is semirecursive, hence, “freezing z” (i.e., substituting the constant e into z), we obtain the semi-recursive ϕ_{e}(x) = y.

Digression. Two things: One, we may use λ-notation to indicate “freezing” of variables. I could write just λxy.ϕ_{z}(x) = y. Now I know that z is not an input! I can also write λxy.ϕ_{e}(x) = y. The name of the “constant” (or “parameter”, i.e., the “non-input”) is immaterial. It could be named e, z, w, whatever.

Two, a question: Why freezing an input of a recognizable relation leads to another recognizable relation? Is this also true for decidable relations? End of Digression.

We now continue: y ∈ ran(f) ≡ (∃x)ϕ_{e}(x) = y. Case rests by Theorem 9.4.

16

Intro to Computability via TMs—Part II \begin{matrix}c \\ ◯ \end{matrix} by George Tourlakis

Bibliography

[1] H. Rogers. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.

[2] M. Sipser. Introduction to the Theory of Computation. PWS Publishing Co., Boston, 1997.