Coursify

Closure Properties of Turing-Language Classes: Identifying False Statements

Closure Properties of Turing-Language Classes: Identifying False Statements

Verified Sources
Sep 11, 2026

We interpret the statements using standard terminology:

  • keyword: Languages accepted by some TM; non-members may cause infinite loops.
  • keyword: Languages decided by some TM that always halts and answers membership.
  • keyword: If LL is in the class, then after an operation (e.g., union), the resulting language stays in the class.
  • keyword: L‾=Σ∗∖L\overline{L}=\Sigma^* \setminus L.

The question asks: Which statements are false? (Choices are combinations of which statements are false.) The correct answer is: (iii) B only.

This corresponds to:

  • A is true,
  • B is false,
  • C is true,
  • D is true.

So the false statements are B only. Therefore the correct option is (iii) B only. 2

Footnotes

  1. 6.045: Closure Properties (MIT OCW lecture PDF) - States RE is closed under union and intersection, but not closed under complement. ↩

  2. Turing-Machine-Closure-Properties condensed PDF - Recaps: RE languages closed under union/intersection (and not complement); decidable closed under union/intersection/complement. ↩

Closure Properties of Decidable and Turing recognizable languages

Statement-by-statement truth values

Below, “true/false” refers to whether the claimed closure/equivalence statement holds for the standard classes of Turing-recognizable and Turing-decidable languages.

Key closure facts (the ones used most here):

  • Turing-recognizable (RE) languages are closed under union and intersection, but not closed under complementation. 2
  • Turing-decidable languages are closed under union, intersection, and complement (hence also intersection and complement). 2

Now we justify each option carefully.

Footnotes

  1. 6.045: Closure Properties (MIT OCW lecture PDF) - States RE is closed under union and intersection, but not closed under complement. ↩

  2. Turing decidable languages are closed under intersection. (UVic notes) - Contains theorems/proofs for closure under intersection and complement for decidable languages. ↩

  3. Decidability (Stanford handout) - Includes closure of decidable languages under complementation and intersection/union via parallel execution. ↩

  4. Turing-Machine-Closure-Properties condensed PDF - Recaps: RE languages closed under union/intersection (and not complement); decidable closed under union/intersection/complement. ↩

Statement A

A. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

This is true: NDTMs and DTM are computationally equivalent in the sense that for every NDTM there exists a DTM recognizing/deciding the same language (i.e., they generate the same family of languages). 2

So A is not false.

Footnotes

  1. Turing machine equivalents - Wikipedia - Explains that NDTM can be turned into DTM and they are computationally equivalent. ↩

  2. Turing Machines - andrew.cmu.edu - States: every nondeterministic TM has an equivalent deterministic TM; proof idea given. ↩

Statement B

B. Turing recognizable languages are closed under union and complementation.

This statement is false because although RE languages are closed under union, they are not closed under complement in general. 2

So B is false, and thus it must be included among “false statements”.

Footnotes

  1. 6.045: Closure Properties (MIT OCW lecture PDF) - States RE is closed under union and intersection, but not closed under complement. ↩

  2. Turing-Machine-Closure-Properties condensed PDF - Recaps: RE languages closed under union/intersection (and not complement); decidable closed under union/intersection/complement. ↩

Statement C

C. Turing decidable languages are closed under intersection and complementation.

This is true. If a language is decidable, its complement is also decidable (flip accept/reject while preserving halting), and decidable languages are also closed under intersection (run the two deciders and accept iff both accept). 2

So C is not false.

Footnotes

  1. Decidability (Stanford handout) - Includes closure of decidable languages under complementation and intersection/union via parallel execution. ↩

  2. Turing decidable languages are closed under intersection. (UVic notes) - Contains theorems/proofs for closure under intersection and complement for decidable languages. ↩

Statement D

D. Turing recognizable languages are closed under union and intersection.

This is true: RE languages are closed under both union and intersection (construct machines that run recognizers in parallel and accept according to the operation). 2

So D is not false.

Footnotes

  1. 6.045: Closure Properties (MIT OCW lecture PDF) - States RE is closed under union and intersection, but not closed under complement. ↩

  2. Turing-Machine-Closure-Properties condensed PDF - Recaps: RE languages closed under union/intersection (and not complement); decidable closed under union/intersection/complement. ↩

