CPSC 513 — Assignment #4
Post’s Problem
This assignment can be completed individually or by pairs of students. It is due at 11:59pm on
Wednesday, April 14 and must be submitted as a single PDF file using Gradescope.
Recall that — as presented in the lecture — a solution for Post’s problem was obtained by
describing a construction for a sequence
A0, A1, A2, A3, . . .
of sets — so that Ai ⊆ N for i ∈ N — with the following properties:
(a) This sequence has a limit . This will be called the set A ⊆ N.
(b) A is not recursive, because no L-program computes the characteristic function of A.
(c) This above sequence is recursive. This — and the fact that Ai ⊆ Ai+1 for all i ∈ N —
makes it reasonably easy to prove that A is recursively enumerable.
(d) The leap A′′ of A is ∅(1)-recursive. It follows from this that A cannot be Turing-complete
for the set Σ1 — as needed to solve Post’s problem.
In the alternative solution, considered in this assignment, we will construct a pair of sequences
of subsets of N
A0, A1, A2, A3, . . . and B0, B1, B2, B3, . . . (1)
which satisfy the following properties, instead.
(d) Ai ⊆ Ai+1 and Bi ⊆ Bi+1 for every number i ∈ N, so that these sequences both have
limits. Let A be the limit of the sequence A0, A1, A2, A3, . . . and let B be the limit of the
sequence B0, B1, B2, B3, . . . .
(e) The sequences A0, A1, A2, A3, . . . and B0, B1, B2, B3, . . . are both recursive.
(f) A 6T B and B 6T A.
Note that B does not correspond to the set B used in the construction that is described in the
lecture notes concerning a solution for Post’s problem.
1
1. Show that if the above properties (d), (e) and (f) are satisfied, then the sets A and B
each satisfy the following properties.
(a) A and B are both recursively enumerable.
(b) Neither A nor B is recursive.
(c) Neither A nor B is Turing-complete for Σ1.
It follows that it is sufficient to prove the existence of a pair of sequences of subsets of N as
shown at line (1), to obtain another solution for Post’s problem.
The result to be established next will be of use when arguing that A 6T B and B 6T A.
Recall that if S ⊆ N and n ∈ N then W Sn is the domain of the partial function g : N → N
that is cS-computed by an L-program P such that #(P) = n, where cS : N → {0, 1} is the
characteristic function of the set S.
2. Let A,B ⊆ N. Prove that if there exists a total function f : N→ N such that f(x) ∈ A if
and only if f(x) ∈WBx for all x ∈ N, then A 6T B.
It follows by essentially the same argument that if g : N → N is a total function such that
g(x) ∈ B if and only if g(x) ∈WAx for all x ∈ N, then B 6T A>
For S ⊆ N, and n, k ∈ S, letW Sn,k be the set of numbers x ∈ N such that the L-program#(P )
with an oracle, such that #(P) = n, halts when executed on input x, with an oracle for S, after
taking at most k steps. ThusW Sn,k ⊆ W
S
n,k+1 ⊆ W
S
n for all S ⊆ N and k, n ∈ N. The following
result helps to explain the objectives for the protocol that will be developed.
3. Consider any sequence A0, A1, A2, A3, . . . of subsets of N such that Ai ⊆ Ai+1 for all
i ∈ N, and let A =
⋃
i∈NAi. Prove that, for all a, x ∈ N, if a ∈ W
A
x then there exists a
number m ∈ N such that
a ∈WAnx,n
for every number n ∈ N such that n ≥ m.
The process, given below, will be used to construct sequences of subsets of N, as shown at
line (1) and total functions fA,B : N→ N and fB,A : N → N such that the following the follow-
ing objectives are satisfied.
• Objective A–B, i for each number i ∈ N: fA,B(i) ∈ A if and only if fA,B(i) ∈W
B
i .
• Objective B–A, i for each number i ∈ N: fB,A(i) ∈ B if and only if fB,A(i) ∈W
A
i .
2
These objectives are (eventually) achieved using a process that makes use of a pair of vertical
lists of the natural numbers, called the A-List and the B-List , the smaller numbers above
larger ones, as follows.
A-List B-List
0 0
1 1
2 2
3 3
4 4
...
...
At each point in this process a finite number of the numbers in the list are marked with either
“+” or “−”, but not both at once:
A-List B-List
0 + 0
1 1 −
2 2
3 3
4 4
...
...
Indeed, this process proceeds in a series of stages, numbered by positive integers, with sym-
bols in the A-List possibly being marked with + and symbols in the B-List possibly being
marked with− in odd-numbered rounds, and with symbols in the B-List possibly being marked
with + and symbols in the A-List possibly being marked with − in (positive) even-numbered
rounds.
Only a finite number of symbols can be marked in this way in each round. so that, A0 = B0 = ∅
and, for each positive integer i,Ai is the set of numbers in theA-list marked with “+” after round
2i− 1, and Bi is the set of numbers in the B-list marked after round 2i.
Thus, if the lists include markers as shown above after round 1, and no integers greater than 4
are marked on either list, then A1 = {0}.
Once the process has been described, it will be clear that no number that is marked with “+”
will ever lose that marker, on either list — so that it will be true that Ai ⊆ Ai+1 and Bi ⊆ Bi+1
for all i ∈ N, as desired.
3
On the other hand, it will be possible that a number marked with “−” on a list will have this
marker replaced with “+” at a later point.
A number on either list is said to be vacant if it is not marked with “+”. Thus, if no numbers
greater than 4 are marked on either of the A-list or B-list, above, then every number on the
A-list except 0 is vacant, and all numbers on the B-list are vacant.
The numbers on the A-list are also marked with “movable markers” 0
A
, 1
A
, 2
A
, . . . and
the numbers on the B-list are also marked with “movable markers” 0
B
, 1
B
, 2
B
, . . . —with
a finite (initial) number of each of these used at each point in the process. For example, the
lists might be as follows.
A-List B-List
0
A
0 + 0
1
A
1 1 −
2 0
B
2
3 3
4 4
...
...
A number on either list is said to be free if it is not marked with any marker and, furthermore,
the is no number below it on this list that is not marked with any marker, either. For example,
if the lists are as shown above and no number greater than 4 has a marker on either list, then
every number greater than or equal to 2 is free on the A-list, and every number greater than or
equal to 3 is free on the B-list.
Initially, no number on either list is marked with either “+” or “−”, so that A0 = B0 = ∅. 0 is
marked with 0
A
on the A-List, and 0 is marked with 0
B
on the B-List. The markers i
A
and i
B
are not used for any positive integer i, so lists are initially as follows.
A-List B-List
0
A
0 0
B
0
1 1
2 2
3 3
4 4
...
...
4
For each number n ∈ N, stage 2n + 1 is as follows.
(a) Assign marker n+ 1
A
to the smallest free integer in the A-list.
(b) For 0 ≤ i ≤ n + 1, let xi ∈ N be the number in the A-list with marker i A; if xi is vacant,
check whether xi ∈W
Bn
i,n+1.
(c) If there is no number k ∈ N such 0 ≤ k ≤ n+1, xk is vacant (that is, not marked with “+”)
in the A-list, and xk ∈W
Bn
k,n+1, then proceed to stage 2n + 2 without making any changes
— so that An+1 = An. Otherwise set j to be the smallest integer k that satisfies these
properties and continue as follows.
(d) Mark the number xj labelled by j
A
in the A-list with “+”, so that it is no longer vacant,
and so that An+1 = An ∪ {xj}.
Mark any number in Bn, whose membership in Bn was queried using the oracle, during
the computation of oracle program with number j on input j, with “−” in the B-list. (Note
that this could not have included any numbers currently marked with “+”.)
(e) Letm ∈ N be the smallest number on theB-list that is currently free. For i = j, j+1, . . . , n,
move marker i
B
from its current position down to the number m+ i− j.
Stage 2n + 2 is almost the same, except that the roles of A and B have been exchanged. In
particular, for each number n ∈ N, stage 2n + 2 is as follows.
(a) Assign marker n+ 1
B
to the smallest free integer in the B-list.
(b) For 0 ≤ i ≤ n+ 1, let xi ∈ N be the number in the B-list with marker i B ; if xi is vacant,
check whether xi ∈W
An+1
i,n+1 .
(c) If there is no number k ∈ N such 0 ≤ k ≤ n+1, xk is vacant (that is, not marked with “+”)
in the B-list, and k ∈ W
An+1
k,n+1, then proceed to stage 2n + 3 without making any changes
— so that Bn+1 = Bn. Otherwise set j to be the smallest integer k that satisfies these
properties and continue as follows.
(d) Mark the number labelled by j
B
in the B-list with “+”, so that it is no longer vacant. Mark
any number in An+1, whose membership in An+1 was queried using the oracle, during the
computation of oracle program with number j on input j, with “−” in the A-list. (Note that
this could not have included any numbers currently marked with “+”.)
(e) Let m ∈ N be the smallest number on the A-list that is currently free. For i = j + 1, j +
2, . . . , n, move marker i
A
from its current position down to the number m+ i− j - 1.
5
It will be useful to bound the number of times that each of the markers i
A
and i
B
can be
moved (after being initialized), during this process, for each number i ∈ N.
• The marker 0
A
is never moved at all, because this can only happen during part (e) of
stage 2n + 2, for some number n ∈ N, when j < 0 ≤ n, for the number j ∈ N set
immediately before this — and there is no number j ∈ N such that j < 0.
• The marker 0
B
is moved at most once. This happens during part (e) of stage 2n + 1,
for some number n ∈ N, when j = 0, for the number j ∈ N set immediately before
this. It must have been the case that the number marked by the marker 0
A
was vacant
on the A-list immediately before this (as a consideration of part (c) of this stage should
show), and this is never true after this, because this number is marked by “+” as part of
this process and the marker 0
A
is not moved.
• For i ≥ 1, the marker i
A
can be moved every time the marker i− 1
A
is. Indeed,
the only time(s) that i
A
is moved, when i− 1
A
is not, are during executions of even-
numbered stages when the number marked with the label i− 1
B
is initially vacant
and is marked with “+”. Since this can happen at most once for each position the marker
i− 1
B
occupies, the number of times that this can happen is one more than the number
of times that marker i− 1
B
is moved.
• Similarly, for i ≥ 1, the marker i
B
can be moved every time the marker i− 1
B
is.
Indeed, the only time(s) that marker i
B
is moved, when marker i− 1
B
is not, are
during executions of odd-numbered stages when the number marked with the label i
A
is initially vacant and is marked with “+”. Since this can happen at most once for each
position the marker i
A
occupies, the number of times that this can happen is one more
than the number of times that the marker i
A
is moved.
4. Recall the sequence of Fibonacci numbers F0, F1, F2, F3, . . . ; for n ∈ N,
Fn =


