Closure Properties - Models of Computation

We now consider closure properties of recognizable and decidable languages.

7.5.1Closure Properties for Decidable Languages¶

Closure properties for decidable languages are relatively straightforward since we can easily simulate deciders as they are guaranteed to always halt.

7.5.2Closure Properties for Recognizable Languages¶

Proof 3

Let $M_1$ and $M_2$ be the recognizers for $L$ and $L^c$ , respectively.

Consider an input string $w$ . We know that either $w$ is in $L$ or is in $L^c$ . If $w$ is in $L$ , then $M_1$ will eventually halt and accept; if $w$ is in $L^c$ , then $M_2$ will eventually halt and accept.

A first try is to first simulate $M_1$ on $w$ and then $M_2$ on $w$ . However, since $M_1$ is only a recognizer, it may not halt on $w$ , and so the simulation may never end. The same problem remains if we first simulate $M_1$ then $M_2$ .

What we will do is to instead simulate $M_1$ and $M_2$ in a round-robin fashion. Here’s a description for the decider for $L$ :

On input $w$ :

Compute the initial configurations of $M_1$ and $M_2$ on $w$
While neither of the current configuration of $M_1$ and $M_2$ has halted:
- Compute the next configuration of $M_1$ by applying its transition function to its current configuration
- Compute the next configuration of $M_2$ by applying its transition function to its current configuration
Accept when $M_1$ accepts or $M_2$ rejects
Reject when $M_1$ rejects or $M_2$ accepts

Since we have already argued earlier that either $M_1$ or $M_2$ will eventually halt on $w$ , the while loop will eventually terminate.

A consequence of this is that we get that $A^c_{TM}$ is not recognizable. In particular, $A^c_{TM}$ is the language consisting of the encoding of a Turing machine $M$ and a string $w$ such that $M$ does not accept $w$ .

This is interesting as it tells us that there are natural problems of practical interest that are not recognizable.

Models of Computation

Reductions

Models of Computation

Mathematical Background (Notation and terms)

7.5Closure Properties

7.5.1Closure Properties for Decidable Languages¶

7.5.2Closure Properties for Recognizable Languages¶