Closed Set

A Closed Set decider is a decider which proves Turing machines infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). 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.

Note that C may contain configurations that M will never reach and in fact this is usually the case. In this way, closed set deciders generalize a behavior in order to simplify its proof of non-halting. A closed set proof does not tell you what the TM will do precisely, instead it tells you that (whatever it does) it will never escape some broad category.

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.

Deciders

We have described closed sets above as general mathematical sets. But in order for a decider to effectively use a closed set method it must define these sets precisely using some sort of "tape language". The exact choice of tape language is one of the primary distinctions between different closed set deciders.

• Closed Tape Language (CTL) defines the closed set using restricted types of Regular Expressions.
• Finite Automata Reduction (FAR) defines the closed set using Regular Languages.
• Closed Position Set (CPS) defines the closed set using a sort of "Markov Chain" language.

For each of these methods, the difficult part is determining a closed set for a machine and proving that that set is closed.

See also

• https://www.sligocki.com/2022/06/10/ctl.html