How to decide which statements are false (closure-logic checklist)

  1. 1
    Step 1

    Identify whether the statement talks about NTM→DTM (machine equivalence) or closure of RE vs decidable (REC).

  2. 2
    Step 2

    Use the fact that RE is not closed under complementation, even though RE is closed under union. Therefore any statement claiming RE is closed under complement is false. 2

    Footnotes

    1. 6.045: Closure Properties (MIT OCW lecture PDF) - States RE is closed under union and intersection, but not closed under complement. ↩

    2. Turing-Machine-Closure-Properties condensed PDF - Recaps: RE languages closed under union/intersection (and not complement); decidable closed under union/intersection/complement. ↩

  3. 3
    Step 3

    Decidable languages are closed under complement and under intersection. 2

    Footnotes

    1. Decidability (Stanford handout) - Includes closure of decidable languages under complementation and intersection/union via parallel execution. ↩

    2. Turing decidable languages are closed under intersection. (UVic notes) - Contains theorems/proofs for closure under intersection and complement for decidable languages. ↩

  4. 4
    Step 4

    RE is closed under union and intersection. 2

    Footnotes

    1. 6.045: Closure Properties (MIT OCW lecture PDF) - States RE is closed under union and intersection, but not closed under complement. ↩

    2. Turing-Machine-Closure-Properties condensed PDF - Recaps: RE languages closed under union/intersection (and not complement); decidable closed under union/intersection/complement. ↩

  5. 5
    Step 5

    Only B is false ⇒ choose the option that says 'B only', which is (iii).

Common pitfall

It’s easy to mix up RE vs decidable (REC). Decidable languages are closed under complement, but RE languages are not necessarily closed under complement. 2

Footnotes

  1. 6.045: Closure Properties (MIT OCW lecture PDF) - States RE is closed under union and intersection, but not closed under complement. ↩

  2. Turing-Machine-Closure-Properties condensed PDF - Recaps: RE languages closed under union/intersection (and not complement); decidable closed under union/intersection/complement. ↩

Fast elimination strategy

In multi-select closure questions, look first for any claim about RE under complement. If it says RE is closed under complement, that statement is almost always the one that’s false.

Footnotes

  1. 6.045: Closure Properties (MIT OCW lecture PDF) - States RE is closed under union and intersection, but not closed under complement. ↩

Mental roadmap for closure-property questions

Detect the class

1

RE vs decidable (REC) vs all languages."

Check the operation

2

Union/intersection/complement behave differently across classes."

Apply known closure theorems

3

RE: closed under union/intersection, not complement; Decidable: closed under intersection/complement."

Choose the option

4

Collect exactly which statements are false and match to (i)-(iv)."

Truth table for A–D

1 = true, 0 = false

Why “RE closed under union/intersection” but not “complement” matters

Key terms to master

1 / 4
Question · Term

[keyword]{def="Turing recognizable (RE) languages"}

Click to reveal
Answer · Definition

Accepted by a TM; non-members may cause infinite loop.

Knowledge Check

Question 1 of 4
Q1Single choice

Which statements are false?

Explore Related Topics

1

8085 Register Pairing for 16-Bit Operations: Why Register E Pairs with Register D

The Intel 8085 microprocessor supports only three fixed 16‑bit register pairs—BC, DE, and HL—so register E can be paired only with register D.

  • Valid 16‑bit pairs are BC, DE, and HL; no other combinations are allowed.
  • E belongs to the DE pair, not to A, B, or C.
  • Instructions such as LXI, INX, DCX, and DAD operate on these predefined pairs.
  • HL is typically used as a memory pointer, while DE mainly holds 16‑bit data.
  • Programmers cannot create custom register pairs; the accumulator A is a separate special‑purpose register.
2

Understanding the MCQ: Compiler, Interpreter, Loader/Linker, or None?

The MCQ conflates formal‑machine concepts (a Turing‑like Machine MM with an unbounded tape) with programming‑language tools, making “None of the mentioned” the only academically correct choice.

  • An infinite tape is a modeling assumption; any actual computation uses only a finite portion.
  • Compilers translate whole programs, interpreters execute statements incrementally, and loaders/linkers build/run executables—they do not bound the tape.
  • An “infinite language” is a set of strings, not a single infinite input to MM.
  • The correct answer is  (iv) None of the mentioned .\,\boxed{\text{(iv) None of the mentioned}}\,.
  • In exams, identify domain mismatches and choose the option that rejects the inconsistency.
3

Functional-Dependency Analysis and Normalization of R(A, B, C, D, E, F)

Browse all research articles