Clarification on exercise 4.2

Clarification on exercise 4.2

par ANNA BRIOTTO,
Nombre de réponses : 0

Hi everyone!

This is to give a clarification about exercise 4.2 from the exercise handout, in particular, about the part on the converse implication:
image.png

The predicate P(x, y) = (y = 2x) & (y ∉ Wx) is clearly not semi-decidable, as it requires checking (y ∉ Wx).
However, the exitentially quantified version  Q( y ) = ∃x.P(x,y) =∃x.(y = 2x) & (y ∉ Wx) is also not semi-decidable. 
We have two cases:

  • y is odd: in this case the predicate  Q( y ) = ∃x.(y = 2x) & (y ∉ Wx) is always false, as we only have integer number as function indices. This case is decidable and not problematic
  • y is even: in this case the predicate boils down to checking (y ∉ Wy/2), which is undecidable. This happens because both parts of the conjunction must be true simultaneously, and the condition (y = 2x) uniquely determines (x = y/2).

A correct counterexample (kindly suggested by Prof. Baldan) is instead: P(x,y) = (y=x)  v  (y ∉ Wy).
In fact, P(x,y) is not semi-decidable, as for all tuples of inputs (y, x) with y != x, the first disjunct is false, thus deciding the predicate needs checking (y ∉ Wy). This not semi-decidable, as it requires checking membership in the complement of K.

The existentially quantified version, Q(x) = ∃y. P(x,y) = ∃y. (y=x)  v  (y ∉ Wy) on the other hand, is decidable, as it is always true.

Indeed, for any fixed x:

  • We can choose some y ≠ x

  • For such y, the predicate reduces to (y ∉ Wy)

  • We know that there exist infinitely many y such that y ∉ Wy, since the complement of K is infinite

Therefore, there always exists at least one y making the formula true

The crucial difference between the two cases is that in the first predicate the existential quantifier does not add expressive power, since the constraint y=2x uniquely determines x. As a result, the existentially quantified predicate remains non–semidecidable.

In contrast, in the second predicate the existential quantifier ranges over infinitely many values of y, and since the complement of the halting set is non-empty, the predicate will always be satisfied. This makes the existentially quantified version decidable, despite the original predicate being non–semidecidable.

I hope that this clarification is useful!

In case, don't hesistate to contact me.

Best,
Anna