Closed Set

A Closed Set decider is a decider which proves Turing machines infinite by defining a set which the TM enters and once it enters it always returns and thus never halts. Examples of closed set deciders are Closed Tape Language, Closed Position Set and Finite Automata Reduction.

General Definition

Given a specific Turing machine M, a set C of configurations is a closed set for M if:

1. M enters C: $\exists c\in C:O\to ^{*}c$ (where $O$ is the initial config).
2. C is closed: $\forall c\in C:\exists d\in C:c\to ^{+}d$. Every configuration in C returns to a new config in C after some positive number of steps.
3. C is non-halting: $\forall c\in C:$ c is not a halting config.

We can easily see that if all of these conditions hold, then M can never halt because it will enter set C and once it has entered, it will return infinitely often and these configurations will never be halt configs.

Stepwise Closed Set

It is often easier to prove that C is a closed set if it satisfies a stricter set of rules.

Given a specific Turing machine M, a set S of configurations is a stepwise closed set for M if:

1. M starts in S: $O\in S$ (where $O$ is the initial config).
2. S is closed under single step: $\forall c\in S:c\to ^{1}d\implies d\in S$. If you take one step from any configuration in S, you remain in S.
3. S is non-halting: $\forall c\in S:$ c is not a halting config.

Any stepwise closed set is general closed set.