0 if n = 0,
1 if n = 1,
Fn−2 + Fn−1 if n ≥ 2.
Use the above information to show that, for all n ∈ N, during the above process,
• the marker n
A
is moved at most F2n+2 − 1 times, and
• the marker n
B
is moved at most F2n+3 − 1 times.
6
For i ∈ N, let fA,B(i) be the final value marked with i A in the A-list, and let fB,A(i) be the
final value marked with marker i
B
in the B list. It now follows that these values exist, so that
fA,B : N→ N and fB,A”N→ N are both well-defined total functions.
Suppose, now, that i ∈ N and that fA,B(i) ∈ A. Then it follows, by the definition of A, that
there exists a number ℓ ∈ N such that
fA,B(i) ∈ Aℓ+1 \ Aℓ.
5. A consideration of the above process should confirm that there is a number k ∈ N such
that fA,B(i) = xk during stage 2ℓ+1 (with k used as the value for “j” at this point) — so
that the number fA,B(i) is marked by k A at this stage of the process.
(a) Prove that k = i.
(b) Use this to prove thatWBi .
Hint: It follows by the result of part (a), and an examination of the process that has
been described, that fA,B(i) ∈ W
Bℓ
i,ℓ+1. What do you need to establish, in order to
conclude that fA,B(i) ∈W
B
i,ℓ+1 ⊆W
B
i , as well?
Thus, if fA,B(i) ∈ A then fA,B(i) ∈ W
B
i . Essentially the same argument can be used to
establish that if fB,A(i) ∈ B then fB,A(i) ∈ W
A
i as well. The following will be of use when
establishing the converse.
6. Prove that if i ∈ N and fA,B(i) /∈ A then fA,B(i) /∈W
B
i .
Note: This can be established using a proof by contradiction (rather than using mathe-
matical induction, or a similar proof technique) — but proving this requires close attention
to the process that has been described.
It follows by essentially the same argument that if i ∈ N then fB,A(i) /∈ B then fB,A(i) /∈W
A
i .
7. Use the above to prove that A 6T B and B 6T A.
Note: This should not be hard to do, if the results that have now been established are
used.
7

欢迎咨询51作业君