Turing Machines

Single correct

• ATuring machine $M$ halts on all input strings in $\{0,1\}^*$
• BTuring machine $M$ accepts all input strings in $L$
• CTuring machine $M$ rejects all input strings in $\{0,1\}^* - L$
• DTuring machine $M$ accepts all input strings in $L$ and rejects all input strings in $\{0,1\}^* - L$

One or more correct

• AThe intersection of two regular languages is regular.
• BThe intersection of two context-free languages is context-free.
• CThe intersection of two recursive languages is recursive.
• DThe intersection of two recursively enumerable languages is recursively enumerable.

Answer key coming soon

One or more correct

• AEvery subset of a recursively enumerable language is recursive.
• BIf a language $L$ and its complement $\bar{L}$ are both recursively enumerable, then $L$ must be recursive.
• CComplement of a context-free language must be recursive.
• DIf $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ must be deterministic context-free.

Answer key coming soon

Single correct

• Aclosed under complementation.
• Bclosed under intersection.
• Ca subset of the set of all recursive languages.
• Dan uncountable set.

Single correct

• A$f$ is computable if and only if $L_f$ is recursive.
• B$f$ is computable if and only if $L_f$ is recursively enumerable.
• CIf $f$ is computable then $L_f$ is recursive, but not conversely.
• DIf $f$ is computable then $L_f$ is recursively enumerable, but not conversely.

Answer key coming soon

Single correct

• A1 and 4 only
• B1 and 3 only
• C2 only
• D3 only

Answer key coming soon